A078008 Expansion of (1 - x)/((1 + x)*(1 - 2*x)).

1, 0, 2, 2, 6, 10, 22, 42, 86, 170, 342, 682, 1366, 2730, 5462, 10922, 21846, 43690, 87382, 174762, 349526, 699050, 1398102, 2796202, 5592406, 11184810, 22369622, 44739242, 89478486, 178956970, 357913942, 715827882, 1431655766, 2863311530, 5726623062

Offset: 0

Author

N. J. A. Sloane, Nov 17 2002

Keywords

• nonn
• easy

Comments

Conjecture: a(n) = the number of fractions in the infinite Farey row of 2^n terms with even denominators. Compare the Salamin & Gosper item in the Beeler et al. link. - Gary W. Adamson, Oct 27 2003

Counts closed walks starting and ending at the same vertex of a triangle. 3*a(n) = P(C_n, 3) chromatic polynomial for 3 colors on cyclic graph C_n. A078008(n) + 2*A001045(n) = 2^n provides decomposition of Pascal's triangle. - Paul Barry, Nov 17 2003

Permutations with one fixed point avoiding 123 and 132.

General form: iterate k -> 2^n - k. See also A001045. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

The inverse g.f. generates sequence 1, 0, -2, -2, -2, -2, ...

a(n) gives the number of oriented (i.e., unreduced for symmetry) meanders on an (n+2) X 3 rectangular grid; see A201145. - Jon Wild, Nov 22 2011

Pisano period lengths: 1, 1, 6, 1, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, ... - R. J. Mathar, Aug 10 2012

a(n) is the number of length n binary words that end in an odd length run of 0's if we do not include the first letter of the word in our run length count. a(4) =6 because we have 0000, 0010, 0110, 1000, 1010, 1110. - Geoffrey Critzer, Dec 16 2013

a(n) is the top left entry of the n-th power of any of the six 3 X 3 matrices [0, 1, 1; 1, 1, 1; 1, 0, 0], [0, 1, 1; 1, 1, 0; 1, 1, 0], [0, 1, 1; 1, 0, 1; 1, 1, 0], [0, 1, 1; 1, 1, 0; 1, 0, 1], [0, 1, 1; 1, 0, 1; 1, 0, 1] or [0, 1, 1; 1, 0, 0; 1, 1, 1]. - R. J. Mathar, Feb 04 2014

a(n) is the number of compositions of n into parts of two kinds without part 1. - Gregory L. Simay, Jun 04 2018

a(n) is the number of words of length n over a binary alphabet whose position in the lexicographic order is a multiple of three. a(3) = 2: aba, bab. - Alois P. Heinz, Apr 13 2022

a(n) is the number of words of length n over a ternary alphabet starting with a fixed letter (say, 'a') and ending in a different letter, such that no two adjacent letters are the same. a(4) = 6: abab, abac, abcb, acab, acac, acbc. - Ignat Soroko, Jul 19 2023

Examples

			G.f. = 1 + 2*x^2 + 2*x^3 + 6*x^4 + 10*x^5 + 22*x^6 + ... - _Michael Somos_, Mar 18 2022
		

References

• Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 1.1.10a.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms n=0..300 from T. D. Noe)
• David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
• Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015. See Section 4.6.
• Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
• Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
• Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
• Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
• Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
• Paul Barry and A. Hennessy, Notes on a Family of Riordan Arrays and Associated Integer Hankel Transforms , JIS 12 (2009) 09.5.3.
• M. Beeler, R. W. Gosper, and R. C. Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb 29 1972. (Item #54 by Salamin & Gosper)
• Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
• Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, arXiv:1907.06517 [math.CO], 2019.
• Ernesto Estevez-Rams, Cristy Azanza Ricardo and Beatriz Aragón Fernández, An alternative expression for counting the number of close-packaged polytypes, Z. Krist. 220 (2005) 592-595, eq (4)
• Leonhard Euler, Introductio in analysin infinitorum, (1748), section 216.
• Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See p. 13.
• T. Mansour and A. Robertson, Refined Restricted Permutations Avoiding Subsets of Patterns of Length Three, arXiv:math/0204005 [math.CO], 2002.
• N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
• Index entries for linear recurrences with constant coefficients, signature (1,2).
• Index entries for sequences related to Chebyshev polynomials.

Crossrefs

First differences of A001045.

See A151575 for a signed version.

Bisections: A047849, A020988.

Cf. A151548, A139250, A151555, A153006.

Programs

GAP

List([0..40], n-> (2^n + 2*(-1)^n)/3); # G. C. Greubel, Jun 28 2019

Magma

[(2^n + 2*(-1)^n)/3: n in [0..40]]; // G. C. Greubel, Jun 28 2019

Mathematica

Table[(2^n + 2*(-1)^n)/3, {n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Dec 11 2008; modified by G. C. Greubel, Jun 28 2019 *)
CoefficientList[Series[(1-x)/(1-x-2x^2),{x,0,40}],x]  (* Harvey P. Dale, Mar 30 2011 *)
LinearRecurrence[{1, 2}, {1, 0}, 40] (* Jean-François Alcover, Sep 23 2017 *)

PARI

a(n)=(1<Charles R Greathouse IV, Jun 10 2011

Python

def A078008(n): return ((1<Chai Wah Wu, Apr 18 2025

Sage

[(2^n + 2*(-1)^n)/3 for n in (0..40)] # G. C. Greubel, Jun 28 2019

Formula

Euler expands(1-x)/(1 - x - 2*x^2) into an infinite series and finds that the coefficient of the n-th term is (2^n + (-1)^n 2)/3. Section 226 shows that Euler could have easily found the recursion relation: a(n) = a(n-1) + 2a(n-2) with a(0) = 1 and a(1) = 0. - V. Frederick Rickey (fred-rickey(AT)usma.edu), Feb 10 2006. [Typos corrected by Jaume Oliver Lafont, Jun 01 2009]

a(n) = Sum_{k=0..floor(n/3)} binomial(n, f(n)+3*k) where f(n) = (0, 2, 1, 0, 2, 1, ...) = A080424(n). - Paul Barry, Feb 20 2003

E.g.f. (exp(2*x) + 2*exp(-x))/3. - Paul Barry, Apr 20 2003

a(n) = A001045(n) + (-1)^n = A000079(n) - 2*A001045(n). - Paul Barry, Feb 20 2003

a(n) = (2^n + 2*(-1)^n)/3. - Mario Catalani (mario.catalani(AT)unito.it), Aug 29 2003

a(n) = T(n, i/(2*sqrt(2)))*(-i*sqrt(2))^n - U(n-1, i/(2*sqrt(2)))*(-i*sqrt(2))^(n-1)/2. - Paul Barry, Nov 17 2003

From Paul Barry, Jul 30 2004: (Start)

a(n) = 2*a(n-1) + 2*(-1)^n for n > 0, with a(0)=1.

a(n) = Sum_{k=0..n} (-1)^k*(2^(n-k-1) + 0^(n-k)/2). (End)

a(n) = A014113(n-1) for n > 0; a(n) = A052953(n-1) - 2*(n mod 2) = sum of n-th row of the triangle in A108561. - Reinhard Zumkeller, Jun 10 2005

A137208(n+1) - 2*A137208(n) = a(n) signed. - Paul Curtz, Aug 03 2008

a(n) = A001045(n+1) - A001045(n) - Paul Curtz, Feb 09 2009

If p[1] =0, and p[i]=2, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, Apr 29 2010

a(n) = 2*(a(n-2) + a(n-3) + a(n-4) ... + a(0)), that is, twice the sum of all the previous terms except the last; with a(0) = 1 and a(1) = 0. - Benoit Jubin, Nov 21 2011

a(n+1) = 2*A001045(n). - Benoit Jubin, Nov 22 2011

G.f.: 1 - x + x*Q(0), where Q(k) = 1 + 2*x^2 + (2*k+3)*x - x*(2*k+1 + 2*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 05 2013

G.f.: 1+ x^2*Q(0), where Q(k) = 1 + 1/(1 - x*(4*k+1+2*x)/(x*(4*k+3+2*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 01 2014

a(n) = 3*a(n-2) + 2*a(n-3). - David Neil McGrath, Sep 10 2014

a(n) = (-1)^n * A151575(n). - G. C. Greubel, Jun 28 2019

a(n)+a(n+1) = 2^n. - R. J. Mathar, Feb 24 2021

a(n) = -a(2-n) * (-2)^(n-1) = (3/2)*(a(n-1) + a(n-2)) - a(n-3) for all n in Z. - Michael Somos, Mar 18 2022