[Math] 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

combinatoricscomputer science

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

Best Answer

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.

Related Question