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,2

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

Example

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

Mathematica

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

Prog

(Magma) [(n)*2^(2*n-2)-(2*n-1)*Binomial(2*n-2, n-1): n in [1..30]]; // Vincenzo Librandi, Sep 18 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

Crossrefs

Cf. A102699, A153334, A153335, A153336, A153337.

Sequence in context: A064837 A224902 A027433 * A007798 A058052 A119578

Adjacent sequences: A153335 A153336 A153337 * A153339 A153340 A153341

Keyword

easy,nonn

Author

Joseph Myers, Dec 24 2008

Extensions

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

Status

approved