SOLUTION: Find the number of sequences (a_1, a_2, a_3, \dots, a_8) such that: * a_i \in \{1, 2, 3, 4, 5, 6, 7, 8\} for all 1 \le i \le 8. * Every number1, 2, 3, 4, 5, 6, 7, 8 appears at le

Question 1210199: Find the number of sequences (a_1, a_2, a_3, \dots, a_8) such that:
* a_i \in \{1, 2, 3, 4, 5, 6, 7, 8\} for all 1 \le i \le 8.
* Every number1, 2, 3, 4, 5, 6, 7, 8 appears at least once in the sequence.
Found 3 solutions by CPhill, greenestamps, ikleyn:
Answer by CPhill(1959)   (Show Source): You can put this solution on YOUR website!
Let's solve this problem using the Principle of Inclusion-Exclusion.
**1. Total Number of Sequences**
* Each a_i can be any of the 8 numbers {1, 2, 3, 4, 5, 6, 7, 8}.
* There are 8 positions in the sequence.
* Total number of sequences = 8⁸.
**2. Inclusion-Exclusion Principle**
Let S be the set of all sequences. Let A_i be the set of sequences that do not contain the number i. We want to find |S \setminus (A_1 ∪ A_2 ∪ ... ∪ A_8)|.
* |S| = 8⁸
* |A_i| = 7⁸ (sequences without the number i)
* |A_i ∩ A_j| = 6⁸ (sequences without numbers i and j)
* |A_i ∩ A_j ∩ A_k| = 5⁸ (sequences without numbers i, j, k)
* ...
* |A_1 ∩ A_2 ∩ ... ∩ A_7| = 1⁸ (sequences without numbers 1 to 7)
* |A_1 ∩ A_2 ∩ ... ∩ A_8| = 0⁸ = 0 (sequences without all numbers 1 to 8)
By the Principle of Inclusion-Exclusion:
|A_1 ∪ A_2 ∪ ... ∪ A_8| = Σ |A_i| - Σ |A_i ∩ A_j| + Σ |A_i ∩ A_j ∩ A_k| - ...
|A_1 ∪ A_2 ∪ ... ∪ A_8| = ⁸C₁ * 7⁸ - ⁸C₂ * 6⁸ + ⁸C₃ * 5⁸ - ⁸C₄ * 4⁸ + ⁸C₅ * 3⁸ - ⁸C₆ * 2⁸ + ⁸C₇ * 1⁸ - ⁸C₈ * 0⁸
The number of sequences we want is:
8⁸ - |A_1 ∪ A_2 ∪ ... ∪ A_8|
**3. Calculate the Values**
* 8⁸ = 16777216
* ⁸C₁ = 8
* ⁸C₂ = 28
* ⁸C₃ = 56
* ⁸C₄ = 70
* ⁸C₅ = 56
* ⁸C₆ = 28
* ⁸C₇ = 8
* ⁸C₈ = 1
* 8 * 7⁸ = 8 * 5764801 = 46118408
* 28 * 6⁸ = 28 * 1679616 = 47029248
* 56 * 5⁸ = 56 * 390625 = 21875000
* 70 * 4⁸ = 70 * 65536 = 4587520
* 56 * 3⁸ = 56 * 6561 = 367416
* 28 * 2⁸ = 28 * 256 = 7168
* 8 * 1⁸ = 8 * 1 = 8
* 1 * 0⁸ = 0
* |A_1 ∪ A_2 ∪ ... ∪ A_8| = 46118408 - 47029248 + 21875000 - 4587520 + 367416 - 7168 + 8 - 0
* |A_1 ∪ A_2 ∪ ... ∪ A_8| = 16334520
* 8⁸ - |A_1 ∪ A_2 ∪ ... ∪ A_8| = 16777216 - 16334520 = 442696
**Therefore, the number of sequences is 442696.**

Answer by greenestamps(13198)   (Show Source): You can put this solution on YOUR website!

The sequence has 8 terms; each term is an integer from 1 to 8 inclusive; and the sequence must contain each of those integers at least once.

That means the sequence contains each of those integers EXACTLY once. So the number of sequences is simply the number of arrangements of the 8 integers, which is 8! = 40,320.

ANSWER: 40,320

Answer by ikleyn(52776)   (Show Source): You can put this solution on YOUR website!
.

The solution by @CPhill is unjustifiably complicated and fatally incorrect.

His answer is incorrect.

See the correct solution in the post by @greenestamps.

RELATED QUESTIONS
A permutation of the numbers (1,2,3,\dots,n) is a rearrangement of the numbers in which... (answered by CPhill,ikleyn)
A permutation of the numbers (1,2,3,\dots,n) is a rearrangement of the numbers in which... (answered by CPhill)
The table below shows the customer rating of five restaurants in the metro city guide to (answered by Fombitz)
Let : U = {1, 2, 3, 4, 5, 6, 7, 8} A = {1, 2, 4, 5, 8} B = {2, 3, 4,... (answered by Fombitz)
Given that a/b = 1- 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + 1/7 - 1/8 + 1/9 - 1/10 , such that... (answered by ikleyn)
In the series 6 4 1 2 2 8 7 4 2 1 5 3 8 6 2 1 7 1 4 4 3 2 8 6 how many pair of successive (answered by ikleyn)
Find an Equation for the least square line of the data below. Use the equation to predict (answered by stanbon)
Write a recursive rule that describes the pattern in the total number of dots.... (answered by ikleyn)
6) For each of the following sequences, write the next 3 terms. If arithmetic or... (answered by ewatrrr)