A351873 - OEIS

%I #18 Oct 03 2024 15:13:19

%S 1,2,4,8,12,16,21,29,45,73,117,178,260,376,552,832,1273,1945,2937,

%T 4385,6521,9730,14612,22040,33252,50032,75053,112437,168549,253065,

%U 380429,572018,859572,1290664,1937152,2907744,4366321,6558769,9853041,14800001,22226225

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

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,1,1,2).

%F a(n) = a(n-1) + a(n-5) + a(n-6) + 2*a(n-7) + delta(n,0) + delta(n,1) + 2*delta(n,2) + 4*delta(n,3) + 4*delta(n,4) + 3*delta(n,5) + 2*delta(n,6).

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

%e When n = 5, the 16 subsets are {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {2,3}, {2,4}, {3,4}, {3,5}, {4,5}, {1,2,3}, {2,3,4}, and {3,4,5}.

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

%t LinearRecurrence[{1,0,0,0,1,1,2},{1,2,4,8,12,16,21},50] (* _Harvey P. Dale_, Mar 01 2023 *)

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

%Y Column k=12 of A376033.

%K easy,nonn

%O 0,2

%A _Michael A. Allen_, Feb 22 2022