A067804 Triangle read by rows: T(n,k) is the number of walks (each step +-1) of length 2n which have a cumulative value of 0 last at step 2k.
1, 2, 2, 6, 4, 6, 20, 12, 12, 20, 70, 40, 36, 40, 70, 252, 140, 120, 120, 140, 252, 924, 504, 420, 400, 420, 504, 924, 3432, 1848, 1512, 1400, 1400, 1512, 1848, 3432, 12870, 6864, 5544, 5040, 4900, 5040, 5544, 6864, 12870, 48620, 25740, 20592, 18480
Offset: 0
Examples
Triangle begins:
1;
2, 2;
6, 4, 6;
20, 12, 12, 20;
70, 40, 36, 40, 70;
252, 140, 120, 120, 140, 252;
...
For a walk of length 4 (=2*2), 6 are only ever 0 at step 0, 4 are zero at step 2 but not step 4 and 6 are 0 at step 4.
For n=3,k=2, T(3,2)=12 since there are 12 monotonic paths from (0,0) to (2,2) and then on to (3,3). Using E for eastward steps and N for northward steps, the 12 paths are given by EENNNE, ENENNE, ENNENE, NNEENE, NENENE, NEENNE, EENNEN, ENENEN, ENNEEN, NNEEEN, NENEEN, NEENEN. - _Dennis P. Walsh_, Mar 23 2012
References
- A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 79, ex. 3f.
Links
- G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
- B. C. Carlson, Power series for inverse Jacobian elliptic functions, Math. Comp., 77 (2008), 1615-1621, see p. 1617, equation (2.20).
- C. M. Grinstead and J. L. Snell, Introduction to Probability p. 482.
- R. P. Kelisky, Inverse elliptic functions and Legendre polynomials, Amer. Math. Monthly 66 (1959), pp. 480-483. MR0103993 (21 #2755).
- Michael Z. Spivey, A Combinatorial Proof for the Alternating Convolution of the Central Binomial Coefficients, The American Mathematical Monthly 121.6 (2014): 537-540. [Suggested by _Roger L. Bagula_, Jun 21 2014]
Programs
-
Magma
/* As triangle */ [[Binomial(2*k, k)*Binomial(2*n-2*k, n-k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Jul 19 2015
-
Mathematica
Table[Table[Binomial[2k,k]Binomial[2(n-k),n-k],{k,0,n}],{n,0,10}]//Grid (* Geoffrey Critzer, Jun 30 2013 *) T[ n_, k_] := SeriesCoefficient[ D[ InverseJacobiSN[2 x, m] / 2, x], {x, 0, 2 n}, {m, 0, k}]; (* Michael Somos, May 06 2017 *) -
PARI
T(n, k) = binomial(2*k, k) * binomial(2*n-2*k, n-k) /* Michael Somos, Aug 20 2005 */
Formula
T(n, k) = C(2k, k)*C(2n-2k, n-k) = C(2n, n)*C(n, k)^2/C(2n, 2k) = A000984(k)*A000984(n-k) = A000984(n)*A008459(n, k)/A007318(2n, 2k).
Row sums are 4^n = A000302(n).
G.f.: A(x,y) = 1/sqrt((1-4*x)*(1-4*x*y)). - Vladeta Jovovic, Dec 12 2003
Sum{k>=0} T(n, k)*(-3)^k = (-4)^n * A002426(n). Sum_{k>=0} T(n, k)/(2*k+1) = 2^(4*n)/((2*n+1)*C(2*n, n)). - Philippe Deléham, Dec 31 2003
O.g.f.: A(x,y) = 1 + x*d/dx(log(B(x,y))), where B(x,y) is the o.g.f. of A120406. - Peter Bala, Jul 17 2015
Comments