A001591 Pentanacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) + a(n-5), a(0)=a(1)=a(2)=a(3)=0, a(4)=1.

0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519, 203513, 400096, 786568, 1546352, 3040048, 5976577, 11749641, 23099186, 45411804, 89277256, 175514464, 345052351, 678355061, 1333610936, 2621810068

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Number of permutations satisfying -k <= p(i) - i <= r, i=1..n-4, with k=1, r=4. - Vladimir Baltic, Jan 17 2005

a(n) is the number of compositions of n-4 with no part greater than 5. - Vladimir Baltic, Jan 17 2005

The pentanomial (A035343(n)) transform of a(n) is a(5n+4), n >= 0. - Bob Selcoe, Jun 10 2014

a(n) is the number of ways to tile a strip of length n-4 with squares, dominoes, trominoes (of length 3), and rectangles with length 4 (tetraminoes) and length 5 (pentaminoes). - Wajdi Maaloul, Jun 21 2022

Examples

			n=2: a(14) = (1*1 + 2*1 + 3*2 + 4*4 + 5*8 + 4*16 + 3*31 + 2*61 + 1*120) = 464. - _Bob Selcoe_, Jun 10 2014
G.f. = x^4 + x^5 + 2*x^6 + 4*x^7 + 8*x^8 + 16*x^9 + 31*x^10 + 120*x^11 + ...
		

References

• Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• 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..200
• Abdullah Açikel, Amrouche Said, Hacene Belbachir, and Nurettin Irmak, On k-generalized Lucas sequence with its triangle, Turkish J. Math. (2023) Vol. 47, No. 4, Art. 6, 1129-1143. See p. 1130.
• Tomás Aguilar-Fraga, Jennifer Elder, Rebecca E. Garcia, Kimberly P. Hadaway, Pamela E. Harris, Kimberly J. Harry, Imhotep B. Hogan, Jakeyl Johnson, Jan Kretschmann, Kobe Lawson-Chavanu, J. Carlos Martínez Mori, Casandra D. Monroe, Daniel Quiñonez, Dirk Tolson III, and Dwight Anderson Williams II, Interval and L-interval Rational Parking Functions, arXiv:2311.14055 [math.CO], 2023. See p. 14.
• Joerg Arndt, Matters Computational (The Fxtbook), pp. 307-309.
• Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135.
• Paul Barry, The Gamma-Vectors of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1804.05027 [math.CO], 2018.
• Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
• P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
• Ömür Deveci, Yesim Akuzum, Erdal Karaduman, and Ozgur Erdag, The Cyclic Groups via Bezout Matrices, Journal of Mathematics Research, Vol. 7, No. 2, 2015, pp. 34-41.
• Ömür Deveci, Zafer Adıgüzel, and Taha Doğan, On the Generalized Fibonacci-circulant-Hurwitz numbers, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 1, 179-190.
• G. P. B. Dresden and Z. Du, A Simplified Binet Formula for k-Generalized Fibonacci Numbers, J. Int. Seq. 17 (2014) # 14.4.7.
• I. Flores, k-Generalized Fibonacci numbers, Fib. Quart., 5 (1967), 258-266.
• Taras Goy and Mark Shattuck, Some Toeplitz-Hessenberg Determinant Identities for the Tetranacci Numbers, J. Int. Seq., Vol. 23 (2020), Article 20.6.8.
• Tian-Xiao He, Impulse Response Sequences and Construction of Number Sequence Identities, J. Int. Seq. 16 (2013) #13.8.2.
• V. E. Hoggatt, Jr. and M. Bicknell, Diagonal sums of generalized Pascal triangles, Fib. Quart., 7 (1969), 341-358, 393.
• F. T. Howard and Curtis Cooper, Some identities for r-Fibonacci numbers, Fibonacci Quart. 49 (2011), no. 3, 231-243.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 12
• Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.
• Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.
• Vladimir Victorovich Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
• Michel Mollard, p-th order generalized Fibonacci cubes and maximal cubes in Fibonacci p-cubes, arXiv:2507.16387 [math.CO], 2025. See p. 3.
• Elisa Heinrich Mora and Noah A. Rosenberg, An nth-cousin mating model and the n-anacci numbers, arXiv:2506.16577 [q-bio.PE], 2025.
• László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
• Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4.
• 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
• Helmut Prodinger, Counting Palindromes According to r-Runs of Ones Using Generating Functions, J. Int. Seq. 17 (2014) # 14.6.2, odd length middle 0, r=4.
• B. Sivakumar and V. James, A Notes on Matrix Sequence of Pentanacci Numbers and Pentanacci Cubes, Communications in Mathematics and Applications (2022) Vol. 13, Iss. 2, 603-611.
• Yüksel Soykan, On A Generalized Pentanacci Sequence, Asian Research Journal of Mathematics (2019) Vol. 14, No. 3, 1-9.
• Yüksel Soykan, Sum Formulas for Generalized Fifth-Order Linear Recurrence Sequences, Journal of Advances in Mathematics and Computer Science (2019) Vol. 34, No. 5, 1-14.
• Kai Wang, Identities for generalized enneanacci numbers, Generalized Fibonacci Sequences (2020).
• Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
• Eric Weisstein's World of Mathematics, Pentanacci Number
• Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1).

