# Generalization of a set partitioning problem

Problem: Let $I=\{1,2,\ldots,2n\}$ be a set which is partitioned into $n$ subsets $X_i$, each containing exactly $2$ elements such $\bigcup\limits_{i=1}^n X_i=I$. Prove that the number of ways this can be done is $\dfrac{(2n)!}{2^n\cdot n!}$

Attempted solution:

First, let us consider the problem of partitioning $I$ into $n$ 2-tuples such that every element of $I$ goes into exactly one tuple. We count the number of ways of doing this.

First, we can select the first element of the $n$ 2-tuples by selecting $n$ elements from $I$ (containing $2n$ elements). This can be done in $\dbinom{2n}n$ ways. Now, the second element of the $n$ 2-tuples are taken from the rest of the (already determined) $n$ elements of $I$. This can be done in $n!$ ways, so by the rule of product, there are $\dbinom{2n}n n!$ ways.

Now, consider relaxing the 2-tuples (ordered) to sets with 2 elements (unordered). Since there are $2$ elements, we count each set $2!$ times and by the rule of product, for a configuration of $n$ such sets, we count each configuration $(2!)^n=2^n$ times.

Hence, the number of ways for the original problem is $\dfrac{\dbinom{2n}n n!}{2^n}=\dfrac{(2n)!}{2^n\cdot n!}$

Is my thinking correct?

If yes, can't this argument be generalized for $I=\{1,2,\ldots,kn\}$ where $k$ is a positive integer and we're partitioning $I$ into $n$ subsets $X_i$, each containing exactly $k$ elements?

By an argument analogous to the one above, the number of ways seems to be,

$$\frac{\binom{kn}n\binom{(k-1)n}n\cdots\binom{2n}n n!}{(k!)^n}=\frac{n!\prod\limits_{m=2}^k\binom{mn}n}{(k!)^n}$$

Is my thinking and conclusions correct?

Your thinking is correct. The generalization is not quite good because you have to shuffle every layer of elements you choose, so it would be $$\frac{n!^{k-1}\prod _{m=2}^{k}\binom{mn}{n}}{k!^n}.$$

You can simplify it by expressing each combinatorial number as its factorial description you will end up with $$\frac{(kn)!}{k!^nn!},$$ which has an analogous combinatorial description. Just Shuffle everything and split the string in $k$-blocks then take out order of blocks ($n!$) and take out order of each block $k!^n.$

• Oh crap, forgot about shuffling the subsequent layers like you mentioned! Thanks! – tom_cruise Jun 9 '17 at 6:59

Your question has been answered properly allready and inspired by your interest in generalizations here I only give you one that goes a step further.

How many ways are there to split up in $\sum_{i=1}^kr_i$ subsets of which exactly $r_i$ sets contain exactly $i$ elements for $i=1,\dots,k$?

Evidently the set must have $\sum_{i=1}^kir_i$ elements.

The answer is:$$\frac{(\sum_{i=1}^kir_i)!}{\prod_{i=1}^kr_i!(i!)^{r_i}}$$

Pick the first pair in ${2n\choose2}$ ways, the next pair in ${(2n-2)\choose2}$ ways, the next pair in ${(2n-4)\choose2}$ ways so on until the last pair which is ${2\choose2}$ ways. To remove the order, divide by n! Thus the answer is

$\frac{(2n)!}{2!.(2n-2)!}.\frac{(2n-2)!}{2!(2n-4)!}\cdots \frac{2!}{2!.0!}.\frac{1}{n!}$

After mass cancellation, you get the final answer to be $\frac{(2n)!}{2^n.n!}$

For generatlization, relpace 2 by k in (2n)! and in the denominator replace 2! by k!

Thus you get $\frac{(kn)!}{(k!)^n.n!}$