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+1r,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<=NR+1 then Tot=Tot+combi(NR+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 20150522 15:37:25 