2
$\begingroup$

In how many ways can I partition a set of size m into n subsets such that each of them must have atleast one element and no two of them should have same no. of elements. ?

$\endgroup$
  • $\begingroup$ If you start with $m=3$, e.g. $\{A,B,C\}$, and $n=2$, do $\{\{A,B\},\{C\}\}$ and $\{\{C,B\},\{A\}\}$ count as different partitions? $\endgroup$ – Henry Nov 25 '15 at 15:55
  • $\begingroup$ Nopes. If a partition contains two subsets of cardinality 1 & 2 and another partition contains two subsets of cardinality 1 & 2 then they are same. $\endgroup$ – Tatan Nov 25 '15 at 16:07
1
$\begingroup$

I had a Java applet which calculated these sorts of things at http://www.se16.info/js/partitions.htm though with worries about Java security, most modern browsers will not allow you to use it. The source code is linked there too.

You can calculate the answer with a simple recurrence, since you can construct a partition of $m$ with $n$ distinct positive parts:

  • either by taking a partition of $m-n$ with $n$ distinct positive parts and adding $1$ to each part
  • or by taking a partition of $m-n$ with $n-1$ distinct positive parts, adding $1$ to each part, and then adding a part of size $1$

so the solution satisfies $$f(m,n) = f(m-n,n-1) + f(m-n,n)$$ starting from $f(0, 0)=1$, $f(m,0)=0$ if $m \gt 0$, and $f(m,n)=0$ if $m \lt 0$.

Another approach can be derived from considering the number of ways of partitioning the positive integer $m$ into $n$ distinct positive integers is the same as the number of ways of partitioning $m- \frac{n(n+1)}{2}$ into up to $n$ positive integers (not necessarily distinct), which is also the number of ways of partitioning $m- \frac{n(n+1)}{2}$ into positive integers where the largest is no greater than $n$. As an example, $7$ can be partitioned into $2$ distinct positive parts in three ways: $$7 = 4+3 = 5+2=6+1$$ corresponding to $7-\frac{2\times (2+1)}{2}=4$ being partitioned into up to $2$ positive integers in three ways: $$4 = 2+2 = 3+1 = 4 (+0)$$ and corresponding to $4$ being partitioned into positive integers each no more than $2$ in three ways: $$4=2+2 = 2+1+1 = 1+1+1+1.$$

OEIS A060016 and A008289 have more details.

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