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

1, 3, 12, 39, 120, 363, 1092, 3279, 9840, 29523, 88572, 265719, 797160, 2391483, 7174452, 21523359, 64570080, 193710243, 581130732, 1743392199, 5230176600, 15690529803, 47071589412, 141214768239, 423644304720, 1270932914163

Offset: 0

Author

Philippe Deléham, Sep 28 2006

Keywords

• nonn
• easy

Comments

From R. J. Mathar, Oct 12 2010: (Start)

The top row, n=2, of an array that counts chess king walks with k >= 0 steps on an n X n board, starting at one of the four corners:

1,3,12, 39,120, 363, 1092, 3279, 9840, 29523, 88572, 265719, 797160,

1,3,21,101,501,2405,11653, 56197, 271493, 1310597, 6328709, 30556549,

1,3,21,126,741,4341,25416,148791, 871041, 5099166,29851041,174751041,

1,3,21,126,810,5169,33447,215796,1395588, 9018255,58302057,376845978,

1,3,21,126,810,5360,36167,246034,1680313,11495503,78705226,539048956,

1,3,21,126,810,5360,36700,254756,1788468,12617828,89338116,633604564,

1,3,21,126,810,5360,36700,256255,1816090,12993280,93566653,676648735,

1,3,21,126,810,5360,36700,256255,1820335,13080120,94845670,692120270,

1,3,21,126,810,5360,36700,256255,1820335,13092211,95117374,696421066,

1,3,21,126,810,5360,36700,256255,1820335,13092211,95151979,697268152,

1,3,21,126,810,5360,36700,256255,1820335,13092211,95151979,697367593,

These are partial sums along rows of the array described in A086346. (End)

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See p. 17.
• Index entries for linear recurrences with constant coefficients, signature (4,-3).

Programs

GAP

a:=[1,3,12];; for n in [4..30] do a[n]:=4*a[n-1]-3*a[n-2]; od; a; # G. C. Greubel, May 24 2019

Magma

I:=[1, 3, 12]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Jun 27 2012

Mathematica

LinearRecurrence[{4,-3}, {1,3,12}, 30] (* Georg Fischer, May 24 2019 *)
Join[{1},NestList[3#+3&,3,30]] (* Harvey P. Dale, Aug 16 2020 *)

PARI

my(x='x+O('x^30)); Vec((1-x+3*x^2)/(1-4*x+3*x^2)) \\ G. C. Greubel, May 24 2019

Sage

((1-x+3*x^2)/(1-4*x+3*x^2)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 24 2019

Formula

a(0) = 1 and a(n) = 3*A003462(n) for n > 0.

G.f.: (1-x+3*x^2)/(1-4*x+3*x^2). [Corrected by Georg Fischer, May 24 2019]

a(n) = Sum_{k=0..n} 3^k*A123110(n,k). - Philippe Deléham, Feb 09 2007

a(n) = A029858(n+1), n > 0. - R. J. Mathar, Jun 18 2008

a(n+1) - a(n) = 3^n, n >= 2. - R. J. Mathar, Aug 18 2011

E.g.f.: 1 + 3*(exp(3*x) - exp(x))/2. - G. C. Greubel, May 24 2019