# Subsets of fixed size with no adjacent elements

One can go over all subsets of the set $\{1,...,n\}$ by using a binary representation - $0$ at index $i$ means that element $i$ is not in the set, while $1$ at index $i$ meanas that it is.

Furthermore, one can count the number of subsets that have no adjacent elements (ie, if $i$ is in the subset then $i-1,i+1$ are not) by counting binary vectors of length $n$ with no adjacent $1$s, recursively: denote by $a_n$ the number of such binary vectors. Either element $1$ is not in the subset (ie, at index $1$ in the binary vector there is a $0$) and there are $a_{n-1}$ ways to continue, or there is $10$ at indexes $1,2$ in the binary vector and there are $a_{n-2}$ ways to continue. Meaning, the number of such binary vectors (subsets) is $a_n = a_{n-1} + a_{n-2}$.

However, how can we count the number of subsets of some fixed size $0 \leq k \leq n$ that have no adjacent elements? Somehow, we need to calculate the number of substrings of length $k$ of binary strings of length $n$ that have no adjacent $1$'s. The number of subsets of length $k$ of the main set is $\binom{n}{k}$.

I would appreciate some guidance.

• See Wilf's generatingfunctionology, problems 11-13 in chapter 1 exercises and example 1 in section 4.3. – Alexander Burstein Jan 19 '18 at 7:27
• Wow, a super useful handbook. I'll make sure to browse it well. Much, much, much appreciated – TheNotMe Jan 19 '18 at 10:07

It will be ${n - k + 1 \choose k}$. For every subset of set {1, 2, ..., n-k,n-k+1} try to add 0 to smallest element, 1 to next element, ..., $k-1$ to largest element. You will get subset of size $k$ with no adjacent elements. Conversly if from set with no adjacent elements you will subtract $k-1$ from largest element, $k-2$ from second largest element, ..., $0$ from smallest number you will get some subset of set {1, 2, ..., n-k+1} - so given function is bijection.
• Note that in generatingfunctionlogy (what was referred to in Alexander's comment above) it says that the answer is $\binom{n-k+1}{k}$ – TheNotMe Jan 19 '18 at 10:36
• Yes is small mistake - there is $k+1$ numbers in set $\{0,...,k\}$ so we should add $k-1$ to largest element - I've corrected answer – J. Doe Jan 19 '18 at 11:35