A385870 Number of subsets of {1,2,...,n} such that no two elements differ by 1 or 6.
1, 2, 3, 5, 8, 13, 21, 29, 45, 66, 99, 148, 218, 337, 497, 755, 1131, 1699, 2571, 3824, 5794, 8661, 13041, 19601, 29376, 44311, 66349, 99936, 150000, 225387, 339000, 508631, 765392, 1148865, 1727249, 2595270, 3898324, 5861084, 8801690, 13231745, 19877092, 29869125
Offset: 0
Examples
For n = 7, the 29 subsets are {}, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}, {5}, {1,5}, {2,5}, {3,5}, {1,3,5}, {6}, {1,6}, {2,6}, {3,6}, {1,3,6}, {4,6}, {1,4,6}, {2,4,6}, {7}, {2,7}, {3,7}, {4,7}, {2,4,7}, {5,7}, {2,5,7}, {3,5,7}.
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,0,1,1,-1,1,-1,0,1,-1,1,-1,1,0,-1,1,-1).
- Index entries for subsets of {1,..,n} with disallowed differences
Crossrefs
Column k=33 of A376033.
Programs
-
Mathematica
CoefficientList[Series[(1 + x + x^2 + 2*x^3 + 2*x^4 + 2*x^5 + 5*x^6 + 3*x^8 + 2*x^9 - x^10 + x^11 - 4*x^12 - x^13 - 2*x^14 - 2*x^15 - x^17)/(1 - x - x^4 - x^5 + 2*x^6 - 4*x^7 + 2*x^8 - 2*x^10 + 2*x^11 - 4*x^12 + 3*x^13 - x^14 + 2*x^16 - x^17 + x^18),{x,0,41}],x] LinearRecurrence[{1,0,0,1,1,-2,4,-2,0,2,-2,4,-3,1,0,-2,1,-1},{1,2,3,5,8,13,21,29,45,66,99,148,218,337,497,755,1131,1699}, 42]
Formula
G.f.: (1 + x + x^2 + 2*x^3 + 2*x^4 + 2*x^5 + 5*x^6 + 3*x^8 + 2*x^9 - x^10 + x^11 - 4*x^12 - x^13 - 2*x^14 - 2*x^15 - x^17)/(1 - x - x^4 - x^5 + 2*x^6 - 4*x^7 + 2*x^8 - 2*x^10 + 2*x^11 - 4*x^12 + 3*x^13 - x^14 + 2*x^16 - x^17 + x^18).
a(n) = a(n-1) + a(n-4) + a(n-5) - 2*a(n-6) + 4*a(n-7) - 2*a(n-8) + 2*a(n-10) - 2*a(n-11) + 4*a(n-12) - 3*a(n-13) + a(n-14) - 2*a(n-16) + a(n-17) - a(n-18) for n >= 18.
Comments