A349840 The number of compositions of n using elements from the set {1,3,5,7,8}.

1, 1, 1, 2, 3, 5, 8, 13, 22, 35, 56, 91, 147, 238, 385, 623, 1009, 1632, 2640, 4272, 6912, 11184, 18096, 29280, 47377, 76657, 124033, 200690, 324723, 525413, 850136, 1375549, 2225686, 3601235, 5826920, 9428155

Offset

0,4

Comments

Number of ways to tile an n-board (an n X 1 array of 1 X 1 cells) using squares, trominoes, pentominoes, heptominoes, and octominoes.

Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-1,0,2,4,6,7} for all i=1,...,n.

a(n) gives the sums of the antidiagonals of A349839.

References

D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), North-Holland, Amsterdam, 1970, pp. 755-770.

Links

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

V. Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics, 4(1) (2010), 119-135.

K. Edwards and Michael A. Allen, Strongly restricted permutations and tiling with fences, Discrete Applied Mathematics, 187 (2015), 82-90.

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

Formula

a(n) = a(n-1) + a(n-3) + a(n-5) + a(n-7) + a(n-8) + delta(n,0), a(n<0)=0 (where delta(i,j) is the Kronecker delta).

a(n) = a(n-1) + a(n-2) + a(n-8) - a(n-9) - a(n-10) + delta(n,0) - delta(n,2), a(n<0)=0.

G.f.: 1/(1-x-x^3-x^5-x^7-x^8).

Mathematica

CoefficientList[Series[1/(1-x-x^3-x^5-x^7-x^8), {x, 0, 35}], x]

Crossrefs

Sums of antidiagonals of triangles in the same family as A349839: A000045, A006498, A079962, A349843.

Sequence in context: A117770 A053412 A198202 * A293639 A320356 A004697

Adjacent sequences: A349837 A349838 A349839 * A349841 A349842 A349843

Keyword

easy,nonn

Author

Michael A. Allen, Dec 05 2021

Status

approved