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

Author

Joseph Myers, Dec 24 2008

Keywords

• easy
• nonn

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

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

Crossrefs

Column 9 of A220062.

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

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[iJean-François Alcover, Jul 01 2018, after Alois P. Heinz *)

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]