What is the chance that $k$ people will be sitting between 2 specific people?

Question

There are $n$ people that are randomly sitting on a bench in a uniform manner. Amongst those people are Reuben and Shimon. Let $X$ be the number of people between Reuben and Shimon. Compute the distribution of $X$.

I'm trying to understand why my answer is incorrect.

$$ P(X=k)=? $$

1. We choose $\binom{n-2}{k}$ places for the $k$ people between Reuben and Shimon. When I determined a place for the $k$ people, then the places for Reuben and Shimon are determined also and so the $n-k-2$ rest of the people.:

$$ \binom{n-2}{k}* \left(\frac{1}{n}*\frac{1}{n-1}*...*\frac{1}{n-k+1}\right)\left(\frac{1}{n-k}*\frac{1}{n-k-1}\right)\left(\frac{1}{n-k-2}*\frac{1}{n-k-3}*...*1\right) = $$

$$ \binom{n-2}{k}*\frac{1}{n!} $$

I'm not sure that I understand what $ \frac{1}{n} $ means. Does it mean the probability that a specific human from the group of $k$ people will be sitting in a specific place from \binom{n-2}{k} places? Each time in different place?

Answer 1

Your interpretation of $\frac{1}{n}$ within the product $\frac{1}{n}\cdot \frac{1}{n-1}\cdots \frac{1}{2} \cdot \frac{1}{1}$ is correct. Indeed, you can see the product as the probability that a specific person sits at a specific seat, a second specific person sits at another specific seat and so on till there is only one person and one seat left.

Basically, you have modelled all possible arrangements correctly by $n!$.

The problem arises with your expression $\binom{n-2}{k}$. This does not take into account possible arrangements of the $k$ people between R. and S. Besides this, it does not take into account where R. and S. can be placed depending on $k$.

So, I suggest to go back to the point where everything is still correct:

• There are $n!$ arrangements at all.
• The remaining $n-2$ people can always be arranged in $(n-2)!$ ways.
• Wherever R. and S. are placed, they account for $2!$ possible arrangements, as they can flip their position
• We only need to find out in how many ways we can place R. and S. among the possible arrangements of the $n-2$ people depending on $k$.
• For $k=0$ you can place R. and S. together at $n-1$ positions: $$P(X= 0) = \frac{(n-2)!\cdot 2!}{n!}\cdot (n-1)$$
• For $k = n-2$ (the maximum possible number for people in between) you can place R. at the leftmost and S. at the rightmost position of an arrangement or vice versa: $$P(X= n-2) = \frac{(n-2)!\cdot 2!}{n!}\cdot 1$$
• For any $k$ in between you can start placing the first on the leftmost position (position $p=1$). Now, any position $p$ starting from the leftmost position you have for $k$ people in between: $$(p-1)+1+k+1 \leq n$$ (The rightmost position of R. or S. cannot be beyond position $n$)
• So, for $k$ there are only $n-k-1$ possible positions for R. and S.

All together $$P(X = k ) = \frac{(n-2)!\cdot 2!}{n!}\cdot (n-k-1)=\frac{2(n-k-1)}{n(n-1)}$$

Answer 2

There are $n-k-1$ possible seats for Reuben, given Shimon sits k places to the right, multiple that by 2 to cover all cases when Shimon sits before Reuben, no?

$\frac{\binom{n-2}{k}}{n!}$ on its own only denotes exactly how many different (unordered) subsets of power $k$ there are, for a set of power $n$. $n!$ denotes exactly the number of permutations, and will serve as denominator in our answer no matter what.

The answer is wrong because we do not choose $\binom{n-2}{k}$ places for $k$ people: once we picked one place, remaining places are immediately fixed by our problem statement.

Therefore (counting numerator), you first suppose Shimon sits to the left of Reuben (multiplier of $2$ to account for inverse order too), then you choose one place for Shimon ($2(n-k-2)$), which automatically dictates where Reuben is, then you account for all possible permutations of the remaining (n-2) persons ($2(n-k-2)(n-2)!$).

Remembering our denominator, we obtain the answer of $\frac{2(n-k-2)}{n(n-1)}$.

This sits well with the general rough estimation idea that, for any possible seat of Reuben, we can roughly estimate the probability of Shimon sitting in one of two-or-less possible places (sometimes zero) being either $0/n$, $1/n$ or $2/n$ depending on whether there are enough seats to the left and to the right.