A005709 - OEIS

%I M0492 #111 Sep 11 2024 00:39:11

%S 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,

%T 168,211,264,330,413,518,651,819,1030,1294,1624,2037,2555,3206,4025,

%U 5055,6349,7973,10010,12565,15771,19796,24851

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

%C 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.

%C For n >= 7, a(n-7) is the number of compositions of n in which each part is >=7. - _Milan Janjic_, Jun 28 2010

%C Number of compositions of n into parts 1 and 7. - _Joerg Arndt_, Jun 24 2011

%C 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

%C Number of tilings of a 7 X n rectangle with 7 X 1 heptominoes. - _M. Poyraz Torcuk_, Feb 26 2022

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

%H T. D. Noe, <a href="/A005709/b005709.txt">Table of n, a(n) for n=0..500</a>

%H Mudit Aggarwal and Samrith Ram, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Ram/ram3.html">Generating Functions for Straight Polyomino Tilings of Narrow Rectangles</a>, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.

%H Michael A. Allen, <a href="https://arxiv.org/abs/2209.01377">On a Two-Parameter Family of Generalizations of Pascal's Triangle</a>, arXiv:2209.01377 [math.CO], 2022.

%H Michael A. Allen, <a href="https://arxiv.org/abs/2409.00624">Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings</a>, arXiv:2409.00624 [math.CO], 2024. See p. 18.

%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3, Example 10.

%H P. Chinn and S. Heubach, <a href="/A005710/a005710.pdf">(1, k)-compositions</a>, Congr. Numer. 164 (2003), 183-194. [Local copy]

%H E. Di Cera and Y. Kong, <a href="https://doi.org/10.1016/S0301-4622(96)02178-3">Theory of multivalent binding in one and two-dimensional lattices</a>, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.

%H I. M. Gessel and Ji Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Gessel/gessel6.html">Compositions and Fibonacci identities</a>, J. Int. Seq. 16 (2013) 13.4.5.

%H R. K. Guy, <a href="/A004001/a004001_2.pdf">Letter to N. J. A. Sloane with attachment, 1988</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=380">Encyclopedia of Combinatorial Structures 380</a>

%H R. J. Mathar, <a href="http://arxiv.org/abs/1609.03964">Tiling n x m rectangles with 1 x 1 and s x s squares</a>, arXiv:1609.03964 [math.CO], 2016, Section 4.6.

%H Augustine O. Munagi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Munagi/munagi10.html">Integer Compositions and Higher-Order Conjugation</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.

%H David Newman, <a href="https://www.jstor.org/stable/2322766">Problem E3274</a>, Amer. Math. Monthly, 95 (1988), 555.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,0,0,1).

%F G.f.: 1/(1-x-x^7). - _Simon Plouffe_ in his 1992 dissertation.

%F 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

%F 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

%p A005709 := proc(n) option remember; if n <=6 then 1; else A005709(n-1)+A005709(n-7); fi; end;

%p 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

%p 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

%p 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

%t f[ n_Integer ] := f[ n ]=If[ n>7, f[ n-1 ]+f[ n-7 ], 1 ]

%t Table[Sum[Binomial[n-6*i, i], {i, 0, n/7}], {n, 0, 45}] (* _Adi Dani_, Jun 25 2011 *)

%t LinearRecurrence[{1, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1}, 80] (* _Vladimir Joseph Stephan Orlovsky_, Feb 16 2012 *)

%o (PARI) x='x+O('x^66); Vec(1/(1-(x+x^7))) /* _Joerg Arndt_, Jun 25 2011 */

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

%K nonn,easy

%O 0,8

%A _N. J. A. Sloane_

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