Number of k-subsets of an n-set, no pair of consecutive integers

Feb 2014
8
0
South Africa
Let f(n,k) be the number of k-subsets of an n set {1,2,....,n} that does not contain a pair of consecutive integers. Show that f(n,k)= {n-k+1} \choose {k} I know we can think of it as a sequence of k 1's and n-k 0's with no pair of consecutive 1's, but I can't figure out why this would be the same as choosing k places from n-k+1. Any help would be appreciated.
 

Plato

MHF Helper
Aug 2006
22,490
8,653
Let f(n,k) be the number of k-subsets of an n set {1,2,....,n} that does not contain a pair of consecutive integers. Show that f(n,k)= {n-k+1} \choose {k} I know we can think of it as a sequence of k 1's and n-k 0's with no pair of consecutive 1's, but I can't figure out why this would be the same as choosing k places from n-k+1. Any help would be appreciated.
First, it should be clear to you that $k \le \left\lceil {{n \over 2}} \right\rceil $ (that is the ceiling function).
Think of a bit-string consisting of k ones and n-k zeros.
Any rearrangement of that string represents a k-element subset of an n-set.
How many rearrangements are there in which no two ones are consecutive?

Well the zeros create n-k+1 places to place the ones, chose k of them.
 
  • Like
Reactions: 1 person