Each one of 30 people has bought 2 identical presents for the poor (every person's gifts are different from everyone else's). All the gifts were put in a large bag.

In turns, 30 poor people approached the bag and took 2 presents each (the 2 presents were taken simultaneously, not one by one).

In how many ways can they draw gifts so that not one of them had pulled 2 identical gifts?

I was thinking I should take all the ways for withdrawal (60! for the permutations I think) and apply the Inclusion-Exclusion where $Ai$ = poor guy #i pulled 2 identical gifts, $Ai∩Aj$ would be 2 people that drawn identical gifts, etc. But I didn't know how to calculate it..

This question is a part of a Combinatorics 101 practice page, under Inclusion-Exclusion Principle \ Derangements

Thank you.


This problem presents no surprises and we can use ordinary inclusion-exclusion of the set inclusion poset. Suppose we seek the number of configurations where at least $q$ people have received a pair of identical gifts.

First we must choose these $q$ people, which gives $${n\choose q}.$$

View the recipients as a sequence ordered from left to right. Second we must chooose the pairs of identical gifts they receive, which gives

$${n\choose q} \times q!.$$

Finally distribute the remaining gifts any way we like into the left-over slots i.e. recipients, getting

$${2n-2q\choose 2,\ldots,2}.$$

Putting it all together we get the inclusion-exclusion formula

$$S_n = \sum_{q=0}^n {n\choose q}^2 (-1)^q q! \frac{(2n-2q)!}{2^{n-q}}.$$

Starting at $n=1$ we get the sequence

$$0, 4, 48, 1440, 65280, 4348800, 398200320, 48007895040,\ldots$$

Now looking at the value for $n=2$ we see that with this count the gifts a person receives are ordered as opposed to being sets. Note however that we have the count $S_n$ where it is already assured that the gifts everybody received are different. Therefore the orbits of these configurations when ordered pairs are turned into sets all have the same size namely $2^n.$ Therefore with the two gifts being sets we get the formula

$$T_n = \frac{1}{2^n} \sum_{q=0}^n {n\choose q}^2 (-1)^q q! \frac{(2n-2q)!}{2^{n-q}}.$$

Starting at $n = 1$ we obtain the modified sequence

$$0, 1, 6, 90, 2040, 67950, 3110940, 187530840, 14398171200,\ldots$$

Addendum. There is another approach when we are interested in the model where the gifts received form sets with two elements which is to replace the multinomial coefficient with an application of the Polya Enumeration Theorem (PET). In particular we need the cycle index $Z(G_m)$ of the permutation group $G_m$ acting on $2m$ slots where adjacent slots form sets of two elements, e.g. $[1,2]$ is the same as $[2,1].$ This cycle index is

$$Z(G) = \frac{1}{2^m} \sum_{k=0}^m {m\choose k} a_2^k a_1^{2m-2k}.$$

Introducing the quantity

$$F_m = [C_1^2 C_2^2\cdots C_m^2] Z(G_m)(C_1+C_2+\cdots+C_m)$$

we thus obtain

$$T_n = \sum_{q=0}^n {n\choose q}^2 (-1)^q q! F_{n-q}.$$

Starting at $n = 1$ once more we obtain the modified sequence

$$0, 1, 6, 90, 2040, 67950, 3110940, 187530840, 14398171200,\ldots$$


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.