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
Examples
[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.
References
- D. E. Knuth, TAOCP, Vol. 4a, Section 7.2.1.6, Eq. 22, p. 451.
Links
- P. Luschny, The lost Catalan numbers
Programs
-
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 *) -
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)]
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.
Comments