login
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.
7

%I #18 Sep 08 2022 08:45:39

%S 0,2,18,116,650,3372,16660,79592,371034,1697660,7654460,34106712,

%T 150499908,658707896,2863150440,12371226064,53178791162,227561427612,

%U 969890051884,4119092850680,17438036501676,73611934643368,309935825654168,1301878616066736

%N 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.

%H Indranil Ghosh, <a href="/A153338/b153338.txt">Table of n, a(n) for n = 1..1000</a>

%H Joseph Myers, <a href="http://www.polyomino.org.uk/publications/2008/bmo1-2009-q1.pdf">BMO 2008--2009 Round 1 Problem 1---Generalisation</a>

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

%F 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

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

%t Table[n 2^(2 n - 2) - (2 n - 1) Binomial[2 n - 2, n - 1], {n, 22}] (* _Michael De Vlieger_, Sep 17 2015 *)

%o (Magma) [(n)*2^(2*n-2)-(2*n-1)*Binomial(2*n-2, n-1): n in [1..30]]; // _Vincenzo Librandi_, Sep 18 2015

%o (Python)

%o import math

%o def C(n,r):

%o ....f=math.factorial

%o ....return f(n)/f(r)/f(n-r)

%o def A153338(n):

%o ....return str(n*2**(2*n-2)-(2*n-1)*C(2*n-2,n-1)) # _Indranil Ghosh_, Feb 19 2017

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

%K easy,nonn

%O 1,2

%A _Joseph Myers_, Dec 24 2008

%E a(23)-a(24) from _Vincenzo Librandi_, Sep 18 2015