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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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

%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 December 20 17:21 EST 2014. Contains 252272 sequences.