Lesson Upper level combinatorics problems on Inclusion-Exclusion principle
Algebra
->
Permutations
-> Lesson Upper level combinatorics problems on Inclusion-Exclusion principle
Log On
Algebra: Combinatorics and Permutations
Section
Solvers
Solvers
Lessons
Lessons
Answers archive
Answers
Source code of 'Upper level combinatorics problems on Inclusion-Exclusion principle'
This Lesson (Upper level combinatorics problems on Inclusion-Exclusion principle)
was created by by
ikleyn(53107)
:
View Source
,
Show
About ikleyn
:
<H2>Upper level combinatorics problems on Inclusion-Exclusion principle</H2> <H3>Problem 1</H3>In how many ways can we seat 3 pairs of siblings in a row of 10 chairs, so that in each pair the siblings seat together, but different pairs are not next to each other ? <B>Solution</B> The meaning of the problem is that in each pair the siblings seat next to each other, and no two pairs of siblings seat in adjacent chairs. There is /(or there are) the dividing chair/chairs between the pairs. This problem can be solved using Inclusion-Exclusion principle step by step, following this logic. <pre> Let's the pairs of siblings are A=(x,y), B=(u,v), and C=(z,t) (so, A, B and C are their family names). Step 1. Find the number N1 of all placements of siblings, where siblings in pairs are sitting next to each other and there are no other restrictions. Step 2. Find the number N2(A,B) of all possible placements of siblings, where pairs A and B are next to each other, without restrictions on placing pair C(z,t). -then the number N2(A,C) of all possible placements of siblings, where pairs A and C are next to each other; without restrictions on placing B(u,v). -then the number N2(B,C) of all possible placements of siblings, where pairs B and C are next to each other. without restrictions on placing A(x,y). It is obvious that due to the symmetry, N2(A,B) = N2(A,C) = N2(B,C). Step 3. Find the number N3 of all possible placements of pairs of siblings as one block, where pairs A, B and C are next to each other, in any order. Then the answer to the problem's question, due to Inclusion-Exclusion, is N1 - (N2(A,B) + N2(A,C) + N2(B,C) + N3. As the program/(the idea) is formulated so clear, we can start implementing it. <U>S T E P 1</U> We have 3 pairs of siblings A, B, and C; each pair occupies 2 next chairs. In addition, we have 4 vacant indistinguishable chairs. Thus we have 3 + 4 = 7 items (pairs and vacant chairs). For these items, the number of arrangements is {{{7!/4!}}} = 7*6*5 = 210. In addition, there are 2 permutations inside each pair. It gives, in total 210*8 = 1680 different possible distinguishable arrangement in this configuration. Step 1 is complete. <U>S T E P 2</U> We want to find the number N2(A,B) of all possible placements of siblings, where pairs A and B are next to each other, without restrictions on placing pair C(z,t). Two pairs (A,B) form the block of 4 chairs. So, now we have this block of 4 chairs, the block of 2 chairs for pair C and 4 vacant chairs: in all, 1 + 1 + 4 = 6 items. We can arrange these 6 items in {{{6!/4!}}} = 6*5 = 30 different distinguishable ways. In addition, we have 2 permutations inside each pair A, B and C, and we can permute A and B in the block (A,B). It gives us the number of all possible arrangements N2(A,B) = {{{2^4*30}}} = 16*30 = 480. Due to the symmetry, N2(A,B) = N2(A,C) = N2(B,C) = 480. Step 2 is complete. <U>S T E P 3</U> We want to find the number N3 of all possible placements of pairs of siblings as one block, where pairs A, B and C are next to each other, in any order. This big block occupies 6 chairs, and 4 chairs remain vacant. Thus, this time there are 1 + 4 = 5 items, so the number of ways to arrange them is {{{5!/4!}}} = 5. In addition, we have 3! = 6 permutations of pairs A, B, C in the block, and 2 permutations inside each pair. It gives the number N3(A,B,C) = {{{5*6*2^3}}} = 30*8 = 240. Step 3 is complete. Now we have everything to compute the final answer. It is, according to the Inclusion-Exclusion principle, N1 - (N2(A,B) + N2(A,C) + N2(B,C) + N3 = 1680 - (480 + 480 + 480) + 240 = 480. <U>ANSWER</U>. There are 480 different ways to arrange 3 pairs of siblings in a row of 10 chairs such that nobody sits next to their sibling. </pre> It can be easy generalized to a greater number of chairs and a greater number of pairs of siblings. The same logic and the same technique work. <H3>Problem 2</H3>In how many ways can we seat 3 pairs of siblings in a row of 10 chairs, so that nobody sits next to their sibling ? (Four chairs will be left empty, of course.) <B>Solution</B> The meaning of the problem is that for each pair of siblings, the paired siblings do not seat in adjacent chairs. This problem can be solved using Inclusion-Exclusion principle step by step, following this logic. <pre> Let's the pairs of siblings be A=(x,y), B=(u,v), and C=(z,t) (so, A, B and C are their family names). Step 1. First, we consider all possible different placements of 6 persons (three pairs of siblings) in 10 chairs without any constraints. The number of these placements is 10*9*8*7*6*5 = 151200, so we consider the list of all such 151200 placements. Step 2. From this list, we cross out all arrangements, where (x,y) are next to each other. We consider the pair (x,y) as one unit; so, we have this unit and 4 other persons to arrange them in 9 places. It can be done by N1 = 9*(8*7*6*5) different ways. It means that for (x,y) we cross out N1 =(9)*(8*7*6*5) = 15120 records from the list of all 151200 placements. We do the same for the pairs (y,x), (u,v), (v,u), (z,t) and (t,z). Thus, doing this way, we cross out, in all, 6*N1 similar records from the list . After this step, we have 151200-6*N1 = 151200 - 6*15120 = 60480 records in the list. Again, for now, there are 60480 records in our list. Step 3. But doing it, we cross out some records several times. We cross out several time the records, where we find - the pair (x,y) sitting together and the pair (u,v) sitting together; - the pair (x,y) sitting together and the pair (z,t) sitting together; - the pair (u,v) sitting together and the pair (z,t) sitting together. - the pair (y,x) sitting together and the pair (u,v) sitting together; - the pair (y,x) sitting together and the pair (z,t) sitting together; - the pair (v,u) sitting together and the pair (z,t) sitting together. - the pair (x,y) sitting together and the pair (v,u) sitting together; - the pair (x,y) sitting together and the pair (t,z) sitting together; - the pair (u,v) sitting together and the pair (z,t) sitting together. - the pair (y,x) sitting together and the pair (v,u) sitting together; - the pair (y,x) sitting together and the pair (t,z) sitting together; - the pair (v,u) sitting together and the pair (t,z) sitting together. So, we want to know the number of such records what we crossed out several times to compensate them in the future. Therefore, we make Step 4. Let's determine the number N2 of all possible placements of pair A and B, where siblings (x,y) seat next to each other, and siblings (u,v) seat next to each other, without other restrictions. For it, we consider the pair (x,y) as one unit and consider the pair (u,v) as the other unit. so, we have these two units and 2 other persons to arrange them in (10-1-1) = 8 places. It can be done by N2= (8*7)*(6*5) = 1680 different ways. It means that in the step 3 we crossed out N2 = (8*7)*(6*5) = 1680 records 12 times from the list of all 151200 placements. So, to compensate multiply crossing, we should restore 12*N2 = 12*1680 = 20160 records in the list of placements. Thus, for now, the list of records will contain 60480 + 20160 = 80640 records. Step 5. But again, doing this way, we restore some records in the list several times. Namely, we restore several times the records, where siblings (x,y) seat together, as well as siblings (u,v) seat together and siblings (z,t) seat together. Let's calculate, in how many cases N2 siblings (x,y) seat together, as well as siblings (u,v)seat together and siblings (z,t) seat together in 10 chairs in the row. So, we consider three pairs A = (x,y), B = (u,v) and C = (z,t) as three units, and we can place them in (10-3) = 7 positions. It can be done in N2 = 7*6*5 = 210 different ways. In these records, there are 2 possible permutations of siblings inside each pair. So, the total number of these repeating restoring is {{{2^3*N2}}} = 8*N2 = 8*(7*6*5) = 8*210 = 1680. Hence, to keep the balance, we should subtract 1680 from 80640. Step 6. Thus, the final number of arranging/placing of three pairs of siblings in accordance with the problem is 80640 - 1680 = 78960. At this point, the problem is solved completely. <U>ANSWER</U>. There are 78960 different ways to arrange 3 pairs of siblings in a row of 10 chairs such that, in paired siblings, nobody sits next to their sibling. </pre> My other additional lessons on Combinatorics problems in this site are - <A HREF=https://www.algebra.com/algebra/homework/Permutations/Upper-league-combinatorics-problem.lesson>Upper league combinatorics problem</A> - <A HREF=https://www.algebra.com/algebra/homework/Permutations/An-upper-level-problem-on-a-party-of-people-sitting-at-a-round-table.lesson>Upper level problems on a party of people sitting at a round table</A> - <A HREF=https://www.algebra.com/algebra/homework/Permutations/Upper-level-combinatorics-problem-on-subsets-of-a-finite-set.lesson>Upper level combinatorics problem on subsets of a finite set</A> - <A HREF=https://www.algebra.com/algebra/homework/Permutations/A-confusing-combinatorics-problem-on-repeating-digits.lesson>A confusing combinatorics problem on repeating digits in numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/Permutations/This-nice-problem-teaches-to-distinguish-permutations-from-combinations.lesson>This nice problem teaches to distinguish permutations from combinations</A> - <A HREF=https://www.algebra.com/algebra/homework/Permutations/OVERVIEW-of-additional-combinatorics-problems.lesson>OVERVIEW of additional combinatorics problems</A> Use this file/link <A HREF=https://www.algebra.com/algebra/homework/complex/ALGEBRA-II-YOUR-ONLINE-TEXTBOOK.lesson>ALGEBRA-II - YOUR ONLINE TEXTBOOK</A> to navigate over all topics and lessons of the online textbook ALGEBRA-II.
