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,3

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

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

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

Example

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

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

Prog

(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 */
(Magma) [Round(2^(n+2)/7): n in [0..40]]; // Vincenzo Librandi, Jun 25 2011
(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<<n+2)//7) + int((m-7*k<<1)>=7) # Chai Wah Wu, Jan 21 2023

Crossrefs

Apart from signs, same as A077972.

Cf. A139217 and A139218.

Cf. A078010.

Cf. A294627.

Sequence in context: A289976 A068036 A364525 * A077972 A293354 A293329

Adjacent sequences: A077944 A077945 A077946 * A077948 A077949 A077950

Keyword

nonn,easy

Author

N. J. A. Sloane, Nov 17 2002

Extensions

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

Status

approved