I had two combinatorics questions that I was having trouble with using inclusion-exclusion methods to solve them:
- 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?
- 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!
Best Answer
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.