cp's OEIS Frontend

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

%I A375979 #9 Mar 19 2025 08:37:24
%S A375979 1,2,4,8,16,24,32,42,55,76,118,192,314,504,767,1120,1612,2324,3412,
%T A375979 5148,7900,12169,18631,28152,42024,62364,92576,138141,207629,313718,
%U A375979 474796,717456,1080320,1620994,2427447,3634800,5450293,8188936,12323172,18555880,27930853
%N A375979 Number of subsets of {1,2,...,n} such that no two elements differ by 4 or 5.
%H A375979 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 A375979 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 A375979 <a href="/index/Rec#order_12">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,-1,0,1,1,2,3,-1,-2,-3).
%H A375979 <a href="/index/Su#sublatts">Index entries for subsets of {1,..,n} with disallowed differences</a>
%F A375979 a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) + a(n-7) + 2*a(n-8) + 3*a(n-9) - a(n-10) - 2*a(n-11) - 3*a(n-12) for n >= 12.
%F A375979 G.f.: (1 + x + 2*x^2 + 3*x^3 + 7*x^4 + 6*x^5 + 3*x^6 - x^7 - 3*x^8 - 6*x^9 - 5*x^10 - 3*x^11)/(1 - x - x^3 + x^4 - x^6 - x^7 - 2*x^8 - 3*x^9 + x^10 + 2*x^11 + 3*x^12).
%e A375979 For n = 6, the 32 subsets are {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}, {5}, {2,5}, {3,5}, {2,3,5}, {4,5}, {2,4,5}, {3,4,5}, {2,3,4,5}, {6}, {3,6}, {4,6}, {3,4,6}, {5,6}, {3,5,6}, {4,5,6}, {3,4,5,6}.
%t A375979 CoefficientList[Series[(1 + x + 2*x^2 + 3*x^3 + 7*x^4 + 6*x^5 + 3*x^6 - x^7 - 3*x^8 - 6*x^9 - 5*x^10 - 3*x^11)/(1 - x - x^3 + x^4 - x^6 - x^7 - 2*x^8 - 3*x^9 + x^10 + 2*x^11 + 3*x^12),{x,0,38}],x]
%t A375979 LinearRecurrence[{1, 0, 1, -1, 0, 1, 1, 2, 3, -1, -2, -3}, {1, 2, 4, 8, 16, 24, 32, 42, 55, 76, 118, 192}, 39]
%Y A375979 Column k=24 of A376033.
%K A375979 nonn,easy
%O A375979 0,2
%A A375979 _Michael A. Allen_, Sep 20 2024