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

Printable View

- Feb 21st 2008, 11:18 AMNiall2Choosing 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 PMPlato
Note that ; from the set the subset

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 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 PMNiall2
Ah. I can see how you can use an n-bit string to represent the problem.

Does that mean 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 PMPlato
- Feb 24th 2008, 03:08 PMNiall2
Brilliant...

EDIT: I now see completely :)

Thanks a lot