# Inclusion Exlusion Problems: twins and circular arrangements

I had two combinatorics questions that I was having trouble with using inclusion-exclusion methods to solve them:

1. Given six pairs of non-identical twins, how many ways are there for six teachers to each choose two children with no one getting a pair of twins?
2. How many ways are there to seat n couples around a circular table such that no couple sits next to each other?

I understand how to so this without inclusion-exclusion, but I had no idea how to do using that method. Would someone be able to help me? Thanks in advance, I really appreciate it!

edit: After working on the question some, I came up with something. Would someone check to see if my logic is right?

The universe, the amount of arrangements that can be made with n people around a circular table is (2n-1)! . Therefore, following the inclusion-exclusion principles, $|\cap_{i=1}^n not A_i|$, We can arrange it so each A_i is i couples sitting next to each other. For example:

A_1 = 1 couple sitting next to each other, which is (2n-1)! - 2!

A_2 = 2 couples sitting next to each other, which is (2n-1)! - 4!

...

A_i = i couples sitting next to each other, which is (2n-1)! - 2i!

Is my logic correct? I appreciate all your help! Thanks in advanced!

• For the first, note that the six teachers can choose the first six children arbitrarily. How many ways are there for six teachers to pick 1 child each? Then how many ways are there for each teacher to pick a second, non-twin child? – Newb Nov 27 '13 at 18:02
• But how do I translate that into specific sets that can be used to perform inclusion-exclusion? – Billy Thorton Nov 27 '13 at 18:04
• Oh! I misread your question! I thought you wanted to know how to do this without inclusion-exclusion. Sorry. – Newb Nov 27 '13 at 18:05
• No problem! That's what makes this problem so difficult! :p – Billy Thorton Nov 27 '13 at 18:06
• Your second problem is analogous to this one: math.stackexchange.com/questions/78278/… – Newb Nov 27 '13 at 18:06

In the first problem there are $\binom{12}{2,2,2,2,2,2}$ ways for the teachers to choose $2$ children each without restriction. There are $6\binom{10}{2,2,2,2,2}$ ways for the first teacher to choose a pair of twins and the other five teachers to choose without restriction, and the same goes for each of the other $5$ teachers, so the first correction in the inclusion-exclusion count is

$$\binom{12}{2,2,2,2,2,2}-\binom61\cdot6\binom{10}{2,2,2,2,2}\;.$$

There are $6\cdot5\binom8{2,2,2,2}$ ways for any given pair of teachers to choose a pair of twins each, and there are $\binom62$ pairs of teachers, so the second correction term results in

$$\binom{12}{2,2,2,2,2,2}-\binom61\cdot6\binom{10}{2,2,2,2,2}+\binom62\cdot6\cdot5\binom8{2,2,2,2}\;.$$

I expect that you can probably finish the inclusion-exclusion argument from here.

• why is there $6*\binom{10}{2,2,2,2,2,2}$ ways for one teacher to choose a pair of twins? – Billy Thorton Nov 27 '13 at 18:20
• @Billy: (You have one $2$ too many in the multinomial coefficient.) The teacher can pick any one of the $6$ pairs of twins, and after that the other $5$ teachers are simply selecting $2$ children each from the remaining $10$ children. – Brian M. Scott Nov 27 '13 at 18:23
• So really its $\binom{6}{1} * \binom{10}{2,2,2,2,2}$ ? – Billy Thorton Nov 27 '13 at 18:25
• @Billy: No, because order matters. Look at the next bit, for two teachers picking sets of twins: the first teacher can pick any of the $6$ pairs, and then the second teacher can pick any of the $5$ remaining pairs, so the multiplier is $6\cdot 5$, not $\binom62$. – Brian M. Scott Nov 27 '13 at 18:27
• Sorry, I'm still having trouble getting this straight. So Looking at the second bit; You can choose $\binom{6}{2}$ of the teachers to choose their twin. Once the teachers are chosen, the first teacher can choose one of 6 of the twins, then the fifth teacher can choose on of 5 twins. Then, what's left is the $\binom{8}{2,2,2,2}$ twins to be chosen ? – Billy Thorton Nov 27 '13 at 18:35