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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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

%I M1108 N0423

%S 0,0,0,1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536,10671,20569,

%T 39648,76424,147312,283953,547337,1055026,2033628,3919944,7555935,

%U 14564533,28074040,54114452,104308960,201061985,387559437,747044834,1439975216,2775641472

%N 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.

%C 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

%C 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

%C a(n+4) = number of 0-1 sequences of length n that avoid 1111. - _David Callan_, Jul 19 2004

%C 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

%C Number of permutations satisfying -k<=p(i)-i<=r, i=1..n-3, with k=1, r=3. - _Vladimir Baltic_, Jan 17 2005

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

%D 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.

%D J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A000078/b000078.txt">Table of n, a(n) for n = 0..200</a>

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp.307-309

%H Vladimir Baltic, <a href="http://pefmath.etf.rs/vol4num1/AADM-Vol4-No1-119-135.pdf">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H S. A. Corey and Otto Dunkel, <a href="http://www.jstor.org/stable/2299550">Problem 2803</a>, Amer. Math. Monthly, 33 (1926), 229-232.

%H E. Deutsch, <a href="http://www.jstor.org/stable/3219192">Problem 1613: A recursion in four parts</a>, Math. Mag., 75, No. 1, 64-64.

%H M. Feinberg, <a href="http://www.fq.math.ca/Scanned/1-3/feinberg.pdf">Fibonacci-Tribonacci</a>, Fib. Quart. 1(#3) (1963), 71-74.

%H F. T. Howard and Curtis Cooper, <a href="http://www.math-cs.ucmo.edu/~curtisc/articles/howardcooper/genfib4.pdf">Some identities for r-Fibonacci numbers</a>.

%H INRIA Algorithms Project, <a href="http://algo.inria.fr/encyclopedia/">Encyclopedia of Combinatorial Structures 11</a>

%H W. C. Lynch, <a href="http://www.fq.math.ca/Scanned/8-1/lynch.pdf">The t-Fibonacci numbers and polyphase sorting</a>, Fib. Quart., 8 (1970), pp. 6ff.

%H Tony D. Noe and Jonathan Vos Post, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html">Primes in Fibonacci n-step and Lucas n-step Sequences,</a> J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number.</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TetranacciNumber.html">Tetranacci Number.</a>

%H <a href="/index/Rec#order_04">Index to sequences with linear recurrences with constant coefficients</a>, signature (1,1,1,1).

%F a(n) = A001630(n)-a(n-1). - _Henry Bottomley_

%F G.f.: x^3/(1 - x - x^2 - x^3 - x^4).

%F G.f.: x^3 / (1 - x / (1 - x / (1 + x^3 / (1 + x / (1 - x / (1 + x)))))). - _Michael Somos_, May 12 2012

%F 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

%F 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

%F 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

%F 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.

%F 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

%F Starting (1, 2, 4, 8,...) = the INVERT transform of (1, 1, 1, 1, 0, 0, 0,...). - _Gary W. Adamson_, May 13 2013

%F 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

%F a(n) = 2*a(n-1) - a(n-5), n>=5. - _Bob Selcoe_, Jul 06 2014

%p A000078:=-1/(-1+z+z**2+z**3+z**4); # _Simon Plouffe_ in his 1992 dissertation

%p 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

%t CoefficientList[Series[x^3/(1 - x - x^2 - x^3 - x^4), {x, 0, 50}], x]

%t LinearRecurrence[{1, 1, 1, 1}, {0, 0, 0, 1}, 50] (* _Vladimir Joseph Stephan Orlovsky_, May 25 2011 *)

%o (PARI) {a(n) = if( n<0, 0, polcoeff( x^3 / (1 - x - x^2 - x^3 - x^4) + x * O(x^n), n))}

%o (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

%o (Haskell)

%o import Data.List (tails, transpose)

%o a000078 n = a000078_list !! n

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

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

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

%o -- _Reinhard Zumkeller_, Jul 06 2014, Apr 28 2011

%o (Python)

%o A000078 = [0,0,0,1]

%o for n in range(4,100):

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

%o # _Chai Wah Wu_, Aug 20 2014

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

%Y First differences are in A001631.

%Y Cf. A008287 (quadrinomial coefficients).

%K nonn,easy,nice

%O 0,6

%A _N. J. A. Sloane_, Apr 30 1991

%E Definition augmented (with 4 initial terms) by _Daniel Forgues_, Dec 02 2009

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 September 17 13:37 EDT 2014. Contains 246846 sequences.