A005709 a(n) = a(n-1) + a(n-7), with a(i) = 1 for i = 0..6.

1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 10, 13, 17, 22, 28, 35, 43, 53, 66, 83, 105, 133, 168, 211, 264, 330, 413, 518, 651, 819, 1030, 1294, 1624, 2037, 2555, 3206, 4025, 5055, 6349, 7973, 10010, 12565, 15771, 19796, 24851

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 0...m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.

For n >= 7, a(n-7) is the number of compositions of n in which each part is >=7. - Milan Janjic, Jun 28 2010

Number of compositions of n into parts 1 and 7. - Joerg Arndt, Jun 24 2011

a(n+6) is the number of binary words of length n having at least 6 zeros between every two successive ones. - Milan Janjic, Feb 09 2015

Number of tilings of a 7 X n rectangle with 7 X 1 heptominoes. - M. Poyraz Torcuk, Feb 26 2022

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n=0..500
• Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
• Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
• Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See p. 18.
• D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 10.
• P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
• E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
• I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
• R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 380
• S. Kitaev, Independent sets on path-schemes, JIS 9 (2006) # 06.2.2 G(x) for M={1,2,3,4,5,6} gives seq. shifted 6 places left
• R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO], 2016, Section 4.6.
• Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
• David Newman, Problem E3274, Amer. Math. Monthly, 95 (1988), 555.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,1).

Crossrefs

Cf. A000045, A000079, A000930, A003269, A003520, A005708, A005710, A005711.

Programs

Maple

A005709 := proc(n) option remember; if n <=6 then 1; else A005709(n-1)+A005709(n-7); fi; end;
with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 6)}, unlabeled]: seq(count(SeqSetU, size=j), j=7..55); # Zerinvary Lajos, Oct 10 2006
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 6)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=6..54); # Zerinvary Lajos, Mar 26 2008
M:= Matrix(7, (i,j)-> if j=1 and member(i,[1,7]) then 1 elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,1]; seq(a(n), n=0..50); # Alois P. Heinz, Jul 27 2008

Mathematica

f[ n_Integer ] := f[ n ]=If[ n>7, f[ n-1 ]+f[ n-7 ], 1 ]
Table[Sum[Binomial[n-6*i, i], {i, 0, n/7}], {n, 0, 45}] (* Adi Dani, Jun 25 2011 *)
LinearRecurrence[{1, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)

PARI

x='x+O('x^66); Vec(1/(1-(x+x^7))) /* Joerg Arndt, Jun 25 2011 */

Formula

G.f.: 1/(1-x-x^7). - Simon Plouffe in his 1992 dissertation.

For positive integers n and k such that k <= n <= 7*k, and 6 divides n-k, define c(n,k) = binomial(k,(n-k)/6), and c(n,k)=0, otherwise. Then, for n >= 1, a(n) = Sum_{k=1..n} c(n,k). - Milan Janjic, Dec 09 2011

Apparently a(n) = hypergeometric([1/7-n/7, 2/7-n/7, 3/7-n/7, 4/7-n/7, 5/7-n/7, 6/7-n/7, -n/7], [1/6-n/6, 1/3-n/6, 1/2-n/6, 2/3-n/6, 5/6-n/6, -n/6], -7^7/6^6) for n >= 36. - Peter Luschny, Sep 19 2014

Extensions

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000