# Sitting $(n+1)$ people at $2$ circular tables

In how many ways can one sit $(n+1)$ people at two circular tables so that both tables are occupied by at least one person? Assume that the tables are not distinguishable.

I have attempted to solve this problem but got a wrong answer. Could you help me to notice where my mistake was?
The correct answer: $n! \sum_{k=1}^n \frac{1}{k}$
My solution:
We have $(n+1)$ people. At least one person has to sit at each of them. Therefore:
1. I choose $k$ people to sit at the first table: $\binom{n+1}{k}$.
2. There are a group of $k$ people at the first table and $(n+1 -k)$ people at the second table.
3. The first group can be rearranged in $(k-1)!$ ways.
4. The second group can be rearranged in $(n-k)!$ ways.
Now, I sum up with respect to all possible choices: $$\sum_{k = 1}^{n} \binom{n+1}{k}(k-1)!(n-k)!$$ But this does not simplify to the correct answer. It would work if $\binom{n+1}{k}$ were$\binom{n}{k}$. But how?

• You have assumed that the tables are distinguishable. Since the tables are indistinguishable, you can distinguish them by seating person number 1 at a table and calling it table 1. Then you can continue your calculation. – Isomorphism May 26 '18 at 11:11
• @Isomorphism So, my answer is correct under the assumption that the tables are distinguishable? For example, I sit $\binom{n+1}{k}$ people at the green table and the rest at the blue table? – Aemilius May 26 '18 at 11:15

The answer is $s(n+1,2)$, where $s(n,k)$ is the Stirling number of the first kind.

This Stirling number counts the number of permutations on $n$ letters with $k$ disjoint cycles. Your problem is to decompose a permutation (the people) into two disjoint cycles (to seat them around a table).

The generating function $$x(x-1)(x-2)...(x-n+1) = \displaystyle \sum_{k=1}^{n} s(n,k) x^k,$$ gives the answer for $s(n+1,2)$ as the coefficient of $x^2$. You can compute that: $$n!\displaystyle \sum_{k=1}^{n}\dfrac1{k}.$$

Let $s(n)$ be the number of distinguishable seatings.

Label the people as $1,...,n+1$.

As noted in the comments, your approach assumes the tables are distinguishable.

Here's one way to avoid that . . .

Let $k$ be the total number of people at the same table as person $1$.

Then we have $1 \le k \le n$, hence, using the same reasoning as in your attempt, we get \begin{align*} s(n)&=\sum_{k=1}^{n}{\small{\binom{n}{k-1}}}(k-1)!(n-k)!\\[4pt] &=\sum_{k=1}^{n}\left(\frac{n!}{(k-1)!(n-k+1)!}\right)(k-1)!(n-k)!\\[4pt] &=n!\sum_{k=1}^{n}\frac{1}{n-k+1}\\[4pt] &=n!\sum_{k=1}^{n}\frac{1}{k}\qquad\text{[the same summands, but in reverse order]}\\[4pt] \end{align*}