2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ What exactly is your answer to the question $P(X=k)=?$? $\endgroup$
    – drhab
    May 6, 2018 at 11:37
  • $\begingroup$ $P(X=k)=\binom{n-2}{k}*\frac{1}{n!}$ $\endgroup$
    – Stav Alfi
    May 6, 2018 at 12:02

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I'm not looking for any other approaches. The question is: Why am I wrong. $\endgroup$
    – Stav Alfi
    May 6, 2018 at 11:01
  • 1
    $\begingroup$ $\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. $\endgroup$
    – Thehx
    May 6, 2018 at 11:25

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.