login
a(n) = a(n-1) + a(n-6), with a(i) = 1 for i = 0..5.
(Formerly M0496)
37

%I M0496 #143 Sep 11 2024 00:39:01

%S 1,1,1,1,1,1,2,3,4,5,6,7,9,12,16,21,27,34,43,55,71,92,119,153,196,251,

%T 322,414,533,686,882,1133,1455,1869,2402,3088,3970,5103,6558,8427,

%U 10829,13917,17887,22990,29548,37975,48804,62721,80608,103598,133146,171121,219925,282646

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

%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>=6, a(n-6) = number of compositions of n in which each part is >=6. - _Milan Janjic_, Jun 28 2010

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

%C The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=6, 2*a(n-6) equals the number of 2-colored compositions of n with all parts >=6, such that no adjacent parts have the same color. - _Milan Janjic_, Nov 27 2011

%C a(n+5) equals the number of binary words of length n having at least 5 zeros between every two successive ones. - _Milan Janjic_, Feb 07 2015

%C Number of tilings of a 6 X n rectangle with 6 X 1 hexominoes. - _M. Poyraz Torcuk_, Mar 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="/A005708/b005708.txt">Table of n, a(n) for n=0..500</a>

%H Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, <a href="https://www.emis.de/journals/JIS/VOL22/Shattuck/shattuck13.html">Some New Restricted n-Color Composition Functions</a>, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.

%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 pp. 18, 22.

%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 Bruce M. Boman, Thien-Nam Dinh, Keith Decker, Brooks Emerick, Christopher Raymond, and Gilberto Schleinger, <a href="https://www.fq.math.ca/Papers1/55-5/Boman.pdf">Why do Fibonacci numbers appear in patterns of growth in nature?</a>, in Fibonacci Quarterly, 55(5): pp 30-41, (2017).

%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="http://dx.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 V. C. Harris and C. C. Styles, <a href="http://www.fq.math.ca/Scanned/2-4/harris.pdf">A generalization of Fibonacci numbers</a>, Fib. Quart. 2 (1964) 277-289, sequence u(n,5,1).

%H V. E. Hoggatt, Jr., <a href="/A005676/a005676.pdf">7-page typed letter to N. J. A. Sloane with suggestions for new sequences</a>, circa 1977.

%H Sergey Kirgizov, <a href="https://arxiv.org/abs/2201.00782">Q-bonacci words and numbers</a>, arXiv:2201.00782 [math.CO], 2022.

%H D. Kleitman, <a href="http://www.jstor.org/stable/2324158">Solution to Problem E3274</a>, Amer. Math. Monthly, 98 (1991), 958-959.

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

%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 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=379">Encyclopedia of Combinatorial Structures 379</a>

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

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

%F a(n) = term (1,1) in the 6 X 6 matrix [1,1,0,0,0,0; 0,0,1,0,0,0; 0,0,0,1,0,0; 0,0,0,0,1,0; 0,0,0,0,0,1; 1,0,0,0,0,0]^n. - _Alois P. Heinz_, Jul 27 2008

%F For positive integers n and k such that k <= n <= 6*k and 5 divides n-k, define c(n,k) = binomial(k,(n-k)/5), 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/6-n/6, 1/3-n/6, 1/2-n/6, 2/3-n/6, 5/6-n/6, -n/6], [1/5-n/5, 2/5-n/5, 3/5- n/5, 4/5-n/5, -n/5], -6^6/5^5) for n>=25. - _Peter Luschny_, Sep 19 2014

%p with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 5)}, unlabeled]: seq(count(SeqSetU, size=j), j=6..59); # _Zerinvary Lajos_, Oct 10 2006

%p ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 5)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=5..58); # _Zerinvary Lajos_, Mar 26 2008

%p M := Matrix(6, (i,j)-> if j=1 and member(i,[1,6]) then 1 elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,1]; seq(a(n), n=0..60); # _Alois P. Heinz_, Jul 27 2008

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

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

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

%K nonn,easy

%O 0,7

%A _N. J. A. Sloane_

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