A077846 Expansion of g.f. 1/(1 - 3*x + 2*x^3).

1, 3, 9, 25, 69, 189, 517, 1413, 3861, 10549, 28821, 78741, 215125, 587733, 1605717, 4386901, 11985237, 32744277, 89459029, 244406613, 667731285, 1824275797, 4984014165, 13616579925, 37201188181, 101635536213, 277673448789, 758617970005, 2072582837589, 5662401615189

Offset: 0

Author

N. J. A. Sloane, Nov 17 2002

Keywords

• nonn
• easy

Comments

Number of (s(0), s(1), ..., s(n+2)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| <= 1 for i = 1..n+2, s(0) = 1, s(n+2) = 3. - Herbert Kociemba, Jun 17 2004

A Whitney transform of 2^n (see Benoit Cloitre formula and A004070). The Whitney transform maps the sequence with g.f. g(x) to that with g.f. (1/(1-x))g(x(1+x)). - Paul Barry, Feb 16 2005

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Fan Chung and R. L. Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194.
• William J. Keith, Partitions into parts simultaneously regular, distinct, and/or flat, Proceedings of CANT 2016; arXiv:1911.04755 [math.CO], 2019. Mentions this sequence.
• Yassine Otmani, The 2-Pascal Triangle and a Related Riordan Array, J. Int. Seq. (2025) Vol. 28, Issue 3, Art. No. 25.3.5. See p. 12.
• Index entries for linear recurrences with constant coefficients, signature (3,0,-2).

Crossrefs

First differences are in A002605.

Cf. A028859, A052945, A057960, A068911,

Programs

Mathematica

CoefficientList[Series[1 / (1 - 3 x + 2 x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Jun 19 2013 *)
LinearRecurrence[{3,0,-2},{1,3,9},40] (* Harvey P. Dale, Apr 27 2014 *)

PARI

a(n)=sum(i=0,n,sum(j=0,n,2^j*binomial(j,i-j)))

PARI

Vec(1/(1-3*x+2*x^3) + O(x^100)) \\ Altug Alkan, Mar 24 2016

Formula

a(n) = 3*a(n-1) - 2*a(n-3) = 2*A057960(n) - 1 = round(2*A028859(n)/sqrt(3) - 1/3) = Sum_{i} b(n, i), where b(n, 0) = b(n, 6) = 0, b(0, 3) = 1, b(0, i) = 0 if i <> 3 and b(n+1, i) = b(n, i-1) + b(n, i) + b(n, i+1) if 0 < i < 6 (i.e., the number of three-choice paths along a corridor width 5, starting from the middle). - Henry Bottomley, Mar 06 2003

Binomial transform of A068911. a(n) = (1+sqrt(3))^n*(2+sqrt(3))/3 + (1-sqrt(3))^n*(2-sqrt(3))/3 - 1/3. - Paul Barry, Feb 17 2004

a(0)=1; for n >= 1, a(n) = ceiling((1+sqrt(3))*a(n-1)). - Benoit Cloitre, Jun 19 2004

a(n) = Sum_{i=0..n} Sum_{j=0..n} 2^j*binomial(j, i-j). - Benoit Cloitre, Oct 23 2004

a(n) = 2*(a(n-1) + a(n-2)) + 1, n > 1. - Gary Detlefs, Jun 20 2010

a(n) = (2*A052945(n+1) - 1)/3. - R. J. Mathar, Mar 31 2011

a(n) = floor((1+sqrt(3))^(n+2)/6). - Bruno Berselli, Feb 05 2013

a(n) = (-2 + (1-sqrt(3))^(n+2) + (1+sqrt(3))^(n+2))/6. - Alexander R. Povolotsky, Feb 13 2016

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

Extensions

Name changed by Arkadiusz Wesolowski, Dec 06 2011