|
| |
|
|
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.
(Formerly M1122 N0429)
|
|
56
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,7
|
|
|
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) = number of compositions of n-4 with no part greater than 5. Example: a(12)=61 because we have 61 compositions of 8: 8 = 1+1+1+1+1+1+1+1 = 2+1+1+1+1+1+1 = ... = 2+2+1+1+1+1 = ... = 2+2+2+1+1 = ... = 2+2+2+2 = 3+1+1+1+1+1 = ... = 3+2+1+1+1 = ... = 3+2+2+1 = ... = 3+3+1+1 = ... = 3+3+2 = ... = 4+1+1+1+1 = ... = 4+2+1+1 = ... = 4+2+2 = ... = 4+3+1 = ... = 5+1+1+1 = ... = 5+2+1 = ... = 5+3 = 3+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
|
|
|
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
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
Martin Burtscher, Igor Szczyrba, 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.
O. Deveci, Y. Akuzum, E. Karaduman, O. Erdag, The Cyclic Groups via Bezout Matrices, Journal of Mathematics Research, Vol. 7, No. 2, 2015, pp. 34-41.
G. P. B. Dresden, 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.
T.-X. 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.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 12
Vladimir Victorovich Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
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.
Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.
H. 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.
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)
|
|
|
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} A001591(k+b)*A035343(n,k) = A001591(5*n+b), b >= 0.
a(n) = 2*a(n-1) - a(n-6) with initial values 0, 0, 0, 0, 1, 1. - Vincenzo Librandi, Dec 19 2010
|
|
|
EXAMPLE
|
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 + ...
|
|
|
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
a:=taylor((z^4-z^5)/(1-2*z+z^6), z=0, 51); for p from 0 to 50 do j(p):=coeff(a, z, p):od :seq(j(p), p=0..50); for n from 0 to 50 do k(n):=sum((-1)^i*binomial(n-4-5*i, i)*2^(n-4-6*i), i=0..floor((n-4)/6))-sum((-1)^i*binomial(n-5-5*i, i)*2^(n-5-6*i), i=0..floor((n-5)/6)):od:seq(k(n), n=0..50); # Richard Choulet, Feb 22 2010
|
|
|
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 *)
a[n_] := a[n] = Sum[Sum[Binomial[k, r]*Sum[Binomial[r, m]*Sum[Binomial[m, j]*Binomial[j, n - 4 - m - k - j - r], {j, 0, m}], {m, 0, r}], {r, 0, k}], {k, 1, n - 4}]; a[4] = 1; Table[a[n], {n, 0, 37}] (* L. Edson Jeffery, Jul 18 2014, after Vladimir Kruchinin's formula *)
|
|
|
PROG
|
(Maxima) a(n):=sum(sum(binomial(k, r)*sum(binomial(r, m)*sum(binomial(m, j)*binomial(j, n-m-k-j-r), j, 0, m), m, 0, r), r, 0, k), k, 1, n); /* Vladimir Kruchinin, Aug 30 2010 */
(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
(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 */
|
|
|
CROSSREFS
|
Row 5 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).
Cf. A106303 (Pisano period lengths)
Cf. A035343 (pentanomial coefficients).
Sequence in context: A192656 A128761 A239557 * A194628 A003240 A280543
Adjacent sequences: A001588 A001589 A001590 * A001592 A001593 A001594
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
STATUS
|
approved
|
| |
|
|
