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

 

Logo


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)
79
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) 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 [Polya-Szego]. - 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

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

Indranil Ghosh, Table of n, a(n) for n = 0..3505 (terms 0..200 from T. D. Noe)

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 4(1) (2010), 119-135.

Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016.

Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, J. Integer Seq. 18 (2015), Article 15.4.5.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integer Seq. 3 (2000), Article 00.1.5.

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

F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, J. Integer Seq. 19 (2016), Article 16.1.1.

E. Deutsch, Problem 1613: A recursion in four parts, Math. Mag. 75(1) (2002), 64-65.

G. P. B. Dresden, Z. Du, A Simplified Binet Formula for k-Generalized Fibonacci Numbers, J. Integer Seq. 17 (2014), Article 14.4.7.

M. Feinberg, Fibonacci-Tribonacci, Fib. Quart. 1(3) (1963), 71-74.

Petros Hadjicostas, Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence, J. Integer Seq. 19 (2016), Article 16.8.2.

P. Hadjicostas and L. Zhang, Sommerville's symmetrical cyclic compositions of a positive integer with parts avoiding multiples of an integer, Fibonacci Quarterly 55 (2017), 54-73.

F. T. Howard and Curtis Cooper, Some identities for r-Fibonacci numbers, Fibonacci Quarterly 49 (2011), 231-242.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 11

Ziqian Jin, Tetrancci Identities With Squares, Dominoes, And Hexagonal Double Strips, arXiv:1907.09935 [math.GM], 2019.

W. C. Lynch, The t-Fibonacci numbers and polyphase sorting, Fib. Quart., 8 (1970), 6-22.

T. Mansour and M. Shattuck, A monotonicity property for generalized Fibonacci sequences, arXiv:1410.6943 [math.CO], 2014.

Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. Integer Seq. 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.

H. Prodinger, Counting Palindromes According to r-Runs of Ones Using Generating Functions, J. Integer Seq. 17 (2014), Article 14.6.2; odd length middle 0, r=3.

Helmut Prodinger and Sarah J. Selkirk, Sums of squares of Tetranacci numbers: A generating function approach, arXiv:1906.08336 [math.NT], 2019.

J. L. Ramírez and V. F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, Electron. J. Combin. 22(1) (2015), #P1.38.

Yüksel Soykan, Gaussian Generalized Tetranacci Numbers, arXiv:1902.03936 [math.NT], 2019.

Yüksel Soykan, Tetranacci and Tetranacci-Lucas Quaternions, arXiv:1902.05868 [math.RA], 2019.

Yüksel Soykan, Matrix Sequences of Tetranacci and Tetranacci-Lucas Numbers, Zonguldak Bülent Ecevit University (Zonguldak, Turkey), Preprints (2019), 2019070205.

O. Turek, Abelian Complexity Function of the Tribonacci Word, J. Integer Seq. 18 (2015), Article 15.3.4.

Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Eric Weisstein's World of Mathematics, Tetranacci Number.

L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Index entries for 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

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

From Ziqian Jin, Jul 28 2019: (Start)

a(2n+4) = 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

EXAMPLE

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

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

Table[RootSum[-1 - # - #^2 - #^3 + #^4 &, 10 #^n + 157 #^(n + 1) - 103 #^(n + 2) + 16 #^(n + 3) &]/563, {n, 0, 20}] (* Eric W. Weisstein, Nov 09 2017 *)

Table[RootSum[#^4 - #^3 - #^2 - # - 1 &, #^(n - 2)/(-#^3 + 6 # - 1) &], {n, 0, 20}] (* Eric W. Weisstein, Nov 09 2017 *)

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

(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

(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

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

Sequence in context: A066369 A239555 A275544 * A176503 A262333 A293335

Adjacent sequences:  A000075 A000076 A000077 * A000079 A000080 A000081

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane

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 | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 20:04 EDT 2019. Contains 328037 sequences. (Running on oeis4.)