A375983 - OEIS

%I #12 Sep 20 2024 06:23:34

%S 1,2,4,6,9,12,15,20,28,40,59,86,121,169,235,326,458,649,919,1301,1837,

%T 2582,3627,5101,7179,10118,14272,20120,28349,39930,56221,79165,111509,

%U 157091,221325,311830,439291,618791,871621,1227752,1729447,2436267,3432010

%N Number of subsets of {1,2,...,n} such that no two elements differ by 2, 4, or 5.

%C a(n) is the number of compositions of n+5 into parts 1, 6, 7, 9, 12, 15, 18, 21, ...

%H Michael A. Allen, <a href="https://doi.org/10.22049/CCO.2024.29370.1959">Combinations without specified separations</a>, Communications in Combinatorics and Optimization (in press).

%H Michael A. Allen, <a href="https://doi.org/10.48550/arXiv.2409.00624">Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings</a>, arXiv:2409.00624 [math.CO], 2024.

%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,-1,0,1,1,0,0,-1).

%F a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) + a(n-7) - a(n-10) for n >= 10.

%F G.f.: (1 + x + 2*x^2 + x^3 + 2*x^4 + x^5 - x^7 - x^8 - x^9)/(1 - x - x^3 + x^4 - x^6 - x^7 + x^10).

%e For n = 6, the 15 subsets are {}, {1}, {2}, {1,2}, {3}, {2,3}, {4}, {1,4}, {3,4}, {5}, {2,5}, {4,5}, {6}, {3,6}, {5,6}.

%t CoefficientList[Series[(1 + x + 2*x^2 + x^3 + 2*x^4 + x^5 - x^7 - x^8 - x^9)/(1 - x - x^3 + x^4 - x^6 - x^7 + x^10),{x,0,42}],x]

%t LinearRecurrence[{1, 0, 1, -1, 0, 1, 1, 0, 0, -1}, {1, 2, 4, 6, 9, 12, 15, 20, 28, 40}, 42]

%Y See A375981 for other sequences related to restricted combinations.

%K easy,nonn

%O 0,2

%A _Michael A. Allen_, Sep 04 2024