A375984 - OEIS

%I #8 Sep 23 2024 18:09:02

%S 1,2,4,8,12,16,20,25,33,49,77,121,181,258,356,488,680,976,1432,2113,

%T 3089,4449,6329,8961,12729,18226,26292,38056,55012,79200,113548,

%U 162425,232401,333201,478853,689177,991949,1426322,2048244,2938696,4215552,6049984,8688816

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

%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_08">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,0,1,1,2).

%F a(n) = a(n-1) + a(n-6) + a(n-7) + 2*a(n-8) for n >= 8.

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

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

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

%t LinearRecurrence[{1, 0, 0, 0, 0, 1, 1, 2}, {1, 2, 4, 8, 12, 16, 20, 25}, 41]

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

%Y Column k=28 of A376033.

%K nonn,easy

%O 0,2

%A _Michael A. Allen_, Sep 21 2024