1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think it is taken from the first pages of : An Elementary Solution to the Ménage Problem - by A F Passmore. $\endgroup$ – jiten Oct 20 '20 at 8:32
3
+50
$\begingroup$

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$.
$\endgroup$
6
  • 1
    $\begingroup$ @ Will Orrick,Thank you so much for the answer,just some observations,we choose $k$ bars to be our non-consecutive objects and of course because of this property we need at least $k-1$ of the remaining objects to be placed between every two adjacent bars,then I thought "now why don't we just choose $n-2k+1$ places from the $k+1$ bins? t" then I figured out that in this case there does not exist a bin containing more than one object (indeed every bin contains at most one element). $\endgroup$ – user771003 May 18 '20 at 8:33
  • 1
    $\begingroup$ And this is not what we want,since every bin can contain more than one object (as you said at most $n-2k+1$ objects),besides how the $n-2k+1$ remaining objects are placed into $k+1$ bins gives the number of ways to choose $k$ non-consecutive objects from a set of cardinality $n$,moreover the answer is the number of the solutions to the equations:$$a_1+a_2+...+a_k+a_{k+1}=2n-k+1$$ Where each $a_i\;\;\; (i \in \mathbb N^{+})$ is a non-negative integer,am I right? $\endgroup$ – user771003 May 18 '20 at 8:47
  • 1
    $\begingroup$ Did you mean non-negative integer solutions to $$a_1+a_2+\ldots+a_k+a_{k+1}=n-2k+1?$$ If so, then you are right. There is a one-to-one correspondence between such solutions and sequences containing $n-2k+1$ stars and $k$ bars. (Take $a_j$ to be the number of stars in the $j^\text{th}$ interval, where the intervals are formed by the bars.) And there is a one-to-one correspondence between star-and-bar sequences and selections of $k$ non-consecutive objects from a set of size $n$. (Insert an extra star in each of the $k-1$ middle intervals and let the positions of the bars in the sequence be... $\endgroup$ – Will Orrick May 18 '20 at 11:53
  • $\begingroup$ ...the selected items.) A small example, $n=4$, $k=2$. The three possible selections are $\{1,3\}$, $\{1,4\}$, and $\{2,4\}$. Write sequences $|*|*$, $|**|$, and $*|*|$. Now absorb the mandatory star in the middle interval into the bar to its left. This leaves the sequences $|\,|*$, $|*|$, and $*|\,|$. These are all the sequences you can make containing one star and two bars ($4-2\cdot2+1$ stars and $2$ bars, giving $\binom{2+(4-2\cdot2+1)}{2}$ sequences). What is being chosen here? We are not choosing "places" from "bins". Rather, we are choosing which $k$ positions in a star-and-bar... $\endgroup$ – Will Orrick May 18 '20 at 12:05
  • $\begingroup$ ...sequence of length $n-k+1$ are going to contain the bars. $\endgroup$ – Will Orrick May 18 '20 at 12:06
1
$\begingroup$

I am giving my own proof. Check if this can clear your doubt.

Suppose we have $k$ red balls placed and $k+1$ buckets in between and on two far sides of them. We shall distribute $n-k$ blue balls by putting at least one blue ball in each middle buckets (but the left and rightmost buckets can contain $0$ balls) .Then we start numbering all the balls from say, from left to right.

And that guarantees that we have at least one blue ball in between two red balls. And we have total $n$ balls.

What does it ultimately do? We shall pick up those red balls (those were destined to be picked up). This means we shall never choose two consecutive balls. We have just arrived to the original problem.

As there are $n-k$ .But unfortunately this is useless. to put, total $k+1$ buckets among which $k-1$ must contain at least one blue ball. And other two may not contain a single one.

So we can do this in $\binom{(n-k)-(k-1)+(k+1)-1}{(k+1)-1}=\binom{n-k+1}{k}$ ways.

$\endgroup$
3
  • $\begingroup$ Do we choose the $k$ objects such that they all are consecutive? $\endgroup$ – user771003 May 10 '20 at 12:16
  • 1
    $\begingroup$ No. There are placed $k$ red balls (to be chosen) beforehand. And then we place the balls in between them. The red balls are those which is to be chosen. You may keep any number( non zero) of blue balls( not to be chosen) in between. In the original question, we choose $k$ balls, none of which is consecutive. This means they have objects in between. My presentation is easier to deal with. $\endgroup$ – Alapan Das May 10 '20 at 12:21
  • 1
    $\begingroup$ They were kept consecutive until we place blue balls to let them be consecutive no more. Not $k-1$ blue balls, but $k-1$ buckets in between with $\geq k-1$ blue balls. $\endgroup$ – Alapan Das May 10 '20 at 12:34
1
$\begingroup$

This is an application of the "stars and bars" formula. If we have $a$ objects to be placed in $b$ buckets and we don't care about the arrangement of objects in each bucket, then we can think of this as choosing $b-1$ gaps between the buckets (the "bars") from an expanded pool of $a+b-1$ objects, so there are $\binom{a+b-1}{b-1}$ arrangements.

In this case we can think of the $k$ objects as being the $b-1$ bars between the buckets. To avoid any of these $k$ objects being consecutive we also have the additional constraint that there is at least one object in each of the $k-1$ buckets between one bar and the next. So that leaves $n-2k+1$ objects to be placed in $k+1$ buckets. Setting $a=n-2k+1$ and $b=k+1$ in the stars and bars formula gives

$\binom {(n-2k+1)+(k+1)-1}{(k+1)-1}=\binom{n-k+1}{k}$

arrangements.

$\endgroup$
0
1
$\begingroup$

This “proof” doesn’t deserve that name (if you’ve quoted it verbatim and in full) – I'd recommend ditching the text that you took it from. It speaks about “putting” objects somewhere, but we’re selecting objects in a fixed arrangement. Even if we accept this as an abuse of language intended to refer to placing selections, not objects, the argument is quite confusing and unrigorous; I’m not surprised you have questions about it. For instance, it’s unclear what is meant by “choose $k-1$ objects, each of which will go between an adjacent pair of the $k$ selected objects”, since no objects are “going” anywhere, and selections can’t be “chosen”.

To arrive at a proper proof, consider $n$ balls, $k$ of which are red and the rest blue, and count the ways to arrange the balls linearly so that no red balls are adjacent (where the order of balls of the same colour doesn’t matter). The red balls represent the selected objects. (This may have been the image the author had in mind, but a proof shouldn’t make you guess what images the author has in mind.) Glue a blue ball to the right of each red ball except the right-most one. Now you have $k-1$ glued pairs, $1$ red ball and $n-k-(k-1)=n-2k+1$ blue balls, for a total of $k-1+1+n-2k+1=n-k+1$ objects, and you need to choose positions for $k$ of them, which can be done in $\binom{n-k+1}k$ ways.

$\endgroup$
2
  • $\begingroup$ Would the downvoter care to comment? $\endgroup$ – joriki May 10 '20 at 13:39
  • 1
    $\begingroup$ @user715522: I haven't looked at the other proofs, but with respect to mine, you seem to be misunderstanding it. My impression that this is due to the confusion sowed by the bad "proof" you quoted. You seem to still be thinking in terms of putting the objects somewhere. But the objects are already arranged, they're not going anywhere, we're merely selecting some of them. In my proof, it's the red balls that are being arranged, and these stand not for the objects in the arrangement but for the selections. So your counterargument doesn't apply to my proof. $\endgroup$ – joriki May 10 '20 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy