A182522 a(0) = 1; thereafter a(2*n + 1) = 3^n, a(2*n + 2) = 2 * 3^n.

1, 1, 2, 3, 6, 9, 18, 27, 54, 81, 162, 243, 486, 729, 1458, 2187, 4374, 6561, 13122, 19683, 39366, 59049, 118098, 177147, 354294, 531441, 1062882, 1594323, 3188646, 4782969, 9565938, 14348907, 28697814, 43046721, 86093442, 129140163, 258280326, 387420489

Offset: 0

Author

Michael Somos, May 03 2012

Keywords

• nonn
• easy

Comments

Row sums of triangle in A123149. - Philippe Deléham, May 04 2012

This is simply the classic sequence A038754 prefixed by a 1. - N. J. A. Sloane, Nov 23 2017

Binomial transform is A057960.

Range of row n of the circular Pascal array of order 6. - Shaun V. Ault, May 30 2014

a(n) is also the number of achiral color patterns in a row or cycle of length n using three or fewer colors. Two color patterns are the same if we permute the colors, so ABCAB=BACBA. For a cycle, we can rotate the colors, so ABCAB=CABAB. A row is achiral if it is the same as some color permutation of its reverse. Thus the reversal of ABCAB is BACBA, which is equivalent to ABCAB when we permute A and B. A cycle is achiral if it is the same as some rotation of some color permutation of its reverse. Thus CABAB reversed is BABAC. We can permute A and B to get ABABC and then rotate to get CABAB, so CABAB is achiral. It is interesting that the number of achiral color patterns is the same for rows and cycles. - Robert A. Russell, Mar 10 2018

Also, the number of walks of length n on the graph 0--1--2--3--4 starting at vertex 0. - Sean A. Irvine, Jun 03 2025

Examples

			G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 9*x^5 + 18*x^6 + 27*x^7 + 54*x^8 + ...
From _Robert A. Russell_, Mar 10 2018: (Start)
For a(4) = 6, the achiral color patterns for rows are AAAA, AABB, ABAB, ABBA, ABBC, and ABCA.  Note that for cycles AABB=ABBA and ABBC=ABCA.  The achiral patterns for cycles are AAAA, AAAB, AABB, ABAB, ABAC, and ABBC.  Note that AAAB and ABAC are not achiral rows.
For a(5) = 9, the achiral color patterns (for both rows and cycles) are AAAAA, AABAA, ABABA, ABBBA, AABCC, ABACA, ABBBC, ABCAB, and ABCBA. (End)
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, arXiv:1407.2197 [math.CO], 2014.
• Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Volume 332, October 2014, Pages 45-54.
• Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.
• Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015-2016.
• Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
• Sean A. Irvine, Walks on Graphs.
• Index entries for linear recurrences with constant coefficients, signature (0,3).

Crossrefs

Cf. A038754 (essentially the same sequence).

Cf. A008277, A052551, A057427, A057960.

Cf. A123149, A140735, A293181, A304973.

Also row sums of triangle in A169623.

Column 3 of A305749.

Cf. A124302 (oriented), A001998 (unoriented), A107767 (chiral), for rows, varying offsets.

Cf. A002076 (oriented), A056353 (unoriented), A320743 (chiral), for cycles.

Programs

Magma

I:=[1,1,2]; [n le 3 select I[n] else 3*Self(n-2): n in [1..40]]; // Bruno Berselli, Mar 19 2013

Mathematica

Join[{1}, RecurrenceTable[{a[1]==1, a[2]==2, a[n]==3 a[n-2]}, a, {n, 40}]] (* Bruno Berselli, Mar 19 2013 *)
CoefficientList[Series[(1+x-x^2)/(1-3*x^2), {x,0,50}], x] (* G. C. Greubel, Apr 14 2017 *)
Table[If[EvenQ[n], StirlingS2[(n+6)/2,3] - 4 StirlingS2[(n+4)/2,3] + 5 StirlingS2[(n+2)/2,3] - 2 StirlingS2[n/2,3], StirlingS2[(n+5)/2,3] - 3 StirlingS2[(n+3)/2,3] + 2 StirlingS2[(n+1)/2,3]], {n,0,40}] (* Robert A. Russell, Oct 21 2018 *)
Join[{1},Table[If[EvenQ[n], 2 3^((n-2)/2), 3^((n-1)/2)],{n,40}]] (* Robert A. Russell, Oct 28 2018 *)

Maxima

makelist(if n=0 then 1 else (1+mod(n-1,2))*3^floor((n-1)/2), n, 0, 40); /* Bruno Berselli, Mar 19 2013 */

PARI

{a(n) = if( n<1, n==0, n--; (n%2 + 1) * 3^(n \ 2))}

PARI

my(x='x+O('x^50)); Vec((1+x-x^2)/(1-3*x^2)) \\ G. C. Greubel, Apr 14 2017

SageMath

def A182522(n): return (3 -(3-2*sqrt(3))*((n+1)%2))*3^((n-3)/2) + int(n==0)/3
[A182522(n) for n in range(41)] # G. C. Greubel, Jul 17 2023

Formula

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

Expansion of 1 / (1 - x / (1 - x / (1 + x / (1 + x)))) in powers of x.

a(n+1) = A038754(n).

a(n) = Sum_{k=0..n} A123149(n,k). - Philippe Deléham, May 04 2012

a(n) = (3-(1+(-1)^n)*(3-2*sqrt(3))/2)*sqrt(3)^(n-3) for n>0, a(0)=1. - Bruno Berselli, Mar 19 2013

a(0) = 1, a(1) = 1, a(n) = a(n-1) + a(n-2) if n is odd, and a(n) = a(n-1) + a(n-2) + a(n-3) if n is even. - Jon Perry, Mar 19 2013

For odd n = 2m-1, a(2m-1) = T(m,1)+T(m,2)+T(m,3) for triangle T(m,k) of A140735; for even n = 2m, a(2m) = T(m,1)+T(m,2)+T(m,3) for triangle T(m,k) of A293181. - Robert A. Russell, Mar 10 2018

From Robert A. Russell, Oct 21 2018: (Start)

a(2m) = S2(m+3,3) - 4*S2(m+2,3) + 5*S2(m+1,3) - 2*S2(m,3).

a(2m-1) = S2(m+2,3) - 3*S2(m+1,3) + 2*S2(m,3), where S2(n,k) is the Stirling subset number A008277.

a(n) = 2*A001998(n-1) - A124302(n) = A124302(n) - 2*A107767(n-1) = A001998(n-1) - A107767(n-1).

a(n) = 2*A056353(n) - A002076(n) = A002076(n) - 2*A320743(n) = A056353(n) - A320743(n).

a(n) = A057427(n) + A052551(n-2) + A304973(n). (End)

Extensions

Edited by Bruno Berselli, Mar 19 2013

Definition simplified by N. J. A. Sloane, Nov 23 2017