Crossrefs

Row 5 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).

Cf. A106303 (Pisano period lengths).

Cf. A035343 (pentanomial coefficients).

Cf. A074048, A123127, A123126, A074062.

Programs

Magma

a:=[0,0,0,0,1]; [n le 5 select a[n] else Self(n-1) + Self(n-2) + Self(n-3) + Self(n-4) + Self(n-5): n in [1..40]]; // Marius A. Burtea, Oct 03 2019

Maple

g:=1/(1-z-z^2-z^3-z^4-z^5): gser:=series(g, z=0, 49): seq((coeff(gser, z, n)), n=-4..32); # Zerinvary Lajos, Apr 17 2009
# second Maple program:
a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>, <0|0|0|0|1>, <1|1|1|1|1>>^n)[1, 5]:
seq(a(n), n=0..44);  # Alois P. Heinz, Apr 09 2021

Mathematica

CoefficientList[Series[x^4/(1 - x - x^2 - x^3 - x^4 - x^5), {x, 0, 50}], x]
a[0] = a[1] = a[2] = a[3] = 0; a[4] = a[5] = 1; a[n_] := a[n] = 2 a[n - 1] - a[n - 6]; Array[a, 37, 0]
LinearRecurrence[{1, 1, 1, 1, 1}, {0, 0, 0, 0, 1}, 50] (* Vladimir Joseph Stephan Orlovsky, May 25 2011 *)

Maxima

a(n):=mod(floor(10^((n-4)*(n+1))*10^(5*(n+1))*(10^(n+1)-1)/(10^(6*(n+1))-2*10^(5*(n+1))+1)),10^n); /* Tani Akinari, Apr 10 2014 */

PARI

a=vector(100);a[4]=a[5]=1;for(n=6,#a,a[n]=a[n-1]+a[n-2]+a[n-3]+a[n-4]+a[n-5]);concat(0, a) \\ Charles R Greathouse IV, Jul 15 2011

PARI

A001591(n,m=5)=(matrix(m,m,i,j,i==j-1||i==m)^n)[1,m] \\ M. F. Hasler, Apr 20 2018

PARI

a(n)= {my(x='x, p=polrecip(1 - x - x^2 - x^3 - x^4 - x^5)); polcoef(lift(Mod(x, p)^n), 4); }
vector(41, n, a(n-1)) \\ Joerg Arndt, May 16 2021

Python

def pentanacci():
    a, b, c, d, e = 0, 0, 0, 0, 1
    while True:
        yield a
        a, b, c, d, e = b, c, d, e, a + b + c + d + e
f = pentanacci()
print([next(f) for  in range(100)]) # _Reza K Ghazi Apr 09 2021

Formula

G.f.: x^4/(1 - x - x^2 - x^3 - x^4 - x^5). - Simon Plouffe in his 1992 dissertation.

G.f.: Sum_{n >= 0} x^(n+4) * (Product_{k = 1..n} (k + k*x + k*x^2 + k*x^3 + x^4)/(1 + k*x + k*x^2 + k*x^3 + k*x^4)). - Peter Bala, Jan 04 2015

Another form of the g.f.: f(z) = (z^4-z^5)/(1-2*z+z^6); then a(n) = Sum_{i=0..floor((n-4)/6)} ((-1)^i*binomial(n-4-5*i,i)*2^(n-4-6*i)) - Sum_{i=0..floor((n-5)/6)} ((-1)^i*binomial(n-5-5*i,i)*2^(n-5-6*i)) with convention Sum_{i=m..n} alpha(i) = 0 for m > n. - Richard Choulet, Feb 22 2010

a(n) = Sum_{k=1..n} (Sum_{r=0..k} (binomial(k,r) * Sum_{m=0..r} (binomial(r,m) * Sum_{j=0..m} (binomial(m,j)*binomial(j,n-m-k-j-r))))), n > 0. - Vladimir Kruchinin, Aug 30 2010

Sum_{k=0..4*n} a(k+b)*A035343(n,k) = a(5*n+b), b >= 0.

a(n) = 2*a(n-1) - a(n-6). - Vincenzo Librandi, Dec 19 2010

a(n) = (Sum_{i=0..n-1} a(i)*A074048(n-i))/(n-4) for n > 4. - Greg Dresden and Advika Srivastava, Oct 01 2019

For k>0 and n>0, a(n+5*k) = A074048(k)*a(n+4*k) - A123127(k-1)*a(n+3*k) + A123126(k-1)*a(n+2*k) - A074062(k)*a(n+k) + a(n). - Kai Wang, Sep 06 2020

lim n->oo a(n)/a(n-1) = A103814. - R. J. Mathar, Mar 11 2024