A153361 Number of zig-zag paths from top to bottom of a rectangle of width 12 with n rows.

12, 22, 42, 80, 154, 296, 572, 1104, 2138, 4136, 8020, 15536, 30148, 58450, 113472, 220110, 427410, 829352, 1610628, 3125954, 6071028, 11784514, 22887536, 44431506, 86293452, 167532792, 325373382, 631721620, 1226878704, 2382108386

Offset: 1

Author

Joseph Myers, Dec 24 2008

Keywords

• easy
• nonn

Comments

Number of words of length n using a 12-symbol alphabet where neighboring letters are neighbors in the alphabet. - Andrew Howroyd, Apr 17 2017

Links

• Joseph Myers, BMO 2008--2009 Round 1 Problem 1---Generalisation
• Index entries for linear recurrences with constant coefficients, signature (1,5,-4,-6,3,1).

Crossrefs

Column 12 of A220062.

Twice A129638.

Programs

Mathematica

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i == 0, Sum[b[n - 1, j, k], {j, 1, k}], If[i > 1, b[n - 1, i - 1, k], 0] + If[i < k, b[n - 1, i + 1, k], 0]]]; a[n_] := b[n, 0, 12]; Array[a, 30] (* Jean-François Alcover, Oct 10 2017, after Alois P. Heinz *)

Formula

G.f.: -2*x*(3*x^5 + 12*x^4 - 12*x^3 - 20*x^2 + 5*x + 6)/(x^6 + 3*x^5 - 6*x^4 - 4*x^3 + 5*x^2 + x - 1). - Colin Barker, Sep 02 2012