1
$\begingroup$

Suppose I am given a set of $n$ pairs of items (so I have $2n$ items in the set). I wish to partition the set into 2 disjoint sets such that at least one pair of items has a member in each set. I want to know how many 2-partitions there are of the $2n$ items where the smallest set has $k$ elements.

For example, if I have two pairs of items $\{a_1,a_2,b_1,b_2\}$ I can partition them into the following subsets:

  • $\{a_1,a_2,b_1\}$$\{b_2\}$;
  • $\{a_1,a_2,b_2\}$$\{b_1\}$;
  • $\{a_1,b_1,b_2\}$$\{a_2\}$;
  • $\{a_2,b_1,b_2\}$$\{a_1\}$;
  • $\{a_1,b_1\}$$\{a_2,b_2\}$;
  • $\{a_1,b_2\}$$\{a_2,b_1\}$;

So there are 4 partitions with the smallest set of size 1, and 2 partitions with the smallest set of size 2.

I have exhaustively computed the numbers for 1, 2, and 3 pairs, but I'm looking for a general formula. I know if $k=1$ there are $2n$ partitions, but I haven't found a closed form for a general solution, or even a recursive formula.

edit: I can show that if $k=2$ there are $4n-4$ partitions.

$\endgroup$

1 Answer 1

1
$\begingroup$

First count the total number of partitions where the smallest set has $k$ elements, and then count the bad partitions, in which all pairs are together. Subtract bad from total.

The situation is a little different for $k=n$ than for $k\lt n$. This is because in the case $k=n$ there are $\frac{1}{2}\binom{2n}{n}$ partitions, and for $k\lt n$ there are $\binom{2n}{k}$.

Let us deal with $k\lt n$. If $k$ is odd, there is no bad partition. At least one couple must be separated, else our $k$-set would be made up of couples, so would have an even number of elements.

Now we deal with the case $k$ even, say $k=2l$. To make a bad partition, we choose $l$ couples. This can be done in $\binom{n}{l}$ ways.

A similar calculation takes care of the case $k=n$.

$\endgroup$
2
  • $\begingroup$ Thanks, this was perfect. Just to clarify, for the case where $k=n$, the same rules with whether k is even or odd for $k<n$ apply. If $k$ is even, then there are an odd number of pairs, and any manner of splitting them into two groups will have at least one pair with an element on both sides. $\endgroup$ Jul 18, 2013 at 11:43
  • 1
    $\begingroup$ Yes, analysis is the same, no bads if $n$ odd. If $n$ even, say $2l$, then $\frac{1}{2}\binom{2l}{l}$. So only different thing is the $1/2$ in front of both total and bads. $\endgroup$ Jul 18, 2013 at 11:52

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.