1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Newb Nov 27 '13 at 18:02
  • $\begingroup$ But how do I translate that into specific sets that can be used to perform inclusion-exclusion? $\endgroup$ – Billy Thorton Nov 27 '13 at 18:04
  • $\begingroup$ Oh! I misread your question! I thought you wanted to know how to do this without inclusion-exclusion. Sorry. $\endgroup$ – Newb Nov 27 '13 at 18:05
  • $\begingroup$ No problem! That's what makes this problem so difficult! :p $\endgroup$ – Billy Thorton Nov 27 '13 at 18:06
  • $\begingroup$ Your second problem is analogous to this one: math.stackexchange.com/questions/78278/… $\endgroup$ – Newb Nov 27 '13 at 18:06
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ why is there $6*\binom{10}{2,2,2,2,2,2}$ ways for one teacher to choose a pair of twins? $\endgroup$ – Billy Thorton Nov 27 '13 at 18:20
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Nov 27 '13 at 18:23
  • $\begingroup$ So really its $\binom{6}{1} * \binom{10}{2,2,2,2,2}$ ? $\endgroup$ – Billy Thorton Nov 27 '13 at 18:25
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Nov 27 '13 at 18:27
  • $\begingroup$ 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 ? $\endgroup$ – Billy Thorton Nov 27 '13 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.