document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1210200>Question 1210200</A>: <I><SPAN STYLE=\"word-break: break-all;\"> A permutation of the numbers (1,2,3,\dots,n) is a rearrangement of the numbers in which each number appears exactly once. For example, (2,5,1,4,3) is a permutation of (1,2,3,4,5).\r<BR>\n" );
document.write( "\n" );
document.write( " \r<BR>\n" );
document.write( "\n" );
document.write( "Find the number of permutations (x_1, x_2, \dots, x_8) on (1, 2, 3, \dots, 8), such that (x_i, x_{i + 1}), 1 \le i \le 7, is never equal to (1,2), (3,4), (5,6), or (7,8).  (However, (x_i, x_{i + 1}) can be equal to (2,1), (4,3), (6,5), or (8,7).) </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #851556 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=851556\">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 Permutations**\r<BR>\n" );
document.write( "\n" );
document.write( "* The total number of permutations of (1, 2, 3, ..., 8) is 8! = 40320.\r<BR>\n" );
document.write( "\n" );
document.write( "**2. Define the Sets**\r<BR>\n" );
document.write( "\n" );
document.write( "Let:\r<BR>\n" );
document.write( "\n" );
document.write( "* A₁ be the set of permutations where (1, 2) appears.<BR>\n" );
document.write( "* A₂ be the set of permutations where (3, 4) appears.<BR>\n" );
document.write( "* A₃ be the set of permutations where (5, 6) appears.<BR>\n" );
document.write( "* A₄ be the set of permutations where (7, 8) appears.\r<BR>\n" );
document.write( "\n" );
document.write( "We want to find |S \setminus (A₁ ∪ A₂ ∪ A₃ ∪ A₄)|, where S is the set of all permutations.\r<BR>\n" );
document.write( "\n" );
document.write( "**3. Apply Inclusion-Exclusion Principle**\r<BR>\n" );
document.write( "\n" );
document.write( "* |S| = 8!<BR>\n" );
document.write( "* |Aᵢ| = 7! (treat (1, 2), (3, 4), (5, 6), (7, 8) as single units)<BR>\n" );
document.write( "* |Aᵢ ∩ Aⱼ| = 6! (treat two pairs as single units)<BR>\n" );
document.write( "* |Aᵢ ∩ Aⱼ ∩ A_k| = 5! (treat three pairs as single units)<BR>\n" );
document.write( "* |A₁ ∩ A₂ ∩ A₃ ∩ A₄| = 4! (treat all four pairs as single units)\r<BR>\n" );
document.write( "\n" );
document.write( "By the Principle of Inclusion-Exclusion:\r<BR>\n" );
document.write( "\n" );
document.write( "|A₁ ∪ A₂ ∪ A₃ ∪ A₄| = Σ |Aᵢ| - Σ |Aᵢ ∩ Aⱼ| + Σ |Aᵢ ∩ Aⱼ ∩ A_k| - |A₁ ∩ A₂ ∩ A₃ ∩ A₄|\r<BR>\n" );
document.write( "\n" );
document.write( "|A₁ ∪ A₂ ∪ A₃ ∪ A₄| = ⁴C₁ * 7! - ⁴C₂ * 6! + ⁴C₃ * 5! - ⁴C₄ * 4!\r<BR>\n" );
document.write( "\n" );
document.write( "**4. Calculate the Values**\r<BR>\n" );
document.write( "\n" );
document.write( "* 7! = 5040<BR>\n" );
document.write( "* 6! = 720<BR>\n" );
document.write( "* 5! = 120<BR>\n" );
document.write( "* 4! = 24\r<BR>\n" );
document.write( "\n" );
document.write( "|A₁ ∪ A₂ ∪ A₃ ∪ A₄| = 4 * 5040 - 6 * 720 + 4 * 120 - 1 * 24<BR>\n" );
document.write( "|A₁ ∪ A₂ ∪ A₃ ∪ A₄| = 20160 - 4320 + 480 - 24<BR>\n" );
document.write( "|A₁ ∪ A₂ ∪ A₃ ∪ A₄| = 16320 + 456<BR>\n" );
document.write( "|A₁ ∪ A₂ ∪ A₃ ∪ A₄| = 16296\r<BR>\n" );
document.write( "\n" );
document.write( "**5. Find the Desired Number of Permutations**\r<BR>\n" );
document.write( "\n" );
document.write( "* Number of permutations = |S| - |A₁ ∪ A₂ ∪ A₃ ∪ A₄|<BR>\n" );
document.write( "* Number of permutations = 8! - 16296<BR>\n" );
document.write( "* Number of permutations = 40320 - 16296<BR>\n" );
document.write( "* Number of permutations = 24024\r<BR>\n" );
document.write( "\n" );
document.write( "**Therefore, there are 24024 permutations that satisfy the given conditions.**<BR>\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );