Number of possibilities for n persons at m tables with at least 5 persons per table

Question

given are n persons and m tables, with $ n \geq 5m $.

How many possibilities are there, to put the persons to the m tables, so that at each table are at least 5 persons? The arrangement of the persons at a table does not matter. Also the tables are not distinguishable.

I thought about the second Stirling number. As it describes the number of possibilities for k not empty sets from n elements, so that every element is in exactly one set. But with this I do not take into account, that I need at least 5 elements in each set.

How can I fix this or is there an approach which fits better to this problem?

Kind regards, Niklas

Answer 1

Let $S_5(n,m)$ be the number of ways for $n$ people to sit at $m$ identical tables, at least five at each.

Suppose that a new person arrives, making it a crowd of $n+1$ people.

• The new person can sit at one of the tables that are already there. They have $m$ choices, so there are $m\cdot S_5(n,m)$ arrangements of this kind, to be included in $S_5(n+1,m)$.

• The new person can pull out a new table (increasing $m$ by one), and get four of the people already present to sit with them. There are $\binom{n}4\cdot S_5(n-4,m)$ arrangements of this kind, to be included in $S_5(n+1,m+1)$.

  • (If the new person recruited more than four people for the new table, then the result would be indistinguishable from a situation included in the first case for $m'=m+1$, in which the new table was already occupied. For that reason, it does not need to be considered separately in the recurrence.)

Thus $$S_5(n+1,m)=m\cdot S_5(n,m)+\tbinom{n}4\cdot S_5(n-4,m-1)$$

(Note that in this formula the final index is $m-1$, as that term represents a move from a situation with $m-1$ tables to one with $m$.)

Start a spreadsheet with $S_5(n,1)=1$ for all $n\ge5$, and $S_5(n,m)=0$ for $n<5m$.

Then $S_5(10,2)=2\cdot0+\tbinom94\cdot1=126$, and the recurrence can be continued:

$$\begin{array}{c|crr}&1&2&3\\\hline 9&1\\10&1&126\\11&1&462\\12&1&1254\\13&1&3003\\14&1&6721\\15&1&14443&126126\\16&1&30251&1009008\\17&1&62322&5309304\\18&1&127024&23075052\end{array}$$

This is OEIS A059024.

Answer 2

You would have to first make valid partitions of $n$ with at least $5$ people at each table. For $m$ = $7$, say, let a valid partition of $n$ be $a,a,b,b,b,c,d,\;with\; a,b,c,d\ge5$

Then the number of ways for this partition = $\dfrac{\binom{2a+3b+c+d}{a,a,b,b,b,c,d}}{2!3!}= \dfrac{\binom{n}{a,a,b,b,b,c,d}}{2!3!}= $$

Work out similarly for all valid partitions, and add up.

Answer 3

Here is an approach 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{1} \end{align*}

We use (1) to derive a generating function for $S_5(n,m)$, the number of ways for $n$ people to sit at $m$ indistinguishable tables, at least five at each.

Generating function: Since the number of people at each table is at least $5$, we set \begin{align*} A=\mathbb{Z}_{\geq 5}\qquad\text{where}\qquad \alpha(z)=\sum_{n\geq 5}\frac{z^n}{n!}=e^z-\sum_{j=0}^4\frac{z^j}{j!} \end{align*} Since the number of tables is $m$, we set \begin{align*} B=\mathbb{Z}_{= 4}=\{4\}\qquad\text{where}\qquad \beta(z)=\frac{z^4}{4!} \end{align*}

We obtain a generating function $\beta(\alpha(z))$ for $S_5(n,m)$ as \begin{align*} \color{blue}{\sum_{n=5m}^\infty S_5(n,m)\frac{z^n}{n!}=\frac{1}{m!}\left(e^z-\sum_{j=0}^4\frac{z^j}{j!}\right)^m}\tag{2} \end{align*}

We can use the generating function (2) to obtain a recurrence relation for $S_5(n,m)$.

Recurrence relation:

We obtain

\begin{align*} \frac{d}{dz}\left(\frac{1}{m!}\left(e^z-\sum_{j=0}^4\frac{z^j}{j!}\right)^m\right) &=\frac{d}{dz}\left(\sum_{n=5m}^\infty S_5(n,m)\frac{z^n}{n!}\right)\\ &=\sum_{n=5m}^\infty S_5(n,m)\frac{z^{n-1}}{(n-1)!}\\ &=\sum_{n=5m-1}^\infty S_5(n+1,m)\frac{z^{n}}{n!}\tag{3}\\ \end{align*}

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

Coefficient comparison of (3) and (4) for $n\geq 5m$ results in \begin{align*} \color{blue}{S_5(n+1,m)=mS_5(n,m)+\binom{n}{4}S_5(n-4,m-1)} \end{align*}