A153335 Number of zig-zag paths from top to bottom of an n X n square whose color is not that of the top right corner.

0, 1, 2, 8, 18, 52, 116, 296, 650, 1556, 3372, 7768, 16660, 37416, 79592, 175568, 371034, 807604, 1697660, 3657464, 7654460, 16357496, 34106712, 72407728, 150499908, 317777032, 658707896, 1384524656, 2863150440, 5994736336

Offset

1,3

Links

Indranil Ghosh, Table of n, a(n) for n = 1..1000

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

Formula

a(n) = (n+1)2^(n-2) - 2(n-1)binomial(n-2,(n-2)/2) for n even, a(n) = (n+1)2^(n-2) - (n)binomial(n-1,(n-1)/2) for n odd.

Mathematica

Table[If[Mod[n, 2]==0, (n+1)*2^(n-2)-2(n-1) Binomial[n-2, (n-2)/2], (n+1)*2^(n-2)-(n) Binomial[n-1, (n-1)/2]], {n, 1, 30}] (* Indranil Ghosh, Feb 19 2017 *)

Prog

(Python)
import math
def C(n, r):
....f=math.factorial
....return f(n)/f(r)/f(n-r)
def A153335(n):
....if n%2==0: return str(int((n+1)*2**(n-2)-2*(n-1)*C(n-2, (n-2)/2)))
....else: return str(int((n+1)*2**(n-2)-(n)*C(n-1, (n-1)/2))) # Indranil Ghosh, Feb 19 2017
(PARI) a(n) = if (n % 2, (n+1)*2^(n-2) - n*binomial(n-1, (n-1)/2), (n+1)*2^(n-2) - 2*(n-1)*binomial(n-2, (n-2)/2)); \\ Michel Marcus, Feb 19 2017

Crossrefs

Cf. A102699, A153334, A153336, A153337, A153338.

Sequence in context: A249763 A114723 A267638 * A119853 A136201 A358907

Adjacent sequences: A153332 A153333 A153334 * A153336 A153337 A153338

Keyword

easy,nonn

Author

Joseph Myers, Dec 24 2008

Status

approved