cp's OEIS Frontend

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

%I A375978 #8 Mar 19 2025 08:35:01
%S A375978 1,2,4,8,12,18,24,34,47,73,111,177,267,409,600,900,1324,2004,2996,
%T A375978 4564,6848,10377,15513,23385,34953,52685,78969,119138,178840,269604,
%U A375978 404656,609310,914548,1376530,2067231,3111457,4674751,7034897,10570855,15903377,23898528
%N A375978 Number of subsets of {1,2,...,n} such that no two elements differ by 3 or 5.
%H A375978 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 A375978 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 A375978 <a href="/index/Rec#order_12">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1,1,-1,1,1,1,-1,-1,-1,-1).
%H A375978 <a href="/index/Su#sublatts">Index entries for subsets of {1,..,n} with disallowed differences</a>
%F A375978 a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-4) - a(n-5) + a(n-6) + a(n-7) + a(n-8) - a(n-9) - a(n-10) - a(n-11) - a(n-12) for n >= 12.
%F A375978 G.f.: (1 + x + x^2 + 3*x^3 + x^4 + x^5 - x^6 - 3*x^7 - 4*x^8 - 3*x^9 - 2*x^10 - x^11)/(1 - x - x^2 + x^3 - x^4 + x^5 - x^6 - x^7 - x^8 + x^9 + x^10 + x^11 + x^12).
%e A375978 For n = 6, the 24 subsets are {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {2,4}, {3,4}, {2,3,4}, {5}, {1,5}, {3,5}, {1,3,5}, {4,5}, {3,4,5}, {6}, {2,6}, {4,6}, {2,4,6}, {5,6}, {4,5,6}.
%t A375978 CoefficientList[Series[(1 + x + x^2 + 3*x^3 + x^4 + x^5 - x^6 - 3*x^7 - 4*x^8 - 3*x^9 - 2*x^10 - x^11)/(1 - x - x^2 + x^3 - x^4 + x^5 - x^6 - x^7 - x^8 + x^9 + x^10 + x^11 + x^12),{x,0,38}],x]
%t A375978 LinearRecurrence[{1, 1, -1, 1, -1, 1, 1, 1, -1, -1, -1, -1}, {1, 2, 4, 8, 12, 18, 24, 34, 47, 73, 111, 177}, 39]
%Y A375978 Column k=20 of A376033.
%K A375978 easy,nonn
%O A375978 0,2
%A A375978 _Michael A. Allen_, Sep 20 2024