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

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

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

Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

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.

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, 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

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

S. A. Corey and Otto Dunkel, Problem 2803, Amer. Math. Monthly, 33 (1926), 229-232.

E. Deutsch, Problem 1613: A recursion in four parts, 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.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 11

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, 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 to sequences with linear recurrences with constant coefficients, signature (1,1,1,1).

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 4 X 4 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} a(k+b) * A008287(n,k) = a(4*n+b), b>=0 ("quadrinomial transform"). - N. J. A. Sloane, Nov 10 2010.

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

a(n) ~ c*r^n, where c=0.079077767399388561146007, and r=1.92756197548292530426195 (One of the roots of the g.f. denominator polynomial is 1/r). - Fung Lam, Apr 29 2014

a(n) = 2*a(n-1) - a(n-5), n>=5. - Bob Selcoe, Jul 06 2014

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 (tails, transpose)

a000078 n = a000078_list !! n

a000078_list = 0 : 0 : 0 : f [0, 0, 0, 1] where

   f xs = y : f (y:xs) where

     y = sum $ head $ transpose $ take 4 $ tails xs

-- Reinhard Zumkeller, Jul 06 2014, Apr 28 2011

(Python)

A000078 = [0, 0, 0, 1]

for n in range(4, 100):

....A000078.append(A000078[n-1]+A000078[n-2]+A000078[n-3]+A000078[n-4])

# Chai Wah Wu, Aug 20 2014

CROSSREFS

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

First differences are in A001631.

Cf. A008287 (quadrinomial coefficients).

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, Apr 30 1991

EXTENSIONS

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 October 26 05:34 EDT 2014. Contains 248568 sequences.