|
| |
|
|
A155020
|
|
a(n) = 2*a(n-1) + 2*a(n-2) for n > 2, a(0)=1, a(1)=1, a(2)=3.
|
|
15
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
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].
(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+2x))/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)
|
|
|
LINKS
|
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.
|
|
|
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) = 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
|
|
|
EXAMPLE
|
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
|
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n=0, 1,
add(a(n-i)*combinat[fibonacci](1+i), i=1..n))
end:
|
|
|
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 *)
|
|
|
PROG
|
(PARI) Vec( (1-x-x^2)/(1-2*x-2*x^2) + O(x^66) ) /* Joerg Arndt, Sep 30 2012 */
(Maxima) makelist(sum(binomial(n-k, k)*2^(n-k-1), k, 0, floor(n/2)), n, 1, 12); /* Emanuele Munarini, Feb 04 2014 */
(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
(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
|
|
|
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).
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
