A375980 - OEIS

%I #10 Mar 19 2025 08:35:35

%S 1,2,3,4,6,9,12,17,25,35,49,71,101,142,203,290,410,583,832,1181,1677,

%T 2389,3397,4825,6865,9766,13879,19736,28074,39913,56748,80709,114765,

%U 163175,232045,329975,469189,667178,948743,1349062,1918310,2727839,3878912,5515657

%N Number of subsets of {1,2,...,n} such that no two elements differ by 1, 2, 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_06">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,0,-1,1).

%H <a href="/index/Su#sublatts">Index entries for subsets of {1,..,n} with disallowed differences</a>

%F a(n) = a(n-1) + a(n-3) - a(n-5) + a(n-6) for n >= 6.

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

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

%t CoefficientList[Series[(1 + x + x^2 + x^5)/(1 - x - x^3 + x^5 - x^6),{x,0,42}],x]

%t LinearRecurrence[{1, 0, 1, 0, -1, 1}, {1, 2, 3, 4, 6, 9}, 43]

%Y Column k=19 of A376033.

%K easy,nonn

%O 0,2

%A _Michael A. Allen_, Sep 21 2024