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

Author

Joseph Myers, Dec 24 2008

Keywords

• easy
• nonn

Links

• Indranil Ghosh, Table of n, a(n) for n = 1..1000
• Joseph Myers, BMO 2008--2009 Round 1 Problem 1---Generalisation

Crossrefs

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

Programs

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 *)

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

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

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.