document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1210199>Question 1210199</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Find the number of sequences (a_1, a_2, a_3, \dots, a_8) such that:<BR>\n" );
document.write( "* a_i \in \{1, 2, 3, 4, 5, 6, 7, 8\} for all 1 \le i \le 8.<BR>\n" );
document.write( "* Every number1, 2, 3, 4, 5, 6, 7, 8 appears at least once in the sequence. </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #851549 by </B><A HREF=/tutors/aboutme.mpl?userid=CPhill><B>CPhill(1959)</B></A><img src=\"/images/stars/stars-12.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=CPhill><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=CPhill><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=851549\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> Let's solve this problem using the Principle of Inclusion-Exclusion.\r<BR>\n" );
document.write( "\n" );
document.write( "**1. Total Number of Sequences**\r<BR>\n" );
document.write( "\n" );
document.write( "* Each a_i can be any of the 8 numbers {1, 2, 3, 4, 5, 6, 7, 8}.<BR>\n" );
document.write( "* There are 8 positions in the sequence.<BR>\n" );
document.write( "* Total number of sequences = 8⁸.\r<BR>\n" );
document.write( "\n" );
document.write( "**2. Inclusion-Exclusion Principle**\r<BR>\n" );
document.write( "\n" );
document.write( "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)|.\r<BR>\n" );
document.write( "\n" );
document.write( "* |S| = 8⁸<BR>\n" );
document.write( "* |A_i| = 7⁸ (sequences without the number i)<BR>\n" );
document.write( "* |A_i ∩ A_j| = 6⁸ (sequences without numbers i and j)<BR>\n" );
document.write( "* |A_i ∩ A_j ∩ A_k| = 5⁸ (sequences without numbers i, j, k)<BR>\n" );
document.write( "* ...<BR>\n" );
document.write( "* |A_1 ∩ A_2 ∩ ... ∩ A_7| = 1⁸ (sequences without numbers 1 to 7)<BR>\n" );
document.write( "* |A_1 ∩ A_2 ∩ ... ∩ A_8| = 0⁸ = 0 (sequences without all numbers 1 to 8)\r<BR>\n" );
document.write( "\n" );
document.write( "By the Principle of Inclusion-Exclusion:\r<BR>\n" );
document.write( "\n" );
document.write( "|A_1 ∪ A_2 ∪ ... ∪ A_8| = Σ |A_i| - Σ |A_i ∩ A_j| + Σ |A_i ∩ A_j ∩ A_k| - ...\r<BR>\n" );
document.write( "\n" );
document.write( "|A_1 ∪ A_2 ∪ ... ∪ A_8| = ⁸C₁ * 7⁸ - ⁸C₂ * 6⁸ + ⁸C₃ * 5⁸ - ⁸C₄ * 4⁸ + ⁸C₅ * 3⁸ - ⁸C₆ * 2⁸ + ⁸C₇ * 1⁸ - ⁸C₈ * 0⁸\r<BR>\n" );
document.write( "\n" );
document.write( "The number of sequences we want is:\r<BR>\n" );
document.write( "\n" );
document.write( "8⁸ - |A_1 ∪ A_2 ∪ ... ∪ A_8|\r<BR>\n" );
document.write( "\n" );
document.write( "**3. Calculate the Values**\r<BR>\n" );
document.write( "\n" );
document.write( "* 8⁸ = 16777216<BR>\n" );
document.write( "* ⁸C₁ = 8<BR>\n" );
document.write( "* ⁸C₂ = 28<BR>\n" );
document.write( "* ⁸C₃ = 56<BR>\n" );
document.write( "* ⁸C₄ = 70<BR>\n" );
document.write( "* ⁸C₅ = 56<BR>\n" );
document.write( "* ⁸C₆ = 28<BR>\n" );
document.write( "* ⁸C₇ = 8<BR>\n" );
document.write( "* ⁸C₈ = 1\r<BR>\n" );
document.write( "\n" );
document.write( "* 8 * 7⁸ = 8 * 5764801 = 46118408<BR>\n" );
document.write( "* 28 * 6⁸ = 28 * 1679616 = 47029248<BR>\n" );
document.write( "* 56 * 5⁸ = 56 * 390625 = 21875000<BR>\n" );
document.write( "* 70 * 4⁸ = 70 * 65536 = 4587520<BR>\n" );
document.write( "* 56 * 3⁸ = 56 * 6561 = 367416<BR>\n" );
document.write( "* 28 * 2⁸ = 28 * 256 = 7168<BR>\n" );
document.write( "* 8 * 1⁸ = 8 * 1 = 8<BR>\n" );
document.write( "* 1 * 0⁸ = 0\r<BR>\n" );
document.write( "\n" );
document.write( "* |A_1 ∪ A_2 ∪ ... ∪ A_8| = 46118408 - 47029248 + 21875000 - 4587520 + 367416 - 7168 + 8 - 0<BR>\n" );
document.write( "* |A_1 ∪ A_2 ∪ ... ∪ A_8| = 16334520\r<BR>\n" );
document.write( "\n" );
document.write( "* 8⁸ - |A_1 ∪ A_2 ∪ ... ∪ A_8| = 16777216 - 16334520 = 442696\r<BR>\n" );
document.write( "\n" );
document.write( "**Therefore, the number of sequences is 442696.**<BR>\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );