There were $107$ people at the wedding and $11$ tables, which could accommodate $10$ people each.

Question

There were $107$ people at the wedding and $11$ tables, which could accommodate $10$ people each. This means there were about $11^{107}$ possible seating plans.

I read that in a book but didn't really understand the solution. I mean the solution doesn't consider the fact that each table can have a max of $10$ people and it actually doesn't care about the capacity of the table. Can anyone explain it to me?

Answer 1

The simplest way to read the problem is to consider all the seats distinct, so there are $110$ of them. In that case the first person has $110$ choices of seat, the next has $109$, the next has $108$ and so on. This gives $\frac {110!}{3!}$ possible seating plans. As in my comment, you may want to consider rotating people around a table the same seating plan. Each table has $11$ rotations, so you should divide by $11^{10}$. Maybe you want to consider swapping groups of people among the tables, so the tables are indistinguishable. Then you should divide by $11!$. You need to specify what makes a seating plan unique.

Answer 2

$11^{107} \approx 2.7 \times 10^{111}$ is the number of ways you allocate each person to a table, not a seat. But you could end up with more than $10$ people to a table in that count.

$\frac{110!}{10!^{11}}\approx 1.1 \times 10^{106}$ would be the way of allocating $110$ people to tables with $10$ at each table. But there will be $110-107 =3$ empty spaces, so I think that number is perhaps $\frac{110\times 109 \times 108}{{11 \choose 1} \times 10\times 9 \times 8+{11 \choose 2}{2\choose 1}\times 10^2\times 9 +{11 \choose3}10^3 } \approx 4.76$ times too high so perhaps about $2.3 \times 10^{105}$ is the true figure.

So $11^{107}$ is too big on this basis, perhaps out by a factor of a million, but this is not that dramatic compared with other possible changes to the calculation: you would get a smaller number if individual tables did not matter, dividing by $11!\approx 4 \times 10^7$, while if you wanted to allocate seats as well as tables too you would get Ross Millikan's much higher numbers.

Answer 3

Let $a(n,t)$ be the number of ways to assign $n$ distinguishable people to $t$ indistinguishable tables, each with capacity $c$. Without the capacity, this is a Stirling number of the second kind. By conditioning on the number $k$ of people at the table that contains the first person, we obtain $$a(n,t) = \begin{cases} 1 &\text{if $n = 0$} \\ 0 &\text{if $t = 0$}\\ \sum_{k=1}^{\min(c,n)} \binom{n-1}{k-1} a(n-k,t-1) &\text{otherwise} \end{cases} $$ For $c=10$, we have $a(107,11)=5.8152\times 10^{97}$.

Let $b(n,t)$ be the number of ways to seat $n$ distinguishable people around $t$ indistinguishable tables, each with capacity $c$. Without the capacity, this is a Stirling number of the first kind. By conditioning on the number $k$ of people at the table that contains the first person, we obtain $$b(n,t) = \begin{cases} 1 &\text{if $n = 0$} \\ 0 &\text{if $t = 0$}\\ \sum_{k=1}^{\min(c,n)} (k-1)! \binom{n-1}{k-1} a(n-k,t-1) &\text{otherwise} \end{cases} $$ For $c=10$, we have $b(107,11)=1.2132\times 10^{156}$. If rotations are not equivalent, multiply each summand by $k!$ instead of $(k-1)!$.

For both $a(n,t)$ and $b(n,t)$, if the tables are instead distinguishable, multiply the final results by $t!$.