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

 No neighbors allowed (Posted on 2015-05-22)
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 | 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

 Search: Search body:
Forums (0)