A155020 a(n) = 2*a(n-1) + 2*a(n-2) for n > 2, a(0)=1, a(1)=1, a(2)=3.

1, 1, 3, 8, 22, 60, 164, 448, 1224, 3344, 9136, 24960, 68192, 186304, 508992, 1390592, 3799168, 10379520, 28357376, 77473792, 211662336, 578272256, 1579869184, 4316282880, 11792304128, 32217174016, 88018956288, 240472260608, 656982433792, 1794909388800, 4903783645184, 13397386067968

Offset: 0

Author

Philippe Deléham, Jan 19 2009

Keywords

• nonn
• easy

Comments

Equals 1 followed by A028859. - Klaus Brockhaus, Jul 18 2009

a(n) is the number of ways to arrange 1- and 2-cent postage stamps (totaling n cents) in a row so that the first stamp is correctly placed and any subsequent stamp may (or not) be placed upside down.

Number of compositions of n into parts k >= 1 where there are F(k+1) = A000045(k+1) sorts of part k. - Joerg Arndt, Sep 30 2012

a(n) is the top-left entry of the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 1, 1; 1, 1, 0] or of the 3 X 3 matrix [1, 1, 1; 1, 0, 1; 1, 1, 1].

From Tom Copeland, Nov 08 2014: (Start)

(Setting a(0)=0.)

This array is one of a family of Catalan arrays related by compositions of the special fractional linear (Möbius) transformations P(x,t) = x/(1-t*x); its inverse Pinv(x,t) = P(x,-t); and an o.g.f. of the Catalan numbers A000108, C(x) = (1-sqrt(1-4x))/2; and its inverse Cinv(x) = x*(1-x). (Cf. A091867.)

O.g.f.: G(x) = -P(P(Cinv(-x),1),1) = -P(Cinv(-x),2) = x(1+x)/(1-2x(1+x)) = (x+x^2)/(1-2(x+x^2)) = x + 3*x^2 + 8*x^3 + ... = A155020(x) with a(0)=0.

Ginv(x) = -C(P(P(-x,-1),-1)) = -C(P(-x,-2)) = (-1+sqrt(1+4*x/(1+2*x)))/2 = x*A064613(-x).

G(x) = x*(1+x) + 2*(x*(1+x))^2 + 2^2*(x*(1+x))^3 - ..., and so this array contains the row sums of A030528 * Diag(1, 2^1, 2^2, 2^3, ...). (End)

INVERT transform of Fibonacci(n+1). - Alois P. Heinz, Feb 11 2021

Examples

			a(2) = 3 because we have {1,1}, {1,_1} and {2}.
a(3) = 8 because we can order the stamps in eight ways: {1,1,1}  {1,1,_1}  {1,_1,1}  {1,_1,_1}  {2,1}   {2,_1}  {1,2}   {1,_2}, where _1 and _2 are upside down stamps.
a(4) = 22 = 2*3 + 2*8 because we can append 2 or _2 to the a(2) examples and 1 or _1 to the a(3) examples. - _Jon Perry_, Nov 10 2014
		

Links

• Indranil Ghosh, Table of n, a(n) for n = 0..2287
• Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 14.
• I. Amburg, K. Dasaratha, L. Flapan, T. Garrity, C. Lee, C. Mihailak, N. Neumann-Chun, S. Peluse, and M. Stoffregen, Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences, arXiv:1509.05239v1 [math.CO] 17 Sep 2015.
• Juan B. Gil and Jessica A. Tomasko, Fibonacci colored compositions and applications, arXiv:2108.06462 [math.CO], 2021.
• Jeffrey Shallit, Proof of Irvine's conjecture via mechanized guessing, arXiv preprint arXiv:2310.14252 [math.CO], October 22 2023.
• Index entries for linear recurrences with constant coefficients, signature (2,2).

Crossrefs

Sequences of the form a(n) = m*(a(n-1) + a(n-2)) with a(0)=1, a(1) = m-1, a(2) = m^2 -1: this sequence (m=2), A155116 (m=3), A155117 (m=4), A155119 (m=5), A155127 (m=6), A155130 (m=7), A155132 (m=8), A155144 (m=9), A155157 (m=10).

Cf. A028859 (essentially the same sequence). - Klaus Brockhaus, Jul 18 2009

Cf. A000045, A000108, A030528, A064613, A091867, A154929.

Row sums of A155112.

Programs

Magma

I:=[1,1,3,8]; [n le 4 select I[n] else 2*Self(n-1)+2*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Nov 10 2014

Maple

a:= proc(n) option remember; `if`(n=0, 1,
      add(a(n-i)*combinat[fibonacci](1+i), i=1..n))
    end:
seq(a(n), n=0..42);  # Alois P. Heinz, Feb 11 2021

Mathematica

CoefficientList[Series[(1 -x -x^2)/(1 -2x -2x^2), {x,0,20}], x]
With[{m=2}, LinearRecurrence[{m, m}, {1, m-1, m^2-1}, 30]] (* G. C. Greubel, Mar 25 2021 *)

Maxima

makelist(sum(binomial(n-k,k)*2^(n-k-1),k,0,floor(n/2)),n,1,12); /* Emanuele Munarini, Feb 04 2014 */

PARI

Vec( (1-x-x^2)/(1-2*x-2*x^2) + O(x^66) )  /* Joerg Arndt, Sep 30 2012 */

Sage

[1]+[(-1)*(sqrt(2)*i)^(n-2)*chebyshev_U(n, -sqrt(2)*i/2) for n in (1..30)] # G. C. Greubel, Mar 25 2021

Formula

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

G.f.: 1/( 1 - Sum_{k>=1} (x+x^2)^k ) - 1/( 1 - Sum_{k>=1} F(k+1)*x^k ) where F(k) = A000045(k). - Joerg Arndt, Sep 30 2012

a(n+1) = Sum_{k=0..n} A154929(n,k) = A028859(n).

a(n) = Sum_{k=0..floor(n/2)} ( binomial(n-k,k)*2^(n-k-1) ) for n > 0. - Emanuele Munarini, Feb 04 2014

a(n) = (1/2)*[n=0] - (sqrt(2)*i)^(n-2)*ChebyshevU(n, -sqrt(2)*i/2). - G. C. Greubel, Mar 25 2021

E.g.f.: (3 + exp(x)*(3*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x)))/6. - Stefano Spezia, Mar 02 2024