A351874 Number of subsets of {1,2,...,n} such that any pair of elements do not 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,2

Links

Table of n, a(n) for n=0..43.

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,0,1).

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).

Example

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

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]

Crossrefs

Other sequences giving numbers of restricted combinations: A000045, A006498, A006500, A031923, A000930, A130137, A263710, A079972, A224809, A351873, A224810, A224815, A003269, A317669, A177485, A121832, A224808, A003520, A224811, A005708, A224812, A005709, A224813, A005710.

Sequence in context: A062438 A102424 A237826 * A080000 A333573 A361852

Adjacent sequences: A351871 A351872 A351873 * A351875 A351876 A351877

Keyword

easy,nonn

Author

Michael A. Allen, Feb 22 2022

Status

approved