[Math] Number of ways of selecting k objects, no two consecutive


Prove the number of ways of selecting k objects, no two consecutive,
from n objects arrayed in a row is $\binom{n-k+1}{k}$
The proof is as follows:

We know that every time we select our $k$ objects, we will also have to
choose $k – 1$ objects, each of which will go between an adjacent pair of the
$k$ selected objects. So there are $n-(k +k -1) = n-2k+1$ objects left and
we must decide where to put them. These objects can be in any of the $k +1$
spaces, either in front of the first object chosen, after the $k$th object chosen,
or in between any two of the $k$ chosen objects. For these $n – 2k – 1$ objects
we could choose an available space more than once and certainly the order
of selection is irrelevant. Referring to the notation above, our $“n”= k + 1$,and our $“k” = n – 2k + 1$. Thus, our count is $\binom{\left(k+1\right)+\left(n-2k+1\right)-1}{n-2k+1}=\binom{n-k+1}{k}$.

I have several questions:

$\color{red}{1}$-How do we know the k selected objects are all consecutive?

$\color{red}{2}$-After selecting $k$ objects and choosing $k-1$ objects which are between an adjacent pair of the selected $k$ objects,we have $n-2k+1$ objects left,we should decide where to put them,well there are $k-1$ spaces between $k$ selected objects,but how many spaces are there before the first object chosen?How many spaces are there after the last object chosen? I really don't know where does $\left(k+1\right)+\left(n-2k+1\right)-1$ come from.

Best Answer

To give an example of the quoted solution method, let's consider $n=10$ and $k=4$. So we have to pick four items from the list

1   2   3   4   5   6   7   8   9  10

with no two chosen items consecutive.

Here's how we're going to do it. Represent the selected items by four bars, $|\,|\,|\,|$. Between two selected items, there must be at least one non-selected item. Use the symbol $*$ to represent these: $|*|*|*|$. Three unselected items remain to be placed. We can think of the four bars as forming five bins, the first bin to the left of the first bar, the second between the first and second bars, and so on, with the fifth bin to the right of the last bar. The three remaining items can go in any of the five bins. One possibility would be to put one item into each of the first, third, and fourth bins: $*|*|**|**|$. This corresponds to the selection $\{2,4,7,10\}$. If instead, we put all three items into the last bin, we would get $|*|*|*|***$, which corresponds to the selection $\{1,3,5,7\}$.

All that is needed is to count star-and-bar sequences. The first three bars are always followed by a star—there is no choice in the matter—so we absorb each of these "mandatory" stars into the adjacent bar. With this change the sequence corresponding to $\{2,4,7,10\}$ becomes $*|\,|*|*|$, while the sequence corresponding to $\{1,3,5,7\}$ becomes $|\,|\,|\,|***$. Each sequence now consists of four bars and three stars, and there are $\binom{4+3}{4}$ such sequences.

In general, to find the number of selections of $k$ non-consecutive items from a list of $n$ items, there will be $k$ bars (into which $k-1$ mandatory stars have been absorbed) and $n-k-(k-1)=n-2k+1$ stars. The number of sequences is therefore $\binom{k+(n-2k+1)}{k}=\binom{n-k+1}{k}$.

Now to try to address the two questions in your post.

  1. I'm not sure what you mean when you ask how we know the $k$ selected items are all consecutive. We, in fact, want them to be non-consecutive. We don't actually ever choose these items directly. Instead, we choose them implicitly by choosing the placement of stars in bins.
  2. There are no "spaces" that need to be considered. The sizes of the bins are flexible. Any bin may contain between $0$ and $n-2k+1$ stars (neglecting the mandatory stars that we absorbed into the bars), as long as the total number of stars in all bins equals $n-2k+1$.