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

10, 18, 34, 64, 122, 232, 444, 848, 1626, 3112, 5972, 11442, 21964, 42106, 80832, 155010, 297570, 570760, 1095620, 2101752, 4034252, 7739690, 14855342, 28501710, 54703004, 104959000, 201439550, 386516750, 741790648, 1423365002, 2731617694

Offset: 1

Author

Joseph Myers, Dec 24 2008

Keywords

• easy
• nonn

Comments

Number of words of length n using a 10 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, 4, -3, -3, 1).

Crossrefs

Column 10 of A220062.

Twice A090994.

Programs

Mathematica

LinearRecurrence[{1, 4, -3, -3, 1}, {10, 18, 34, 64, 122}, 31] (* Jean-François Alcover, Jul 01 2018 *)

Formula

G.f.: 2*x*(5+4*x-12*x^2-6*x^3+3*x^4)/(1-x-4*x^2+3*x^3+3*x^4-x^5) [From Maksym Voznyy (voznyy(AT)mail.ru), Aug 11 2009]

Extensions

G.f. proposed by Maksym Voznyy checked and corrected by R. J. Mathar, Sep 16 2009.