A077947 Expansion of 1/(1 - x - x^2 - 2*x^3).

1, 1, 2, 5, 9, 18, 37, 73, 146, 293, 585, 1170, 2341, 4681, 9362, 18725, 37449, 74898, 149797, 299593, 599186, 1198373, 2396745, 4793490, 9586981, 19173961, 38347922, 76695845, 153391689, 306783378, 613566757, 1227133513, 2454267026, 4908534053, 9817068105

Offset: 0

Author

N. J. A. Sloane, Nov 17 2002

Keywords

• nonn
• easy

Comments

Number of sequences of codewords of total length n from the code C={0,10,110,111}. E.g., a(3)=5 corresponds to the sequences 000, 010, 100, 110 and 111. - Paul Barry, Jan 23 2004

In other words: number of compositions of n into 1 kind of 1's and 2's and two kinds of 3's. - Joerg Arndt, Jun 25 2011

Diagonal sums of number Pascal-(1,2,1) triangle A081577. - Paul Barry, Jan 24 2005

For n>0: a(n) = A173593(2*n+1) - A173593(2*n); a(n+1) = A173593(2*n) - A173593(2*n-1). - Reinhard Zumkeller, Feb 22 2010

Sums of 3 successive terms are powers of 2. - Mark Dols, Aug 20 2010

For n > 2, a(n) is the number of quaternary sequences of length n (i) starting with q(0)=0; (ii) ending with q(n-1)=0 or 3 and (iii) in which all triples (q(i), q(i+1), q(i+2)) contain digits 0 and 3; cf. A294627. - Wojciech Florek, Jul 30 2018

Examples

			It is shown in A294627 that there are 42 quaternary sequences (i.e. build from four digits 0, 1, 2, 3) and having both 0 and 3 in every (consecutive) triple. Only a(4) = 9 of them start with 0 and end with 0 or 3: 0030, 0033, 0130, 0230, 0300, 0303, 0310, 0320, 0330. - _Wojciech Florek_, Jul 30 2018
		

References

• S. Roman, Introduction to Coding and Information Theory, Springer-Verlag, 1996, p. 42

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• G. Cerda-Morales, A note on modified third-order Jacobsthal Numbers, arxiv:1905.00725 [math.CO], 2019.
• M. H. Cilasun, An Analytical Approach to Exponent-Restricted Multiple Counting Sequences, arXiv preprint arXiv:1412.3265 [math.NT], 2014.
• M. H. Cilasun, Generalized Multiple Counting Jacobsthal Sequences of Fermat Pseudoprimes, Journal of Integer Sequences, Vol. 19, 2016, #16.2.3.
• Charles K. Cook and Michael R. Bacon, Some identities for Jacobsthal and Jacobsthal-Lucas numbers satisfying higher order recurrence relations, Annales Mathematicae et Informaticae, 41 (2013) pp. 27-39.
• W. Florek, A class of generalized Tribonacci sequences applied to counting problems, Appl. Math. Comput., 338 (2018), 809-821.
• S. Kitaev, J. Remmel and M. Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012
• Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16; see also arXiv preprint, arXiv:1302.2274 [math.CO], 2013.
• Vladimir Victorovich Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565, arXiv:1009.2565 [math.CO], 2010.
• Evren Eyican Polatlı and Yüksel Soykan, On generalized third-order Jacobsthal numbers, Asian Res. J. of Math. (2021) Vol. 17, No. 2, 1-19, Article No. ARJOM.66022.
• Yüksel Soykan, Summing Formulas For Generalized Tribonacci Numbers, arXiv:1910.03490 [math.GM], 2019.
• Anthony Zaleski and Doron Zeilberger, On the Intriguing Problem of Counting (n+1,n+2)-Core Partitions into Odd Parts, arXiv:1712.10072 [math.CO], 2017.
• Index entries for linear recurrences with constant coefficients, signature (1,1,2).

Crossrefs

Apart from signs, same as A077972.

Cf. A139217 and A139218.

Cf. A078010.

Cf. A294627.

Programs

Magma

[Round(2^(n+2)/7): n in [0..40]]; // Vincenzo Librandi, Jun 25 2011

Maple

seq(round(2^(n+2)/7),n=0..25); # Mircea Merca, Dec 28 2010

Mathematica

CoefficientList[Series[1/(1 - x - x^2 - 2*x^3), {x, 0, 100}], x] (* or *) LinearRecurrence[{1, 1, 2}, {1, 1, 2}, 70] (* Vladimir Joseph Stephan Orlovsky, Jun 28 2011 *)

Maxima

a(n):=sum(sum(binomial(k,j)*binomial(j,n-3*k+2*j)*2^(k-j),j,0,k),k,1,n); /* Vladimir Kruchinin, Sep 07 2010 */

PARI

Vec(1/(1-x-x^2-2*x^3) + O(x^100)) \\ Altug Alkan, Oct 31 2015

Python

def A077947(n): return (k:=(m:=1<=7) # Chai Wah Wu, Jan 21 2023

Formula

G.f.: 1/((1-2*x)*(1+x+x^2)).

a(n) = a(n-1)+a(n-2)+2*a(n-3). - Paul Curtz, May 23 2008

a(n) = round(2^(n+2)/7). - Mircea Merca, Dec 28 2010

a(n) = 4*2^n/7 + 3*cos(2*Pi*n/3)/7 + sqrt(3)*sin(2*Pi*n/3)/21. - Paul Barry, Jan 23 2004

Convolution of A000079 and A049347. a(n) = Sum_{k=0..n} 2^k*2*sqrt(3)*cos(2*Pi(n-k)/3+Pi/6)/3. - Paul Barry, May 19 2004

a(n) = sum(sum(binomial(k,j)*binomial(j,n-3*k+2*j)*2^(k-j),j,0,k),k,1,n), n>0. - Vladimir Kruchinin, Sep 07 2010

Partial sums of A078010 starting (1, 0, 1, 3, 4, 9, ...). - Gary W. Adamson, May 13 2013

a(n) = (1/14)*(2^(n + 3) + (-1)^n*((-1)^floor(n/3) + 4*(-1)^floor((n + 1)/3) + 2*(-1)^floor((n + 2)/3) + (-1)^floor((n + 4)/3))). - John M. Campbell, Dec 23 2016

a(n) = (1/63)*(9*2^(2 + n) + (-1)^n*(2 + 9*floor(n/6) - 32*floor((n + 5)/6) + 24*floor((n + 7)/6) + 20*floor((n + 8)/6) - 10*floor((n + 9)/6) - 27*floor((n + 10)/6) + 14*floor((n + 11)/6) + 3*floor((n + 13)/6) - 2*floor((n + 14)/6) + floor((n + 15)/6))). - John M. Campbell, Dec 23 2016

7*a(n) = 2^(n+2) + A167373(n+1). - R. J. Mathar, Feb 06 2020

a(n) = T(n+1) + 2*(a(1)*T(n-1) + a(2)*T(n-2) + ... + a(n-2)*T(2) + a(n-1)*T(1)) for T(n) = A000073(n), the tribonacci numbers. - Greg Dresden and Bora Bursalı, Sep 14 2023

Extensions

Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021