A096367 Number of winning paths of length n+1 across an n X n Hex board.

2, 14, 58, 194, 578, 1602, 4226, 10754, 26626, 64514, 153602, 360450, 835586, 1916930, 4358146, 9830402, 22020098, 49020930, 108527618, 239075330, 524288002, 1145044994, 2491416578, 5402263554, 11676942338, 25165824002, 54089744386, 115964116994, 248034361346

Offset

3,1

Comments

If m>n-2, H(m,n) = (2*m+1-n)*2^(n-2) is the number of winning paths of length n across an m X n Hex board (cf. A001792). If m>n-1, H'(m,n) = (n-2)*(H(m-3,n-2) + H(m+1,n-2)) - 2^(n-1) + 2 is the number of winning paths of length n+1 across an m X n Hex board.

Links

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

Index entries for linear recurrences with constant coefficients, signature (7, -18, 20, -8).

Formula

a(n) = (n-2)*(n+1)*2^(n-3)-2^(n-1)+2.

G.f.: -2*x^3*(2*x^2-1) / ((x-1)*(2*x-1)^3). - Colin Barker, Sep 06 2013

Example

a(4)=14.

Prog

(Python)
def a(n): return (n-2)*(n+1)*2**(n-3) - 2**(n-1) + 2
print([a(n) for n in range(3, 32)]) # Michael S. Branicky, Feb 14 2021

Crossrefs

Cf. A001792.

Sequence in context: A212895 A115027 A114146 * A232601 A285153 A232370

Adjacent sequences: A096364 A096365 A096366 * A096368 A096369 A096370

Keyword

nonn,easy

Author

David Bevan, Jul 02 2004

Extensions

More terms from Colin Barker, Sep 06 2013

Status

approved