A153338 Number of zig-zag paths from top to bottom of a 2n-1 by 2n-1 square whose color is not that of the top right corner.

0, 2, 18, 116, 650, 3372, 16660, 79592, 371034, 1697660, 7654460, 34106712, 150499908, 658707896, 2863150440, 12371226064, 53178791162, 227561427612, 969890051884, 4119092850680, 17438036501676, 73611934643368, 309935825654168, 1301878616066736

Offset: 1

Author

Joseph Myers, Dec 24 2008

Keywords

• easy
• nonn

Examples

			a(3) = 3*2 ^ (2*3 - 2) - (2*3 - 1) * binomial(2*3 - 2, 3 - 1) = 18. - _Indranil Ghosh_, Feb 19 2017
		

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, A153335, A153336, A153337.

Programs

Magma

[(n)*2^(2*n-2)-(2*n-1)*Binomial(2*n-2, n-1): n in [1..30]]; // Vincenzo Librandi, Sep 18 2015

Mathematica

Table[n 2^(2 n - 2) - (2 n - 1) Binomial[2 n - 2, n - 1], {n, 22}] (* Michael De Vlieger, Sep 17 2015 *)

Python

import math
def C(n,r):
    f=math.factorial
    return f(n)/f(r)/f(n-r)
def A153338(n):
    return str(n*2**(2*n-2)-(2*n-1)*C(2*n-2,n-1)) # Indranil Ghosh, Feb 19 2017

Formula

a(n) = n*2^(2*n-2) - (2*n-1)*binomial(2*n-2,n-1).

4^n*(n+1)-C(2*n,n)*(2*n+1) = Sum_{k=1..n} C(2*(n-k),n-k)*C(2*k,k)*k*(H(k)-H(n-k)) for n >= 0; H(n) denote the harmonic numbers. This identity is attributed to Maillard. - Peter Luschny, Sep 17 2015

Extensions

a(23)-a(24) from Vincenzo Librandi, Sep 18 2015