|
%I M0507 #176 Sep 27 2023 16:11:50
%S 1,1,1,1,1,2,3,4,5,6,8,11,15,20,26,34,45,60,80,106,140,185,245,325,
%T 431,571,756,1001,1326,1757,2328,3084,4085,5411,7168,9496,12580,16665,
%U 22076,29244,38740,51320,67985,90061,119305,158045,209365,277350,367411,486716,644761
%N a(n) = a(n-1) + a(n-5); a(0) = ... = a(4) = 1.
%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(binomial(n-(m-1)*i, i), i=0..n/m). 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 Also counts ordered partitions such that no part is less than 5. For example, a(12) = a(11) + a(7) where a(7) counts 11,6+5 and 5+6 and a(11) counts 15,10+5, 9+6,8+7,7+8,6+9,5+10 and 5+5+5. Thus a(12) = 3 + 8 = 11. a(12) counts 16,11+5,10+6,9+7,8+8,7+9,6+10 and 6+5+5 but also 5+11,5+6+5 and 5+5+6. Similar results hold for the other sequences formed by a(n) = a(n-1) + a(n-k). - _Alford Arnold_, Aug 06 2003
%C Number of compositions of n into parts 1 and 5. - _Joerg Arndt_, Jun 25 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>=5, 2*a(n-5) equals the number of 2-colored compositions of n with all parts >= 5, such that no adjacent parts have the same color. - _Milan Janjic_, Nov 27 2011
%C a(n+4) equals the number of binary words of length n having at least 4 zeros between every two successive ones. - _Milan Janjic_, Feb 07 2015
%C Number of tilings of a 5 X n rectangle with 5 X 1 pentominoes. - _M. Poyraz Torcuk_, Mar 26 2022
%D A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 119.
%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="/A003520/b003520.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 Roland Bacher, <a href="https://arxiv.org/abs/1704.02234">On the number of perfect lattices</a>, arXiv:1704.02234 [math.NT], 2017. See Section 6.
%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 9.
%H Bruce M. Boman, <a href="https://www.fq.math.ca/Papers1/58-5/boman.pdf">Geometric Capitulum Patterns Based on Fibonacci p-Proportions</a>, Fibonacci Quart. 58 (2020), no. 5, 91-102.
%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,4,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 Brian Hopkins and Hua Wang, <a href="https://arxiv.org/abs/2003.05291">Restricted Color n-color Compositions</a>, arXiv:2003.05291 [math.CO], 2020.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=378">Encyclopedia of Combinatorial Structures 378</a>
%H T. G. Lewis, B. J. Smith and M. Z. Smith, <a href="http://www.fq.math.ca/Scanned/14-1/lewis.pdf">Fibonacci sequences and money management</a>, Fib. Quart., 14 (1976), 37-41.
%H Sergey Kirgizov, <a href="https://arxiv.org/abs/2201.00782">Q-bonacci words and numbers</a>, arXiv:2201.00782 [math.CO], 2022.
%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings</a>, arXiv:1311.6135 [math.CO], 2013, Table 33.
%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.4.
%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 Denis Neiter and Amsha Proag, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Proag/proag3.html">Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
%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 E. Wilson, <a href="http://www.anaphoria.com/meruone.PDF">The Scales of Mt. Meru</a>
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,1)
%F G.f.: 1/(1-x-x^5) = 1/((1-x+x^2)(1-x^2-x^3)).
%F a(n) = Sum_{j=0..(n-1)/4} binomial(n-1+(-4)*j,j).
%F For n>5, a(n) = floor( d*c^n + 1/2) where c is the positive real root of x^5-x^4-1 and d is the positive real root of 161*x^3-23*x^2-12*x-1 ( c=1.32471795724474602... and d=0.3811571478326847...) - _Benoit Cloitre_, Nov 30 2002
%F a(n) = term (1,1) in the 5 X 5 matrix [1,1,0,0,0; 0,0,1,0,0; 0,0,0,1,0; 0,0,0,0,1; 1,0,0,0,0]^n. - _Alois P. Heinz_, Jul 27 2008
%F For positive integers n and k such that k <= n <= 5*k, and 4 divides n-k, define c(n,k) = binomial(k,(n-k)/4), and c(n,k)=0, otherwise. Then, for n >= 1, a(n) = sum(c(n,k), k=1..n). - _Milan Janjic_, Dec 09 2011
%F Apparently a(n) = hypergeometric([-1/5*n, 1/5-1/5*n, 2/5-1/5*n, 3/5-1/5*n, 4/5-1/5*n], [-1/4*n, 1/4-1/4*n, 1/2-1/4*n, 3/4-1/4*n], -5^5/4^4) for n>=16. - _Peter Luschny_, Sep 18 2014
%F 7*a(n) = A117373(n+4) +5*b(n) +4*b(n-1) +b(n-2) where b(n) = A182097(n). - _R. J. Mathar_, Aug 07 2017
%p a[0]:=1:a[1]:=1:a[2]:=1:a[3]:=1:a[4]:=1:for n from 5 to 60 do a[n]:=a[n-1]+a[n-5] od:seq(a[n],n=0..60);
%p with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 4)}, unlabeled]: seq(count(SeqSetU, size=j), j=5..55); # _Zerinvary Lajos_, Oct 10 2006
%p A003520:=-1/(z**3+z**2-1)/(z**2-z+1); # _Simon Plouffe_ in his 1992 dissertation
%p ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 4)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=4..54); # _Zerinvary Lajos_, Mar 26 2008
%p M := Matrix(5, (i,j)-> if j=1 then [1, 0, 0, 0, 1][i] 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 a[0] = a[1] = a[2] = a[3] = a[4] = 1; a[n_] := a[n] = a[n - 1] + a[n - 5]; Table[ a[n], {n, 0, 49}] (* _Robert G. Wilson v_, Dec 09 2004 *)
%t CoefficientList[Series[1/(1 - x - x^5), {x, 0, 51}], x] (* _Zerinvary Lajos_, Mar 29 2007 *)
%t LinearRecurrence[{1, 0, 0, 0, 1}, {1, 1, 1, 1, 1}, 80] (* _Vladimir Joseph Stephan Orlovsky_, Feb 16 2012 *)
%t nxt[{a_,b_,c_,d_,e_}]:={b,c,d,e,e+a}; NestList[nxt,{1,1,1,1,1},50][[;;,1]] (* _Harvey P. Dale_, Sep 27 2023 *)
%o (Maxima) a(n):=sum(binomial(n-1+(-4)*j,j),j,0,(n-1)/4); /* _Vladimir Kruchinin_, May 23 2011 */
%o (PARI) my(x='x+O('x^66)); Vec(x/(1-(x+x^5))) /* _Joerg Arndt_, Jun 25 2011 */
%Y Apart from initial terms, same as A017899.
%Y Cf. A000045, A000079, A000930, A003269, A005708, A005709, A005710, A005711.
%K nonn,easy
%O 0,6
%A _N. J. A. Sloane_
%E Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
|
