2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why $ (3,2)=10$ and $(2,2)=3$, I don't see the link the second one must be $6$ no? $\endgroup$ – Elaqqad Apr 9 '15 at 2:29
  • $\begingroup$ @Elaqqad: I assume you used $\binom{5}{2}=\binom{5}{3}10$, $\binom{4}{2}=6$, although it works for the $(3,2)$ but if we apply it directly to $(2,2)$ we will get half of the combinations as duplicates! try it with a piece of paper (as I did) it is an easy example and you can notice that right away $\endgroup$ – chouaib Apr 9 '15 at 2:36
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

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