1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.$

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

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}}$$

$\endgroup$
0
$\begingroup$

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!}$

$\endgroup$

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.