A238762 Triangle read by rows, generalized ballot numbers, 0<=k<=n.

1, 0, 1, 1, 0, 1, 0, 2, 0, 3, 1, 0, 2, 0, 2, 0, 3, 0, 8, 0, 10, 1, 0, 3, 0, 5, 0, 5, 0, 4, 0, 15, 0, 30, 0, 35, 1, 0, 4, 0, 9, 0, 14, 0, 14, 0, 5, 0, 24, 0, 63, 0, 112, 0, 126, 1, 0, 5, 0, 14, 0, 28, 0, 42, 0, 42, 0, 6, 0, 35, 0, 112, 0, 252, 0, 420, 0, 462

Offset

0,8

Comments

Compare with the definition of the Motzkin triangle A238763.

References

D. E. Knuth, TAOCP, Vol. 4a, Section 7.2.1.6, Eq. 22, p. 451.

Links

Table of n, a(n) for n=0..77.

P. Luschny, The lost Catalan numbers

Formula

Definition: T(0, 0) = 1; T(p, q) = 0 if p < 0 or p > q; T(p, q) = T(p-2, q) + (q mod 2) T(p-1, q-1) + T(p, q-2). (The notation is in the style of Knuth, TAOCP 4a (7.2.1.6)).

T(2*k, 2*n) are the classical ballot numbers A009766(n, k).

T(2*k-1, 2*n-1) = A238761(n, k).

T(n,k) = c*A189231(a, b) with a = floor((n + k + (k mod 2))/2), b = floor((n-k)/2) and c = ((n+k+1) mod 2).

T(n, k) = ((n+k+1) mod 2)*(floor(n/2)+floor(k/2) + 1)^(k mod 2)) * (binomial(floor(n/2) + floor(k/2), floor(n/2)) - binomial( floor(n/2) + floor(k/2), floor(n/2) + 1)).

T(n, k) = ((n+k+1) mod 2)*(floor(n/2)+floor(k/2) + 1)^(k mod 2)) *(floor((n-k)/2) + 1)/(floor(n/2) + 1) * binomial( floor(n/2) + floor(k/2), floor(n/2)).

T(n, n) = A057977(n).

T(n, n-2) = A238452(n-1).

Row sums are A238879.

Example

[n\k 0  1  2   3  4   5   6   7]
[0]  1,
[1]  0, 1,
[2]  1, 0, 1,
[3]  0, 2, 0,  3,
[4]  1, 0, 2,  0, 2,
[5]  0, 3, 0,  8, 0, 10,
[6]  1, 0, 3,  0, 5,  0, 5,
[7]  0, 4, 0, 15, 0, 30, 0, 35.

Maple

binom2 := proc(n, k) local h;
   h := n -> (n-((1-(-1)^n)/2))/2;
   n!/(h(n-k)!*h(n+k)!) end:
A238762 := proc(n, k) local a, b, c;
   a := iquo(n+k+2+modp(n, 2), 2);
   b := iquo(n-k+2, 2);
   c := modp(n+k+1, 2);
   binom2(a, b)*b*c/a end:
seq(print(seq(A238762(n, k), k=0..n)), n=0..7);
# Alternativ:
ballot := proc(p, q) option remember;
    if p = 0 and q = 0 then return 1 fi;
    if p < 0 or  p > q then return 0 fi;
    ballot(p-2, q) + ballot(p, q-2);
    if type(q, odd) then % + ballot(p-1, q-1) fi;
    % end:

Mathematica

T[n_, k_] := T[n, k] = Which[k == 0 && n == 0, 1, k < 0 || k > n, 0, True, s = T[n, k - 2] + T[n - 2, k]; If[OddQ[n], s += T[n - 1, k - 1]]; s];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 10 2019, adapted from Sage code *)

Prog

(Sage)
@CachedFunction
def ballot(p, q):
    if p == 0 and q == 0: return 1
    if p < 0 or p > q: return 0
    S = ballot(p-2, q) + ballot(p, q-2)
    if q % 2 == 1: S += ballot(p-1, q-1)
    return S
for q in range(8): [ballot(p, q) for p in (0..q)]

Crossrefs

Cf. A009766, A189231, A238761, A238879.

Sequence in context: A079133 A143143 A158853 * A269517 A190440 A054372

Adjacent sequences: A238759 A238760 A238761 * A238763 A238764 A238765

Keyword

nonn,tabl

Author

Peter Luschny, Mar 05 2014

Status

approved