For example: [1,2,3,4] and k=3 parts should yield
[1],[2],[3,4]
[1],[3],[2,4]
[1],[4],[2,3]
[2],[3],[1,4]
[2],[4],[1,3]
[3],[4],[1,2]
as an output.
For k=2 with the same set we would get
[1],[2,3,4]
[2],[1,3,4]
[3],[1,2,4]
[4],[1,2,3]
[1,2],[3,4]
[1,3],[2,4]
[1,4],[2,3]
instead.
Can anyone give me some advice here? Thanks a lot.
On
I will solve problem for $n=4$ special case. I hope that you can find the solution method for bigger values of $n$.
For $k=1$, there is only $1$ partition: $[1234]$
For $k=2$, there are two groups that $[ab],[cd]$ and $[a],[bcd]$. In the case $[ab],[cd]$: $\dbinom{4}{2} \cdot \dbinom{2}{1}$. But $[ab],[cd]$ and $[cd],[ab]$ are identical. So we have to divide by $2!$, hence $\dfrac{1}{2!}\dbinom{4}{2}=3$. Now in the case $[a],[bcd]$: $\dbinom{4}{1} \cdot \dbinom{3}{3}=4$. Sum of these $3 + 4 = 7$
For $k=3$, there are $[a],[b],[cd]$ partitions. Therefore $\dbinom{4}{1} \cdot \dbinom{3}{1} \cdot \dbinom{2}{2}$. But $[a],[b],[cd]$ and $[b],[a],[cd]$ gives identical partitions. Thus we have to divide by $2!$ and hence $\dfrac{1}{2!}\dbinom{4}{1} \cdot \dbinom{3}{1}=6$.
For $k=4$, there are $[a],[b],[c],[d]$ partitions. We get $\dbinom{4}{1} \cdot \dbinom{3}{1}\cdot \dbinom{2}{1} \cdot \dbinom{1}{1}$. But permutating of $[a],[b],[c],[d]$ are identical. Thus we have to divide by $4!$ and we find $ \dfrac{1}{4!}\dbinom{4}{1} \cdot \dbinom{3}{1}\cdot \dbinom{2}{1}=1$.
Note: Number of total partitions is $1+7+6+1=15$.
Stirling numbers of second kind: $S(n,k)$ is the number of partitions of an $n$-element set into $k$ nonempty pairwise disjoint subsets. There is a recursion for computing these numbers: $S(n,1)=1=S(n,n)$ and $S(n,k+1) = k\cdot S(n,k) + S(n,k-1)$.