5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thanks for that. $\endgroup$ – videlity May 30 '17 at 2:05
  • $\begingroup$ I've incorporated the problem setup from the title into the body. Please check to insure against my unintentionally changing your meaning. $\endgroup$ – hardmath May 30 '17 at 2:15
  • $\begingroup$ The exponential generating function is $$\frac1{k!}\left(\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots+\frac{x^m}{m!}\right)^k$$ $\endgroup$ – bof May 30 '17 at 3:34
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thanks a lot for that and the reference to Analytic combinatorics. It helps me understand ways to tackle these problems. In hindsight, given the answer, i think we can use elementary counting methods to obtain that recurrence. We can write $a_m(n+1,k)=[ka_m(n,k)-X]+a_m(n,k−1)$ where X is the number of sets of size exactly $m$ in all $a_m(n,k)$ set partitions. To make a set of size $m$, we choose $m$ elements from $n$ in ${n \choose m}$ ways. This occurs with multiplicity of the ways of putting the remaining $n-m$ points into $k-1$ partitions (with max. size $m$). This is $a_m(n-m,k-1)$ ways. $\endgroup$ – videlity Jun 15 '17 at 4:02
  • $\begingroup$ The -X part is because $ka_m(n,k)$ counts the number of ways of adding the $n+1$th symbol to one of the sets of the partition. But we want to subtract the number where we add the $n+1$th symbol to a set with $m$ elements. $\endgroup$ – videlity Jun 15 '17 at 5:39
  • $\begingroup$ @videlity: You're welcome! Your explanation sounds reasonable. Maybe you might want to add it as an answer by its own. $\endgroup$ – Markus Scheuer Jun 15 '17 at 6:17
1
$\begingroup$

You can try to take first all blocks of size $m$, then the blocks of size $m-1$ and so on. So $$a(n,k,m)=\sum _{i = 0}^{\lfloor n/m \rfloor }\underbrace{\binom{n}{i*m}}_{*_1}\underbrace{\frac{(m*i)!}{m!^ii!}}_{*_2}a(n-m*i,k-i,m-1).$$ Here $*_1$ takes out the elements that are going to be in the blocks of length $m$ and $*_2$ distributes them in the blocks.

This are called Restrained Stirling numbers.

$\endgroup$
0
$\begingroup$

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.

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