[Math] Choosing non-adjacent chairs

combinatoricsprobabilityprobability distributions

  1. There are $n$ chairs in a row. Find the number of ways of
    choosing $k$ of these chairs, so that no two chosen chairs are
    adjacent.

  2. There are 10 chairs in a circle, labelled from 1 to 10. Find the
    number of ways of choosing 3 of these chairs, so that no two chosen
    chairs are adjacent.

  3. There are $n$ chairs in a circle, labelled from 1 to $n.$ Find
    the number of ways of choosing $k$ of these chairs, so that no two
    chosen chairs are adjacent.

I'm fairly new to the concept of distributions and I'm confused about how you would go about solving these problems, even though I'm pretty sure they're connected.

Best Answer

Yes, you are correct in thinking that the questions are connected. They all depend upon the method used in part (a).

(a) The chosen chairs occupy $k$ of the $n-k+1$ positions between and at the ends of the row of non-chosen chairs. The number of choices is therefore $$\begin{pmatrix}n-k+1\\k\\\end{pmatrix}.$$

(b) If chair 1 is not chosen, then the choice of $3$ chairs from the remaining $9$ is calculated as in (a). If chair 1 is chosen then, ignoring chair $1$ and the chairs adjacent to $1$, the choice of $2$ chairs from $7$ is also calculated as in part (a).

The number of choices is therefore $$\begin{pmatrix}7\\3\\\end{pmatrix}+\begin{pmatrix}6\\2\\\end{pmatrix}=50.$$

(c) As in part (b) we have $$\begin{pmatrix}n-k\\k\\\end{pmatrix}+\begin{pmatrix}n-k-1\\k-1\\\end{pmatrix}=\frac{n(n-k-1)!}{k!(n-2k)!}.$$

Related Question