|
%I M0483 #118 Dec 22 2023 11:03:24
%S 1,1,1,1,1,1,1,1,2,3,4,5,6,7,8,9,11,14,18,23,29,36,44,53,64,78,96,119,
%T 148,184,228,281,345,423,519,638,786,970,1198,1479,1824,2247,2766,
%U 3404,4190,5160,6358,7837,9661,11908,14674,18078,22268,27428,33786,41623
%N a(n) = a(n-1) + a(n-8), with a(i) = 1 for i = 0..7.
%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 >= 8, a(n-8) = number of compositions of n in which each part is >= 8. - _Milan Janjic_, Jun 28 2010
%C Number of compositions of n into parts 1 and 8. - _Joerg Arndt_, Jun 24 2011
%C a(n+7) equals the number of binary words of length n having at least 7 zeros between every two successive ones. - _Milan Janjic_, Feb 09 2015
%D P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194.
%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="/A005710/b005710.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 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 Jia Huang, <a href="https://arxiv.org/abs/1812.11010">Compositions with restricted parts</a>, arXiv:1812.11010 [math.CO], 2018.
%H D. Kleitman, <a href="http://www.jstor.org/stable/2324158">Solution to Problem E3274</a>, Amer. Math. Monthly, 98 (1991), 958-959.
%H A. O. Munagi, <a href="https://www.emis.de/journals/INTEGERS/papers/m60/m60.Abstract.html">Euler-type identities for integer compositions via zig-zag graphs</a>, Integers 12 (2012), Paper No. A60, 10 pp.
%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 D. Newman, <a href="http://www.jstor.org/stable/2322766">Problem E3274</a>, Amer. Math. Monthly, 95 (1988), 555.
%H Djamila Oudrar and Maurice Pouzet, <a href="https://arxiv.org/abs/2312.05913">Ordered structures with no finite monomorphic decomposition. Application to the profile of hereditary classes</a>, arXiv:2312.05913 [math.CO], 2023. See p. 18.
%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 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=381">Encyclopedia of Combinatorial Structures 381</a>
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,0,0,0,1).
%F G.f.: 1/(1-x-x^8).
%F For positive integers n and k such that k <= n <= 8*k, and 7 divides n-k, define c(n,k) = binomial(k,(n-k)/7), and c(n,k) = 0, otherwise. Then, for n >= 1, a(n-1) = Sum_{k=1..n} c(n,k). - _Milan Janjic_, Dec 09 2011
%F Apparently a(n) = hypergeometric([1/8-n/8, 1/4-n/8, 3/8-n/8, 1/2-n/8, 5/8-n/8, 3/4-n/8, 7/8-n/8, -n/8], [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], -8^8/7^7) for n >= 49. - _Peter Luschny_, Sep 19 2014
%p A005710:=-1/(-1+z+z**8); # _Simon Plouffe_ in his 1992 dissertation.
%p ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 7)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=7..62); # _Zerinvary Lajos_, Mar 26 2008
%p M := Matrix(8, (i,j)-> if j=1 and member(i,[1,8]) then 1 elif (i=j-1) then 1 else 0 fi); a := n -> (M^(n))[1,1]; seq(a(n), n=0..55); # _Alois P. Heinz_, Jul 27 2008
%t LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, 80] (* _Vladimir Joseph Stephan Orlovsky_, Feb 16 2012 *)
%t CoefficientList[Series[1/(1-x-x^8),{x,0,60}],x] (* _Harvey P. Dale_, Jun 14 2016 *)
%o (PARI) x='x+O('x^66); Vec(x/(1-(x+x^8))) /* _Joerg Arndt_, Jun 25 2011 */
%Y Cf. A000045, A000079, A000930, A003269, A003520, A005708, A005709, A005711.
%K nonn,easy
%O 0,9
%A _N. J. A. Sloane_
%E Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
|
