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

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

REFERENCES

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.

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

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

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

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

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

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.

F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.

E. Deutsch, Problem 1613: A recursion in four parts, Math. Mag., 75, No. 1, 64-64.

G. P. B. Dresden, Z. Du, A Simplified Binet Formula for k-Generalized Fibonacci Numbers, J. Int. Seq. 17 (2014) # 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, Journal of Integer Sequences, 19 (2016), Article 16.8.2.

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.

T. Mansour, 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. 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.

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

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

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

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

Eric Weisstein's World of Mathematics, Tetranacci Number.

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

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

Sequence in context: A066369 A239555 A275544 * A176503 A262333 A293335

Adjacent sequences:  A000075 A000076 A000077 * A000079 A000080 A000081

KEYWORD

nonn,easy,nice

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 05:59 EST 2018. Contains 317275 sequences. (Running on oeis4.)