How many ways can we split a group of $n$ elements into groups of different sizes such that each group contains more than $1$ element

Question

let's assume $p[n]$ is the name of this partitioning method Let's see some examples:

1. $n=3$:

   all possibilities are: $[(3,0),(2,1),(1,1,1)]$

   all cases don't meet the condition $minSize > 1$

   so $p[3]=0$.

2. $n=4$:

   all possibilities are: $[(4,0), (3,1), (2,2), (2,1,1), (1,1,1,1)]$

   only the case $(2,2)$ stands the condition $minSize>1$, now, let's see how many ways can we split 4 into 2 groups of 2 elements $(2,2)=3$

   so $p[4]=(2,2)=3$

3. $n=5$:

   all possibilities are $[(5,0),(4,1),(3,1,1),(3,2),(2,2,1),(2,1,1,1),(1,1,1,1,1)]$

   only the case $(3,2)$ stands the condition $minSize>1$, $(3,2)=10$ (it starts to get harder to compute it with pen!)

   so $p[5]=(3,2)=10$

$p[6]=(4,2)+(3,3)+(2,2,2)=???$

$p[7]=(4,3)+(3,2,2)=???$

$p[8]=(6,2)+(5,3)+(4,4)+(4,2,2)+(3,3,2)+(2,2,2,2)=???$

and it get harder and harder, can you see the logic?

EDIT

My most serious trials so far is to try to customize Stirling numbers of the second kind to solve this problem, but still have a lot of issues in formalizing it, and I am not sure if it is correct to use it, it is just my guess.

P.S: Feel free to add tags to this question, I am not sure how to tag it correctly

Answer 1

If the objects are distinguishable then one expression (hopefully there is a better one or you can simplify this one) is $$p[n]=-1+\sum_{k=0}^{n}(-1)^k \binom n k B_{n-k} $$ for $n\geq 2$ where $B_n$ is the nth Bell number

http://en.wikipedia.org/wiki/Bell_number (You're right in that they are related to the Sterling numbers; sum Sterling numbers up to get the Bell numbers.)

Count by using inclusion-exclusion with the bell numbers: $B_n$ counts the number of ways to partition a set of distinct objects. Subtract off the number of ways to have one object alone: choose the object in $\binom n 1$ ways then partition the remaining ${n-1}$ objects in $B_{n-1}$ ways. But we oversubtracted the partitions that have at least two objects alone so we add back in $\binom n 2 B_{n-2}$, then subtract off the $\binom n 3 B_{n-3}$ partitions with at least three alone, etc. So there are $\sum_{k=0}^n (-1)^k \binom n k B_{n-k}$ ways to partition the set without any element alone. From above it seems you want to also exclude the case where all the elements are left together in a single group, so we subtract 1 to obtain $p[n]$ as the number of ways to partition $n$ distinct objects into at least two sets of more than 1 element. This expression agrees with your initial calculations of $p[3]=0$, $p[4]=3$, $p[5]=10$, $p[6]=40$, $p[8]=161$, $p[9]=714 \ldots$

Answer 2

Here is a proof of the Bell number formula.

Recall the species for set partitions which is $$\mathfrak{P}(\mathcal{U} \mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ which gives the generating function $$G(z, u) = \exp(u(\exp(z)-1)).$$

It follows that the generating function for Bell numbers is $$G(z) = \exp(\exp(z)-1).$$

Observe that in this problem we are excluding sets of size one, which gives the species $$\mathfrak{P}(\mathfrak{P}_{\ge 2}(\mathcal{Z}))$$

which has the generating function $$H(z) = \exp(\exp(z)-1-z) = \exp(-z) \exp(\exp(z)-1) = \exp(-z) G(z).$$

Note that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the exponential generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Therefore $$n! [z^n] H(z) = n! [z^n] \exp(-z) G(z) = \sum_{k=0}^n {n\choose k} (-1)^k B_{n-k},$$ which was to be shown.

We may subtract one from this if the case of all items in a single set is to be excluded.

The sequence $$0, 1, 1, 4, 11, 41, 162, 715, 3425, 17722, \ldots$$ is OEIS A000296.