All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
No neighbors allowed (Posted on 2015-05-22) Difficulty: 3 of 5
How many subsets of {1,2,...,n} contain no consecutive integers?

See The Solution Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 1 of 2
The idea is to consider choosing double numbers from among the n choices, but with the second number not really being considered as in the chosen set. The problem is that if the last number, n, is to be chosen, we need n+1 to be part of the set to be chosen from. Also, when counting combinations, depending on the cardinality of the subset, the cardinality of the including set has to be artificially decreased.

For example, take the case of n=5. When choosing 2 out of these and we're using this combination approach, we need to go up to 6, that is, n+1. But the combinations are of only 2 out of 4:

1,3 considered as 12 34 5 6
1,4 considered as 12 3 45 6
1,5 considered as 12 3 4 56
2,4 considered as 1 23 45 6
2,5 considered as 1 23 4 56
3,5 considered as 1 2 34 56

That is we're choosing four objects, two of which are to be singletons and two as pairs, the second member of each pair being the number ineligible for inclusion.  Similarly for other numbers, when choosing r out of n, we really want C(n+1-r,r), as number n+1 has to be included to accommodate the nonused part of pairs, but each pairing cuts down on the number to be chosen from.

    4   kill "noneighb.txt"
    5   open "noneighb.txt" for output as #2
   10   for N=3 to 12:Tot=0
   20   for R=0 to N
   30     if R<=N-R+1 then Tot=Tot+combi(N-R+1,R)
   40   next
   50   print #2,N,Tot
   60   next
   70   close #2
Before running this, I thought I'd have to go to Sloane's OEIS with the results, but the output seems more obvious:   
 3   5 
 4   8 
 5   13 
 6   21 
 7   34 
 8   55 
 9   89 
 10   144 
 11   233 
 12   377 
These include the null set (r=0), choosing a subset with no members of the original set.

These are obviously the Fibonacci numbers F(n+2).

  Posted by Charlie on 2015-05-22 15:37:25
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (19)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information