1
$\begingroup$

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.

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

Try to think about subset of set {1,2, ..., n-k+1}. Standard method of counting in combinatorics is finding bijection beetwen some sets.

Below is my solution.

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.

$\endgroup$
  • $\begingroup$ A very interesting approach.... I would've never thought about this. Thanks alot! $\endgroup$ – TheNotMe Jan 18 '18 at 20:09
  • $\begingroup$ Note that in generatingfunctionlogy (what was referred to in Alexander's comment above) it says that the answer is $\binom{n-k+1}{k}$ $\endgroup$ – TheNotMe Jan 19 '18 at 10:36
  • 1
    $\begingroup$ 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 $\endgroup$ – J. Doe Jan 19 '18 at 11:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.