2
$\begingroup$

Number of ways $k$ persons can be selected from $n$ persons sitting around a round table, where no two adjacent persons can be selected, is

$\dbinom{n-k+1}{k}-\dbinom{n-k-1}{k-2}$

Can anyone help me to understand how this formula is derived?

After going through many problems in this site, the explanation for the first term I understand is given below.

Suppose $n$ persons are in a row. Then there are $n-k$ persons left after the selection which gives $(n-k+1)$ spaces. Choosing $k$ spaces from these gives $\dbinom{n-k+1}{k}$

However, I myself is not able to clearly understand this. I find it difficult to understand the second term as well. Please help.

Note: This is needed for me to understand @Aryabhata's explanation

$\endgroup$
  • $\begingroup$ By nearby, do you mean adjacent? $\endgroup$ – N. F. Taussig Jan 14 '17 at 22:32
  • $\begingroup$ @yes, adjacent persons cannot be selected. $\endgroup$ – Kiran Jan 14 '17 at 22:33
  • $\begingroup$ edited the question to use the word 'adjacent' instead of 'nearby' $\endgroup$ – Kiran Jan 14 '17 at 22:41
3
$\begingroup$

A circular arrangement corresponds to a linear arrangement in which the ends of the line have been joined to form a circle.

We first count linear arrangements in which no two adjacent people are selected. Place $n - k$ blue balls in a row, leaving spaces between successive balls and at the ends of the row. There are $n - k - 1$ spaces between successive balls and two at the ends of the row, for a total of $n - k + 1$ spaces. Choose $k$ of these $n - k + 1$ spaces in which to place a green ball. Now number the balls from left to right. The numbers on the green balls, no two of which are adjacent, represent the positions of the selected people. Thus, the number of linear arrangements in which no two consecutive people are selected is $$\binom{n - k + 1}{k}$$

However, we have counted linear arrangements in which people at both ends of the row are selected. These arrangements are not permissible since when the ends of the row are joined to form a circle, the people seated at the ends of the row in a linear arrangement would be sitting in adjacent seats in a circular arrangement.

We count such linear arrangements. Place $n - k$ blue balls in a row, as before. Place a green ball at each of the row. This leaves $n - k - 1$ spaces between successive blue balls and $k - 2$ green balls to place in those spaces. Therefore, there are $$\binom{n - k - 1}{k - 2}$$ linear arrangements in which people are seated at both ends of the row.

Consequently, the number of permissible circular arrangements in which no two of the $k$ selected people are adjacent is $$\binom{n - k + 1}{k} - \binom{n - k - 1}{k - 2}$$

$\endgroup$
  • $\begingroup$ can't the selection of the first $(n-k)$ balls be done in $\dbinom{n}{n-k}$ ways or we did not take this due to overcounting? $\endgroup$ – Kiran Jan 14 '17 at 23:00
  • 1
    $\begingroup$ What I am doing is selecting the positions of the people who are to be chosen. The blue balls act as separators; the numbers on the green balls are the positions of the people who are being selected. $\endgroup$ – N. F. Taussig Jan 15 '17 at 2:21
  • 1
    $\begingroup$ thanks a lot. it took lot of time to understand this concept. your explanation was very good and really helped me . $\endgroup$ – Kiran Jan 15 '17 at 14:53

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.