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

Comments

Since the triangle is symmetric, the probability that a one-dimensional random walk returns to the origin at all in the steps m through to 2m is 1/2 (for m odd).

Diagonal sums are A106183. - Paul Barry, Apr 24 2005

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]

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

Example

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

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

Prog

(PARI) {T(n, k) = binomial(2*k, k) * binomial(2*n-2*k, n-k) /* Michael Somos, Aug 20 2005 */
(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

Crossrefs

Columns include A000984, A028329. Central diagonal is A002894.

Cf. A002426, A120406.

Sequence in context: A092686 A249796 A182411 * A074911 A174222 A071059

Adjacent sequences: A067801 A067802 A067803 * A067805 A067806 A067807

Keyword

nonn,tabl

Author

Henry Bottomley, Feb 07 2002

Status

approved