3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Isomorphism May 26 '18 at 11:11
  • $\begingroup$ @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? $\endgroup$ – Aemilius May 26 '18 at 11:15
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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*}

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