# Choosing Non-Consecutive Integers from a list of N Integers

• Feb 21st 2008, 11:18 AM
Niall2
Choosing Non-Consecutive Integers from a list of N Integers
Prove that the number of ways choosing k integers from the integers 1,2,3...n, such that no two of the chosen integers are consecutive is:
(n-k+1) C k [as in : (n-k+1)CHOOSE(k) ]
with a suitable adjustment when n - k +1 < k
• Feb 21st 2008, 12:13 PM
Plato
Quote:

Prove that the number of ways choosing k integers from the integers 1,2,3...n, such that no two of the chosen integers are consecutive is:
$\displaystyle {{n-k+1} \choose {k}}$

Note that $\displaystyle k \le \left\lfloor {\frac{{n + 1}}{2}} \right\rfloor$; from the set $\displaystyle \left\{ {1,2,3,4,5,6,7,8,9} \right\}$ the subset $\displaystyle \left\{ {3,5,7,9} \right\}$
can be represented by the string 001010101. If fact, any subset of four such that no two are consecutive can be represented by a 9-bit string of four 1s and five zeros in which there are no adjacent 1s.

Thus, from the set $\displaystyle \left\{ {1,2,3, \cdots ,n} \right\}$ we can use an n-bit string consisting of k 1s and n-k 0s, having no adjacent 1 to represent a subset of k elements containing no consecutive integers.
• Feb 24th 2008, 02:24 PM
Niall2
Ah. I can see how you can use an n-bit string to represent the problem.

Does that mean $\displaystyle \begin{pmatrix}n-k+1 \\ k\end{pmatrix}$ is the number of ways to arrange 1's and 0's in an n-bit string so that no two 1's are consecutive?
And if so, how can I prove that is the case?
• Feb 24th 2008, 02:57 PM
Plato
Quote:

Ah. I can see how you can use an n-bit string to represent the problem. Does that mean $\displaystyle \begin{pmatrix}n-k+1 \\ k\end{pmatrix}$ is the number of ways to arrange 1's and 0's in an n-bit string so that no two 1's are consecutive? And if so, how can I prove that is the case?

EXACTLY!

Lets take a particular case: 1111000000 (four ones and six zeros).
We are going to use the zeros to separate the ones from each other: _0_0_0_0_0_0_. We have seven spaces into which we can put four ones.
That can be done in $\displaystyle \binom {7}{4}$ ways.
Now you generalize.
• Feb 24th 2008, 03:08 PM
Niall2
Brilliant...
EDIT: I now see completely :)

Thanks a lot