1
$\begingroup$

How many subsets has the set $\{ 1, 2 , \dots, n\}$ that don't contain two consecutive naturals?

My idea is the following:

$$\displaystyle{2^{\frac{n}{2}}}$$

because $n$ numbers, we can't take two consecutive..

Is this correct??

$\endgroup$
  • 2
    $\begingroup$ $2^{n/2}$ is irrational if $n$ is odd, so that can't be a correct formula in general. $\endgroup$ – Barry Cipra Jun 2 '14 at 16:32
  • $\begingroup$ Could you give me a hint how I can find the number of subsets then?? $\endgroup$ – Mary Star Jun 2 '14 at 16:33
  • 3
    $\begingroup$ A good idea on a problem like is, especially if you're stuck, is to explicitly work out the first few cases and see if a pattern emerges. $\endgroup$ – Barry Cipra Jun 2 '14 at 16:37
  • 1
    $\begingroup$ How many subsets of the set {1,2,...,n}. Not how many "has the set." $\endgroup$ – blue Jun 2 '14 at 19:59
  • 1
    $\begingroup$ @MaryStar it seems like many of the problems you have been posting recently are about recurrence relations. $\endgroup$ – Jorge Fernández Hidalgo Jun 2 '14 at 20:01
6
$\begingroup$

Here is a substantial hint:

Let $f_n$ be the number you are looking for. Then $f_{n+1}$ adds to $f_n$ the number of subsets containing $n+1$ - these cannot contain $n$, so must be subsets of $\{1,2, \dots , n-1\}$ with $n+1$ added as a member.

You should be able to analyse the problem from there. Don't forget the empty set.

$\endgroup$
  • $\begingroup$ $$(n-1)\text{ is the number of 2-element subsets that contains each time a number of the set } \{1,2, \dots, n-1\} \text{ and the element } (n+1)$$ Then do we have to find the number of subsets that contain three elements including the element $(n+1)$, then the number of subsets that contain four elements including the element $(n+1)$, and so on??? Is there a formula that describes that? $\endgroup$ – Mary Star Jun 2 '14 at 17:01
  • 1
    $\begingroup$ @MaryStar You need to write a recurrence of the form $f_{n+1}=f_n+ ?$ - you don't need to count the zero-element subsets, one element subsets etc separately, because $f$ counts them all at once. You should include the empty set in your count. You can subtract it at the end, but if you don't include it, you miss the set $\{n+1\}$ of one element. $\endgroup$ – Mark Bennet Jun 2 '14 at 17:09
1
$\begingroup$

Answer:

If n is even, the number of subsets = $${n\choose0}+{n\choose1}+{{n-1}\choose2}+\cdots+{{\frac{n}{2}+1}\choose \frac{n}{2}}$$

IF n is odd, $${n\choose0}+{n\choose1}+{{n-1}\choose2}+\cdots+{{\frac{n+1}{2}}\choose \frac{n+1}{2}}$$

As per Barry's advice, I worked a few scenarios and found this relation after some hard thinking. Hopefully it is useful. Good luck

Thanks

Satish

$\endgroup$
  • $\begingroup$ @BarryCipra, No problem, Thanks for guiding me to the right answer. Thanks $\endgroup$ – Satish Ramanathan Jun 2 '14 at 20:03
  • $\begingroup$ Oops I forgot the empty set. $\endgroup$ – Satish Ramanathan Jun 2 '14 at 20:13
1
$\begingroup$

Alternatively, it's easy to see that for a subset of size $i$ the number of subsets of $\left[n\right]$ with the required property is $\displaystyle \binom{n-i+1}{i}$ using the following set-up:

Choosing such a subset bijectively corresponds to forming a binary string of length $n$ using $i$ $1$s and $n-i$ $0$s such that no $2$ $1$s are adjacent. Write down $n-i$ $0$s and observe that there are $n-i+1$ positions in which the $i$ $1$s can be inserted. Thus the $1$s can be chosen in $\displaystyle \binom{n-i+1}{i}$ ways. Summing over $i= 1, 2, \ldots, \bigg\lfloor\dfrac{n+1}{2}\bigg \rfloor$ yields the final answer.

As Mark Bennett points out, this is simply $F_{n+2}$ where $F_{n}$ is the $n^{th}$ Fibonacci number.

$\endgroup$

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.