3
$\begingroup$

How many ways are there to divide N elements into K sets where each set has exactly N/K elements.

For the example of 6 elements into 3 sets each with 2 elements. I started by selecting the elements that would go in the first set (6 choose 2) and then those that would go into the second as (4 choose 2) and then the 2 remaining elements into the third set. This gives, (6 choose 2) * (4 choose 2). In general

(N choose N/K) * (N-(N/K) choose N/K) * (N-(2*N/K) choose N/K) * ... * 1
$\endgroup$
  • 3
    $\begingroup$ Any thoughts on the problem? You aren't a new user here. You should know that questions on this site require at least some input on your efforts towards the problem. Otherwise you are destined for downvotes or being placed on hold $\endgroup$ – jameselmore Mar 12 '15 at 21:10
  • $\begingroup$ Added. I'm concerned that I'm assuming some kind of ordering. @jameselmore $\endgroup$ – nickponline Mar 12 '15 at 21:16
1
$\begingroup$

Your approach, as noted by Ross Millikan's answer, is effective. Another way to approach such a problem would be to consider "interpreting" a permutation as such a partition - like, if we wrote the elements in the order: $$eabcfd$$ we might just group them into pairs as $\{\{e,a\},\{b,c\},\{f,d\}\}$ - where we just "fill" the expression $\{\{\_,\_\},\{\_,\_\},\{\_,\_\}\}$ by drawing from the order in which we wrote the elements.

However, $eabcfd$ and $aebcfd$ represent the same partition, as the pairs are unordered - and $bceaf\!\,\!d$ also represents the same partition, as the order of the pairs does not matter. Proceeding thusly, we can see that we can reorder within each of the $K$ sets in $(N/K)!$ ways without affecting the partition, and we can reorder the order in which the sets appear in the partition in $K!$ ways - and that, these are the only transformations which do not affect the partition. Thus, dividing the number of permutations of the elements by the number of permutations representing any given partition yields that there are $$\frac{N!}{(N/K)!^k K!}$$ such partitions.

(This can also be found by expanding ${a \choose b}=\frac{a!}{b!(a-b)!}$ and looking at cancellations in your expression)

$\endgroup$
  • $\begingroup$ Thanks! Is there a way to generalize this such that: if I make D draws with replacement from N distinct items. how many ways are there to get C copies of any K distinct items. I tried to generalize with your analogy of "filling" in the bracket. But for D > C*K it's unclear how to no double count groups. $\endgroup$ – nickponline Mar 20 '15 at 16:26
4
$\begingroup$

Hint: You are close. As the sets are unlabeled, choosing $\{a,b\},\{c,d\},\{e,f\}$ is the same as choosing $\{e,f\},\{c,d\},\{a,b\}$, but you have counted them both.

$\endgroup$
  • $\begingroup$ Ah, so I should divide by the number of ways of ordering the sets = K! $\endgroup$ – nickponline Mar 12 '15 at 21:20
  • $\begingroup$ Awesome :), is there a more compact formula that avoids the product? $\endgroup$ – nickponline Mar 12 '15 at 21:24
  • $\begingroup$ If you look at the factorial expression for the binomial coefficients, there is a lot of cancellation. Let $M=\frac NK$ Your first two terms are $\frac {N!}{(N-M)!M!}\cdot \frac {(N-M)!}{(N-2M)!M!}$ and you can see the cancellation. You wind up with $\frac {N!}{(M!)^KK!}$ There is a nice combinatorial interpretation. There are $N!$ ways to put the elements in order. Reordering elements within a group can be done in $M!$ ways and you have $K$ of those. The last $K!$ is the ordering of the groups. $\endgroup$ – Ross Millikan Mar 12 '15 at 21:54
0
$\begingroup$

In response to your comment on Ross's answer, there is a more compact form: $$ \text{number of partitions }=P_{n,k}=\frac{n!}{(n/k)!^{k}k!} $$ To prove this, we instead prove $$ n!=P_{n,k}\cdot (n/k)!^k\cdot k! $$ To prove that, ask how many ways are there permute $n$ elements? There are certainly $n!$ such ways. But another to form a permutations is this: first, divide the $n$ elements into $k$ equal sets $(P_{n,k}$ ways to do this). Then, permute each element within each of the sets (they all have size $n/k$, and there are $k$ of them, so there are $(n/k)!^k$ ways. Finally, put the $k$ sets themselves into some order $(k!$ ways).

You can check that $P_{6,3}=\frac{6!}{2!^3\cdot3!}=15$, and that indeed there are $5$ choices for what the set containing $1$ is, and then $\binom{4}2=3$ ways to partition the remaining 4 elements into sets.

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