Counting set partitions of $\{1,2,...,n\}$ into exactly $k$ non-empty subsets with max size $m$

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

Solution 1:

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).

Solution 2:

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 can obtain the recurrence in Markus Scheuer's answer using elementary counting methods. We use a similar method described here used to obtain a recurrence for the Stirling numbers of the second kind. https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Recurrence_relation)

We want to show that $$a_m(n+1,k)=ka_m(n,k)+a_m(n,k−1)−{n\choose m}a_m(n−m,k−1) \qquad n,k≥1$$

Proof: A partition of $n+1$ objects into $k$ non-empty sets either has the $n+1$th object as a singleton or not. The number of ways that it is a singleton is given by $a_m(n,k-1)$ since this is the number of ways to partition the remaining $n$ objects into $k-1$ sets.

Next we need to count the other case where the $n+1$th object is in one of the $k$ subsets containing the other $n$ objects. This can be done in $ka_m(n,k)$ ways since $a_m(n,k)$ is the number of ways of partitioning $n$ objects into $k$ subjects and there are $k$ choices. However, this also includes cases where we have added the $n+1$th object to a subset with $m$ objects which we don't want to include. So we need to subtract the number of times this happens. This is the number of subsets with exactly $m$ objects in all of the $a_m(n,k)$ partitions of $n$ objects into $k$ subsets with max size $m$. To make a subset of size $m$, we choose $m$ objects from $n$ in ${n\choose m}$ ways. This occurs with multiplicity of the number of ways of putting the remaining $n-m$ objects into $k-1$ subsets (with max size $m$). This is $a_m(n-m,k-1)$ ways.
Putting this together we get the desired result.