|
| |
|
|
A000078
|
|
Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) with a(0)=a(1)=a(2)=0, a(3)=1.
(Formerly M1108 N0423)
|
|
57
| |
|
|
0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, 1055026, 2033628, 3919944, 7555935, 14564533, 28074040, 54114452, 104308960, 201061985, 387559437, 747044834, 1439975216, 2775641472
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,6
|
|
|
COMMENTS
| a(n)=number of compositions of n-3 with no part greater than 4. Example: a(7)=8 because we have 1+1+1+1=2+1+1=1+2+1=3+1=1+1+2=2+2=1+3=4. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 10 2004
a(n+4)=number of 0-1 sequences of length n that avoid 1111. - David Callan (callan(AT)stat.wisc.edu), Jul 19 2004
a(n)=number of matchings in the graph obtained by a zig-zag triangulation of a convex (n-3)-gon. Example: a(8)=15 because in the triangulation of the convex pentagon ABCDEA with diagonals AD and AC we have 15 matchings: the empty set, seven singletons and {AB,CD},{AB,DE},{BC,AD},{BC,DE},{BC,EA},{CD,EA} and {DE,AC}. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 25 2004
Number of permutations satisfying -k<=p(i)-i<=r, i=1..n-3, with k=1, r=3. - Vladimir Baltic (baltic(AT)matf.bg.ac.yu), Jan 17 2005
|
|
|
REFERENCES
| E. Deutsch, Problem 1613, Math. Mag., 75, No. 1, 64-64.
M. Feinberg, Fibonacci-Tribonacci, Fib. Quart. 1(#3) (1963), 71-74.
F. T. Howard and Curtis Cooper, Some identities for r-Fibonacci numbers, http://www.math-cs.ucmo.edu/~curtisc/articles/howardcooper/genfib4.pdf.
W. C. Lynch, The t-Fibonacci numbers and polyphase sorting, Fib. Quart., 8 (1970), pp. 6ff.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.4.
Problem 2803, Amer. Math. Monthly, 33 (1926), 229-232.
J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.
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, Fxtbook, pp.307-309
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 11
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
Eric Weisstein's World of Mathematics, Tetranacci Number.
Index entries for sequences related to linear recurrences with constant coefficients
|
|
|
FORMULA
| a(n) =A001630(n)-a(n-1) - Henry Bottomley
G.f.: x^3/(1 - x - x^2 - x^3 - x^4).
a(n) = term (1,4) in the 4x4 matrix [1,1,0,0; 1,0,1,0; 1,0,0,1; 1,0,0,0]^n. - Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jun 12 2008
Another form of the g.f.: f(z)=(z^3-z^4)/(1-2*z+z^5) then a(n)=sum((-1)^i*binomial(n-3-4*i,i)*2^(n-3-5*i),i=0..floor((n-3)/5))-sum((-1)^i*binomial(n-4-4*i,i)*2^(n-4-5*i),i=0..floor((n-4)/5)) with natural convention sum(alpha(i),i=m..n)=0 for m>n. [From Richard Choulet (richardchoulet(AT)yahoo.fr), Feb 22 2010]
a(n)=sum(k=1..n, sum(i=k..n mod(5*k-i,4)=0 binomial(k,(5*k-i)/4)*(-1)^((i-k)/4)*binomial(n-i+k-1,k-1))), n>0. [From Kruchinin Vladimir (kru(AT)ie.tusur.ru), Aug 18 2010]
sum_{k=0..3*n} A000078(k+b)*A008287(n,k) = A000078(4*n+b), b>=0.
|
|
|
MAPLE
| A000078:=-1/(-1+z+z**2+z**3+z**4); [S. Plouffe in his 1992 dissertation.]
a := n -> (Matrix([[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1], [1, 0, 0, 0]])^n)[1, 4]; seq ((a(n)), n=0..50); - Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jun 12 2008
|
|
|
MATHEMATICA
| CoefficientList[Series[x^3/(1 - x - x^2 - x^3 - x^4), {x, 0, 50}], x]
LinearRecurrence[{1, 1, 1, 1}, {0, 0, 0, 1}, 50] (* From Vladimir Joseph Stephan Orlovsky, May 25 2011 *)
|
|
|
PROG
| (PARI) a(n)=if(n<0, 0, polcoeff(x^3/(1-x-x^2-x^3-x^4)+x*O(x^n), n))
(Maxima) a(n):=sum(sum(if mod(5*k-i, 4)>0 then 0 else binomial(k, (5*k-i)/4)*(-1)^((i-k)/4)*binomial(n-i+k-1, k-1), i, k, n), k, 1, n); [From Kruchinin Vladimir (kru(AT)ie.tusur.ru), Aug 18 2010]
(Haskell)
import Data.List (zipWith4)
a000078 n = a000078_list !! n
a000078_list = 0 : 0 : 0 : 1 : zipWith4 (\a b c d -> a + b + c + d)
a000078_list
(tail a000078_list)
(drop 2 a000078_list)
(drop 3 a000078_list) -- Reinhard Zumkeller, Apr 28 2011
|
|
|
CROSSREFS
| Row 4 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).
First differences are in A001631.
Sequence in context: A001383 A108564 A066369 * A176503 A034338 A166861
Adjacent sequences: A000075 A000076 A000077 * A000079 A000080 A000081
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Henry Bottomley (se16(AT)btinternet.com), Oct 09 2000
Definition augmented (with 4 initial terms) by Daniel Forgues (squid(AT)zensearch.com), Dec 02 2009
|
| |
|
|
