Seating $m$ people in $m^2$ chairs at a round table

Question

I am having difficulty with the following counting problem.

Suppose there are $m^2$ indistinguishable chairs at a round table. There are $m$ people to be seated. Each arrangement is equally likely. Let $X_m$ denote the number of pairs of people sitting adjacent to one another (i.e., no seats between them). Compute the following limits: $$\lim_{m\rightarrow\infty}E[X_m], \qquad \lim_{m\rightarrow\infty}\operatorname{Var}(X_m).$$

The total number of arrangements can be reasoned out to be $$(m-1)!\binom{m^2-1}{m-1} = \frac{(m^2-1)!}{(m^2-m)!}.$$ However, I am not sure how to count the number of ways that $X_m = 0,1,\cdots,\dfrac{m}{2}$. Doing this for $m = 1$ and $m = 2$ are pretty simple, i.e. $$P(X_1 = 0) = 1, \qquad E[X_1] = 0.\\ P(X_2 = k) = \begin{cases}\dfrac{1}{3}; & k = 0 \\ \dfrac{2}{3}; & k = 1\end{cases}, \qquad E[X_2] = \frac{2}{3}.$$

EDIT: Could I possibly conjecture that $E[X_m] = \dfrac{m}{m+1}$?

Answer 1

First, it makes no difference whether the chairs are distinguishable or not because each configuration in the scenario of indistinguishable chairs corresponds to exactly $m^2$ configurations in the distinguishable scenario (Note that there are $m^2$ cyclic permutations from $\{1, \cdots, m^2\}$ to itself). Thus in the derivation below, chairs are clockwise numbered as $C_1, \cdots, C_{m^2}$, and $C_{m^2 + 1} := C_1$.

Now for $1 \leqslant k \leqslant m^2$, define$$ Y_k = \begin{cases} 1; & \text{both } C_k \text{ and } C_{k + 1} \text{ are occupied}\\ 0; & \text{otherwise} \end{cases}. $$ Note that $X = \sum\limits_{k = 1}^{m^2} Y_k$. For any $a \geqslant b \geqslant 0$, denote $P(a, b) = \dfrac{a!}{(a - b)!}$. For $1 \leqslant k \leqslant m^2$,$$ P(Y_k = 1) = \frac{P(m, 2) P(m^2 - 2, m - 2)}{P(m^2, m)} = \frac{1}{m(m + 1)}. $$

For $1 \leqslant j < k \leqslant m^2$, if $k = j + 1$ or $(j, k) = (1, m^2)$, then$$ P(Y_j = Y_k = 1) = \frac{P(m, 3) P(m^2 - 3, m - 3)}{P(m^2, m)} = \frac{m - 2}{m(m + 1)(m^2 - 2)}. $$ Otherwise,$$ P(Y_j = Y_k = 1) = \frac{P(m, 4) P(m^2 - 4, m - 4)}{P(m^2, m)} = \frac{(m - 2)(m - 3)}{m(m + 1)(m^2 - 2)(m^2 - 3)}. $$ Therefore,$$ E(X) = \sum_{k = 1}^{m^2} E(Y_k) = \sum_{k = 1}^{m^2} P(Y_k = 1) = \frac{m}{m + 1}, $$\begin{align*} E(X^2) &= E\left( \sum_{k = 1}^{m^2} Y_k^2 + 2 \sum_{1 \leqslant j < k \leqslant m^2} Y_j Y_k \right) = \sum_{k = 1}^{m^2} E(Y_k^2) + 2 \sum_{1 \leqslant j < k \leqslant m^2} E(Y_j Y_k)\\ &= \sum_{k = 1}^{m^2} P(Y_k = 1) + 2 \sum_{1 \leqslant j < k \leqslant m^2} P(Y_j = Y_k = 1)\\ &= \frac{1}{m(m + 1)} · m^2 + 2 \Biggl( \frac{m - 2}{m(m + 1)(m^2 - 2)} · m^2\\ &\quad + \frac{(m - 2)(m - 3)}{m(m + 1)(m^2 - 2)(m^2 - 3)} · \left( \frac{1}{2} m^2 (m^2 - 1) - m^2 \right) \Biggr)\\ &= \frac{m^2 (2m - 3)}{(m + 1)(m^2 - 2)}, \end{align*}$$ D(X) = E(X^2) - (E(X))^2 = \frac{m^2 (m^2 - m - 1)}{(m + 1)^2 (m^2 - 2)}, $$ and$$ \lim_{m → ∞} E(X) = 1, \quad \lim_{m → ∞} D(X) = 1. $$

Answer 2

For any $m$ and $i,j\in\{1,\dots,m\}$ Let: $$U_{m,i,j}=\begin{cases}1&i\neq j\text{ and }i\text{ is to the immediate left of }j\\ 0&\text{otherwise}\end{cases}$$

Then $X_m=\sum_{i,j} U_{m,i,j}.$

And hence:

$$E(X_m)=\sum_{i,j} E(U_{m,i,j})=m(m-1)E(U_{m,1,2})$$

Since $U_{m,i,j}$ has the same expected value for each pair $i\neq j$ and is $0$ when $i=j.$

Mow, $E(U_{m,1,2})$ is just the probability that person $1$ is exactly one to the left of person $2.$

Now, the rest depends on the meaning of your question, as outlined in the comments.

With the absolute simplest interpretation, $E(U_{m,1,2})=\frac{m^2}{m^2(m^2-1)}=\frac{1}{m^2-1}$ and hence $E(X_m)=\frac{m}{m+1}.$

---

The harder case might not actually be harder.

Every seating arrangement is equivalent to exactly one arrangement where the first person is put into a specific seat, which we'll label seat 0. Then the odds that the next seat, seat $1$, is taken is taken is $\frac{\binom{m^2-2}{m-2}}{\binom{m^2-1}{m-1}}=\frac{m-1}{m^2-1}=\frac{1}{m+1}.$ So it stills seems like the expected number of people with someone precisely to their right is still $\frac{m}{m+1}.$

I'll try to check this when $m=4,$ but it is a lot of work.

---

The variance is harder. Will think about it.