Combinatorics – Counting Set Partitions into k Non-Empty Subsets with Max Size m

combinatoricspermutationsstirling-numbers

Let $a(n,k,m)$ denote the number of set partitions of $\{1,2,…,n\}$ into exactly $k$ non-empty subsets with max size $m$. Thus all subsets have number of elements $\leq m$. (Here size $m$ doesn't have to be attained by a subset, but if it makes the question easier, then that's fine).

The number with no restriction on part sizes is given by the Stirling number of the second kind $S(n,k)$.

I tried to construct a recurrence to the Stirling numbers but couldn't work in the constraint of the maximal size.

$$a(n+1,k,m) = a(n,k-1,m) + k. a(n,k,m-1) + ?? $$
or
$$a(n+1,k,m) = a(n,k-1,m) + k. a(n,k,m) – ?? $$
with initial conditions $a(n,n,m) = 1, a(1,1,m)=1$ for $m\geq 1$ and $a(n,k,m) = 0$ for $m<n/k$.

Best Answer

Let $a_m(n,k)$ be the number of set partitions of $n$ elements into $k$ non-empty partitions with maximum size $m$ each. We show the following is valid for $m\geq 1$: \begin{align*} \color{blue}{a_m(n+1,k)}&\color{blue}{=ka_m(n,k)+a(n,k-1)-\binom{n}{m}a(n-m,k-1)\qquad n,k\geq 1}\tag{1} \end{align*} with boundary conditions \begin{align*} \color{blue}{a_m(n,k)}&\color{blue}{=a_m(n,k)=0\, \qquad\qquad n<k,n>km}\\ \color{blue}{a_m(n,n)}&\color{blue}{=1\, \qquad\qquad\qquad\qquad\quad n\geq 0}\\ \color{blue}{a_m(n,1)}&\color{blue}{=} \color{blue}{\begin{cases} 1&\qquad\qquad\qquad\quad 1\leq n\leq m\\ 0&\qquad\qquad\qquad\quad n>m \end{cases}}\\ \color{blue}{a_m(0,k)}&\color{blue}{=a_m(n,0)=0\qquad\qquad\ \, n,k>0}\\ \end{align*}

This approach is based upon generating functions. The following can be found in section II.3.1 in Analytic combinatorics by P. Flajolet and R. Sedgewick:

The class $S^{(A,B)}$ of set partitions with block sizes in $A\subseteq \mathbb{Z}_{\geq 1}$ and with a number of blocks that belongs to $B$ has exponential generating function

\begin{align*} S^{(A,B)}(z)=\beta(\alpha(z))\qquad\text{where}\qquad \alpha(z)=\sum_{a\in A}\frac{z^a}{a!},\quad \beta(z)=\sum_{b\in B}\frac{z^b}{b!}\tag{2} \end{align*}

At first we determine a generating function for $a_m(n,k)$.

Generating function: In the current situation we are looking for partitions with maximum size $m$. We set \begin{align*} A=\{1,2,\ldots,m\}\qquad\text{where}\qquad\alpha(z)=\sum_{j=1}^m\frac{z^j}{j!} \end{align*} accordingly. Since the number of partitions is $k$ we have \begin{align*} B=\{k\}\qquad\text{where}\qquad \beta(z)=\frac{z^k}{k!} \end{align*}

The resulting generating function is according to (2) \begin{align*} \beta(\alpha(z))=\frac{1}{k!}\left(\sum_{j=1}^m\frac{z^j}{j!}\right)^k=\sum_{n=k}^{km}a_m(n,k)\frac{z^n}{n!}\tag{3} \end{align*}

We can use the generating function (3) to obtain a recurrence relation for $a_m(n,k)$.

Recurrence relation:

We obtain

\begin{align*} \frac{d}{dz}\sum_{n=k}^{km}a_m(n,k)\frac{z^n}{n!}&=\sum_{n=k}^{km}a_m(n,k)\frac{z^{n-1}}{(n-1)!} =\sum_{n=k-1}^{km-1}a_m(n+1,k)\frac{z^n}{n!}\tag{4} \end{align*}

On the other hand we obtain \begin{align*} \frac{d}{dz}&\left(\frac{1}{k!}\left(\sum_{j=1}^m\frac{z^j}{j!}\right)^k\right)\\ &=\frac{1}{(k-1)!}\left(\sum_{j=1}^m\frac{z^j}{j!}\right)^{k-1}\sum_{j=1}^m\frac{z^{j-1}}{(j-1)!}\\ &=\frac{1}{(k-1)!}\left(\sum_{j=1}^m\frac{z^j}{j!}\right)^{k-1}\sum_{j=0}^m\frac{z^{j}}{j!}\\ &=\frac{1}{(k-1)!}\left(\sum_{j=1}^m\frac{z^j}{j!}\right)^{k-1}\left(\sum_{j=1}^m\frac{z^{j}}{j!}+1-\frac{z^m}{m!}\right)\\ &=\frac{1}{(k-1)!}\left(\sum_{j=1}^m\frac{z^j}{j!}\right)^k+\frac{1}{(k-1)!}\left(\sum_{j=1}^m\frac{z^j}{j!}\right)^{k-1}\\ &\qquad-\frac{z^m}{m!}\cdot\frac{1}{(k-1)!}\left(\sum_{j=1}^m\frac{z^j}{j!}\right)^{k-1}\\ &=k\sum_{n=k}^{km}a_m(n,k)\frac{z^n}{n!}+\sum_{n=k-1}^{(k-1)m}a_m(n,k-1)\frac{z^n}{n!} -\frac{z^m}{m!}\sum_{n=k-1}^{(k-1)m}a_m(n,k-1)\frac{z^n}{n!}\tag{5} \end{align*}

The right-most series in (5) is \begin{align*} \frac{1}{m!}\sum_{n=k-1}^{(k-1)m}a_m(n,k-1)\frac{z^{n+m}}{n!} &=\frac{1}{m!}\sum_{n=k+m-1}^{km}a_m(n-m,k-1)\frac{z^{n}}{(n-m)!}\\ &=\binom{n}{m}\sum_{n=k+m-1}^{km}a_m(n-m,k-1)\frac{z^{n}}{n!}\\ \end{align*}

We conclude from (4) and (5) \begin{align*} \sum_{n=k-1}^{km-1}a_m(n+1,k)\frac{z^n}{n!} &=k\sum_{n=k}^{km}a_m(n,k)\frac{z^n}{n!}+\sum_{n=k-1}^{(k-1)m}a_m(n,k-1)\frac{z^n}{n!}\\ &\qquad -\binom{n}{m}\sum_{n=k+m-1}^{km}a_m(n-m,k-1)\frac{z^{n}}{n!}\tag{6} \end{align*}

Coefficient comparison of (6) for $k\leq n\leq km$ results in \begin{align*} \color{blue}{a_m(n+1,k)=ka_m(n,k)+a_m(n,k-1)-\binom{n}{m}a_m(n-m,k-1)} \end{align*} and the claim follows when also respecting the boundary conditions stated in (1).

Related Question