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

9, 16, 30, 56, 106, 200, 380, 720, 1370, 2600, 4950, 9400, 17900, 34000, 64750, 123000, 234250, 445000, 847500, 1610000, 3066250, 5825000, 11093750, 21075000, 40137500, 76250000, 145218750, 275875000, 525406250, 998125000, 1900937500

Offset

1,1

Comments

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

Links

Table of n, a(n) for n=1..31.

Joseph Myers, BMO 2008--2009 Round 1 Problem 1---Generalisation

Formula

Empirical G.f.: x*(9+16*x-15*x^2-24*x^3+x^4)/(1-5*x^2+5*x^4). [Colin Barker, Sep 02 2012]

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, 9];
Array[a, 31] (* Jean-François Alcover, Jul 01 2018, after Alois P. Heinz *)

Crossrefs

Column 9 of A220062.

Cf. A153363, A153364, A153365, A153366, A153367.

Sequence in context: A351435 A369642 A162616 * A039788 A175652 A348233

Adjacent sequences: A153359 A153360 A153361 * A153363 A153364 A153365

Keyword

easy,nonn

Author

Joseph Myers, Dec 24 2008

Status

approved