Lesson Upper level combinatorics problems on Inclusion-Exclusion principle

Upper level combinatorics problems on Inclusion-Exclusion principle

Problem 1

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.



                           S T E P   1


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*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.

     

                           S T E P   2


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*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) =   = 16*30 = 480.


Due to the symmetry,  N2(A,B) = N2(A,C) = N2(B,C) = 480.   Step 2 is complete.



                           S T E P   3


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.

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) =  = 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.


ANSWER.  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.

Problem 2

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   = 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.


ANSWER.  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.