cp's OEIS Frontend

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

%I A375984 #10 Mar 19 2025 08:38:01
%S A375984 1,2,4,8,12,16,20,25,33,49,77,121,181,258,356,488,680,976,1432,2113,
%T A375984 3089,4449,6329,8961,12729,18226,26292,38056,55012,79200,113548,
%U A375984 162425,232401,333201,478853,689177,991949,1426322,2048244,2938696,4215552,6049984,8688816
%N A375984 Number of subsets of {1,2,...,n} such that no two elements differ by 3, 4, or 5.
%H A375984 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 A375984 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 A375984 <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,0,1,1,2).
%H A375984 <a href="/index/Su#sublatts">Index entries for subsets of {1,..,n} with disallowed differences</a>
%F A375984 a(n) = a(n-1) + a(n-6) + a(n-7) + 2*a(n-8) for n >= 8.
%F A375984 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 A375984 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 A375984 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 A375984 LinearRecurrence[{1, 0, 0, 0, 0, 1, 1, 2}, {1, 2, 4, 8, 12, 16, 20, 25}, 41]
%Y A375984 Column k=28 of A376033.
%K A375984 nonn,easy
%O A375984 0,2
%A A375984 _Michael A. Allen_, Sep 21 2024