cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A000078 Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) for n >= 4 with a(0) = a(1) = a(2) = 0 and a(3) = 1.

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the 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 [Pólya-Szegő]. - N. J. A. Sloane, Jul 28 2012
a(n+4) is the number of 0-1 sequences of length n that avoid 1111. - David Callan, Jul 19 2004
a(n) is the 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
For n >= 0, a(n+4) is the number of palindromic compositions of 2*n+1 into an odd number of parts that are not multiples of 4. In addition, a(n+4) is also the number of Sommerville symmetric cyclic compositions (= bilaterally symmetric cyclic compositions) of 2*n+1 into an odd number of parts that are not multiples of 4. - Petros Hadjicostas, Mar 10 2018
a(n) is the number of ways to tile a hexagonal double-strip (two rows of adjacent hexagons) containing (n-4) cells with hexagons and double-hexagons (two adjacent hexagons). - Ziqian Jin, Jul 28 2019
The term "tetranacci number" was coined by Mark Feinberg (1963; see A000073). - Amiram Eldar, Apr 16 2021
a(n) is the number of ways to tile a skew double-strip of n-3 cells using squares and all possible "dominos", as seen in Ziqian Jin's article, below. Here is the skew double-strip corresponding to n=15, with 12 cells:
_ ___ _ ___ _ ___
| | | | | | |
|__|___|_|___| |___|
| | | | | | |
|_|___|_|___|_|___|,
and here are the three possible "domino" tiles:
_ _
| | | |
| | | | _____
| | | | | |
|_|, |_|, |_____|.
As an example, here is one of the a(15) = 1490 ways to tile the skew double-strip of 12 cells:
_ ___ _____ _______
| | | | | | |
|__|_ |_|_ | _| _|
| | | | | |
|_____|___|_|___|_|. - Greg Dresden, Jun 05 2024

Examples

			From _Petros Hadjicostas_, Mar 10 2018: (Start)
For n = 3, we get a(3+4) = a(7) = 8 palindromic compositions of 2*n+1 = 7 into an odd number of parts that are not a multiple of 4. They are the following: 7 = 1+5+1 = 3+1+3 = 2+3+2 = 1+2+1+2+1 = 2+1+1+1+2 = 1+1+3+1+1 = 1+1+1+1+1+1+1. If we put these compositions on a circle, they become bilaterally symmetric cyclic compositions of 2*n+1 = 7.
For n = 4, we get a(4+4) = a(8) = 15 palindromic compositions of 2*n + 1 = 9 into an odd number of parts that are not a multiple of 4. They are the following: 9 = 3+3+3 = 2+5+2 = 1+7+1 = 1+1+5+1+1 = 2+1+3+1+2 = 1+2+3+2+1 = 1+3+1+3+1 = 3+1+1+1+3 = 2+2+1+2+2 = 2+1+1+1+1+1+2 = 1+2+1+1+1+2+1 = 1+1+2+1+2+1+1 = 1+1+1+3+1+1+1 = 1+1+1+1+1+1+1+1+1.
As _David Callan_ points out in the comments above, for n >= 1, a(n+4) is also the number of 0-1 sequences of length n that avoid 1111. For example, for n = 5, a(5+4) = a(9) = 29 is the number of binary strings of length n that avoid 1111. Out of the 2^5 = 32 binary strings of length n = 5, the following do not avoid 1111: 11111, 01111, and 11110. (End)

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

Crossrefs

Row 4 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).
First differences are in A001631.
Cf. A008287 (quadrinomial coefficients) and A073817 (tetranacci with different initial conditions).

Programs

  • GAP
    a:=[0,0,0,1];; for n in [5..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]+a[n-4]; od; a; # Muniru A Asiru, Mar 11 2018
  • 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
  • Magma
    [n le 4 select Floor(n/4) else Self(n-1)+Self(n-2)+Self(n-3)+Self(n-4): n in [1..50]]; // Vincenzo Librandi, Jan 29 2016
  • Maple
    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 *)
(* From Eric W. Weisstein, Nov 09 2017 *)
Table[RootSum[-1 -# -#^2 -#^3 +#^4 &, 10#^n +157#^(n+1) -103 #^(n+2) +16#^(n+3) &]/563, {n, 0, 40}]
Table[RootSum[#^4 -#^3 -#^2 -# -1 &, #^(n-2)/(-#^3 +6# -1) &], {n, 0, 40}] (* End *)
  • 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 */
  • PARI
    {a(n) = if( n<0, 0, polcoeff( x^3 / (1 - x - x^2 - x^3 - x^4) + x * O(x^n), n))}
  • 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

Formula

a(n) = A001630(n) - a(n-1). - Henry Bottomley
G.f.: x^3/(1 - x - x^2 - x^3 - x^4). - Simon Plouffe in his 1992 dissertation
G.f.: x^3 / (1 - x / (1 - x / (1 + x^3 / (1 + x / (1 - x / (1 + x)))))). - Michael Somos, May 12 2012
G.f.: Sum_{n >= 0} x^(n+3) * (Product_{k = 1..n} (k + k*x + k*x^2 + x^3)/(1 + k*x + k*x^2 + k*x^3)). - Peter Bala, Jan 04 2015
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_{i=0..floor((n-3)/5)} (-1)^i*binomial(n-3-4*i, i)*2^(n - 3 - 5*i) - Sum_{i=0..floor((n-4)/5)} (-1)^i*binomial(n-4-4*i, i)*2^(n - 4 - 5*i) with natural convention Sum_{i=m..n} alpha(i) = 0 for m > n. - Richard Choulet, Feb 22 2010
a(n+3) = Sum_{k=1..n} Sum_{i=k..n} [(5*k-i mod 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 [Edited by Petros Hadjicostas, Jul 26 2020, so that the formula agrees with the offset of the sequence]
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... = A086088 (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
From Ziqian Jin, Jul 28 2019: (Start)
a(2*n+5) = a(n+4)^2 + a(n+3)^2 + a(n+2)^2 + 2*a(n+3)*(a(n+2) + a(n+1)).
a(n) - 1 = a(n-2) + 2*a(n-3) + 3*(a(n-4) + a(n-5) + ... + a(2) + a(1)), n >= 4. (End)
a(n) = (Sum_{i=0..n-1} a(i)*A073817(n-i))/(n-3) for n > 3. - Greg Dresden and Advika Srivastava, Sep 28 2019
a(n) = Sum_{r root of x^4-x^3-x^2-x-1} r^n/(4*r^3-3*r^2-2*r-1). - Fabian Pereyra, Dec 06 2024

Extensions

Definition augmented (with 4 initial terms) by Daniel Forgues, Dec 02 2009
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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