A375981 Number of subsets of {1,2,...,n} such that no two elements differ by 1, 4, or 5.
1, 2, 3, 5, 8, 11, 14, 19, 25, 34, 49, 70, 99, 141, 196, 270, 375, 520, 723, 1014, 1420, 1985, 2777, 3874, 5396, 7526, 10496, 14642, 20449, 28555, 39860, 55647, 77660, 108356, 151214, 211028, 294507, 411071, 573763, 800796, 1117679, 1559895, 2177002
Offset: 0
Examples
For n = 6, the 14 subsets are {}, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}, {5}, {2,5}, {3,5}, {6}, {3,6}, {4,6}.
The a(4) = 8 compositions of 9 into parts 1, 6, 8, 9, ... are 1+1+1+1+1+1+1+1+1, 1+1+1+6, 1+1+6+1, 1+6+1+1, 6+1+1+1, 1+8, 8+1, 9.
Links
- Michael A. Allen, Combinations without specified separations, Communications in Combinatorics and Optimization (in press).
- Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024.
- Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1,0,1,0,1,0,0,-1).
- Index entries for subsets of {1,..,n} with disallowed differences
Crossrefs
See comments for other sequences related to restricted combinations.
Cf. A376743.
Programs
-
Mathematica
CoefficientList[Series[(1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 - x^8 - x^9 - x^10)/(1 - x - x^3 + x^4 - x^6 - x^8 + x^11),{x,0,42}],x] LinearRecurrence[{1, 0, 1, -1, 0, 1, 0, 1, 0, 0, -1}, {1, 2, 3, 5, 8, 11, 14, 19, 25, 34, 49}, 42]
Formula
a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) + a(n-8) - a(n-11) for n >= 11.
G.f.: (1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 - x^8 - x^9 - x^10)/(1 - x - x^3 + x^4 - x^6 - x^8 + x^11).
Comments