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

1, 2, 3, 5, 8, 13, 18, 28, 41, 62, 91, 141, 208, 317, 473, 719, 1069, 1623, 2425, 3666, 5487, 8295, 12424, 18751, 28130, 42416, 63657, 95944, 144083, 217023, 326060, 490985, 737849, 1110753, 1669685, 2512993, 3778125, 5685594, 8549027, 12863637, 19344100, 29104549

Offset: 0

Author

Michael A. Allen, Jul 18 2024

Keywords

• easy
• nonn

Comments

a(n) is the number of permutations of 0..n with each element moved by -1 to 1 places and every 5 consecutive elements having their maximum within 5 of their minimum.

Examples

			For n = 6, the 18 subsets are {}, {1}, {2}, {3}, {4}, {5}, {6}, {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6}, {1,3,5}, {2,4,6}.
		

Links

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

Crossrefs

Column k=17 of A376033.

Programs

Mathematica

CoefficientList[Series[(1 + 2*x + 2*x^2 + 2*x^3 + 2*x^4 + 4*x^5 + 3*x^6 + 2*x^7 + x^8 + x^9)/(1 - x^2 - x^3 - x^4 + x^5 - x^6 - x^7 - x^8 - x^10),{x,0,41}],x]
LinearRecurrence[{0,1,1,1,-1,1,1,1,0,1},{1,2,3,5,8,13,18,28,41,62},50] (* Harvey P. Dale, Feb 15 2025 *)

Formula

a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-5) + a(n-6) + a(n-7) + a(n-8) + a(n-10) for n >= 10.

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