login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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; text; 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, Mar 10 2004

In other words, a(n) is the number of ways of putting stamps in one row on an envelope using stamps of denominations 1, 2, 3 and 4 cents so as to total n-3 cents [Polya-Szego]. - N. J. A. Sloane, Jul 28 2012

a(n+4)=number of 0-1 sequences of length n that avoid 1111. - David Callan, 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, Dec 25 2004

Number of permutations satisfying -k<=p(i)-i<=r, i=1..n-3, with k=1, r=3. - Vladimir Baltic, 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.

G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1, Problems 3 and 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

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

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

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.

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).

G.f.: x^3 / (1 - x / (1 - x / (1 + x^3 / (1 + x / (1 - x / (1 + x)))))). - Michael Somos, May 12 2012

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, 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. [Richard Choulet, 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. [Vladimir Kruchinin, Aug 18 2010]

sum_{k=0..3*n} A000078(k+b)*A008287(n,k) = A000078(4*n+b), b>=0.

G.f.: x^3*(1 + x*(G(0)-1)/(x+1)) where G(k) =  1 + (1+x+x^2+x^3)/(1-x/(x+1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 26 2013

Starting (1, 2, 4, 8,...) = the INVERT transform of (1, 1, 1, 1, 0, 0, 0,...). [Gary W. Adamson, May 13 2013]

EXAMPLE

x^3 + x^4 + 2*x^5 + 4*x^6 + 8*x^7 + 15*x^8 + 29*x^9 + 56*x^10 + ...

MAPLE

A000078:=-1/(-1+z+z**2+z**3+z**4); [Simon Plouffe in his 1992 dissertation.]

a:= n-> (<<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, 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]  (* 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); [Vladimir Kruchinin, 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: A108564 A066369 A239555 * A176503 A217777 A034338

Adjacent sequences:  A000075 A000076 A000077 * A000079 A000080 A000081

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from Henry Bottomley, Oct 09 2000

Definition augmented (with 4 initial terms) by Daniel Forgues, Dec 02 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 17 15:01 EDT 2014. Contains 240645 sequences.