# Partition a set of m objects into n subsets of positive size and no two of them should have equal size.

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

• 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? – Henry Nov 25 '15 at 15:55
• 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. – Tatan Nov 25 '15 at 16:07

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