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

1, 2, 3, 5, 7, 9, 12, 16, 23, 33, 47, 66, 91, 126, 175, 245, 344, 482, 674, 940, 1311, 1830, 2557, 3575, 4997, 6982, 9752, 13620, 19025, 26579, 37136, 51885, 72487, 101264, 141463, 197624, 276088, 385711, 538860, 752810, 1051698, 1469249, 2052584, 2867532

Offset: 0

Author

Michael A. Allen, Feb 22 2022

Keywords

• easy
• nonn

Examples

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

Links

• Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,0,1).
• Index entries for subsets of {1,..,n} with disallowed differences

Crossrefs

Column k=13 of A376033.

Programs

Mathematica

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

Formula

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

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