Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm familiar with Stirling numbers of the second kind to compute the number of ways to partition a set with $n$ elements into $k$ non-empty, disjoint subsets.

However, there are combinations which I would like to forbid, e.g. any partitions where a subset with 2 elements occur. I thought about using $r$-associated Stirling numbers of the second kind $S_r(n,k)$, i.e. where all subsets have at least $r$ elements, but I cannot catch all cases with this.

So how can one write down a recurrence relation for the number of ways to partition a set with $n$ elements into $k$ subsets, where a subset exists which has $r$ elements? If this result is known, I would be grateful for a link to OESIS or something similar. I feel like it shouldn't be too hard, but I'm really bad with combinatorics.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

The bivariate generating function of the Stirling numbers of the second kind is given by $$G(z,u) = \exp(u(\exp(z)-1))$$ so that $$n! [z^n][u^k] G(z, u) = {n \brace k}.$$ If you want to forbid subsets of $r$ elements, mark them and the generating function becomes $$H(z,u) = \exp\left(uv\frac{z^r}{r!} - u \frac{z^r}{r!} + u(\exp(z)-1)\right) = \exp\left(uv\frac{z^r}{r!} - u \frac{z^r}{r!}\right)G(z,u).$$ This has the property that the coefficient of $[v^0]$ is the generating function of the partitions with sets of size $r$ not allowed, which is $$[v^0] H(z, u) = [v^0] \exp\left(uv\frac{z^r}{r!} \right) \exp\left(-u\frac{z^r}{r!} \right) G(z,u) \\= \exp\left(-u\frac{z^r}{r!} \right) G(z,u) .$$ Now extracting the coefficient of $[z^n]$ from this we find $$n! \sum_{q=0}^{\lfloor n/r\rfloor} \frac{1}{q!} \left(-\frac{u}{r!}\right)^q [z^{n-qr}] G(z, u) .$$ We then obtain for the coefficient of $[u^k]$ the formula $$n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{(-1)^q}{q!\times (r!)^q} [u^{k-q}] [z^{n-qr}] G(z, u) \\= n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{1}{(n-qr)!} \frac{(-1)^q}{q!\times (r!)^q} [u^{k-q}] (n-qr)! [z^{n-qr}] G(z, u) \\ = n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{1}{(n-qr)!} \frac{(-1)^q}{q!\times(r!)^q} {n-qr \brace k-q}.$$ This formula gives the number of set partitions of $n$ elements into $k$ sets with subsets of size $r$ not allowed. Subtract this from ${n\brace k}$ to get the number of partitions where there is at least one subset of $r$ elements.

The OEIS has the case of $k=2$ and $r=1$, the case of $k=3$ and $r=1$ and the case of $k=4$ and $r=1$.

Observation. There is an interesting sanity check here, namely what happens when $r>n$. In this case the formula should produce ordinary Stirling numbers because forbidding subsets of a size larger than the total count of available elements does not affect the statistic. And indeed we have $\lfloor n/r \rfloor = 0$ so that only $q=0$ contributes, giving $$n! \frac{1}{n!} \frac{1}{1\times(r!)^0} {n\brace k} = {n\brace k},$$ so the check goes through and we get the correct value.

share|improve this answer
    
Awesome! I checked the OESIS cases and some other sanity checks and your formula seems correct. I must admid though that I only know of basic techniques for generating functions like addition, multiplication and differentiation. Would be great if you could post some link which explains the 'marking' of the subsets or say some illuminating words towards that. Thanks a lot anyway! –  bijancn Oct 22 '13 at 11:58
    
Thank you for your kind words. These techniques are not difficult and anyone can master them. To get started consult the Wikipedia article on Symbolic Combinatorics. –  Marko Riedel Oct 22 '13 at 21:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.