Date: Thu, 8 Aug 2013 02:14:19 +0100 From: Fred Lunnon <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Extending ballot numbers / Catalan triangle Message-ID: <CAN57YqtFfZLnmY6rDWqXGVuw7Xn6yoFV+S2wektV40BC-GQG+A@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1
I've been thinking about ballot numbers recently (the way one does), particularly in connection with RWG's campaign to clean up the binomial coefficient extension to negative arguments.
The traditional definition along the lines of B(n, k) == n+k_C_k (n-k)/(n+k) --- counting positive paths from (0, 0) to (n+k-1, n-k-1) --- breaks down when n+k = 0 , and makes proving identities awkward --- such as the fundamental convolution B(n, k) = \sum_j B(n-1-j, k-j) B(j+1, j) --- where in practice the range may be restricted to 0 <= j <= k .
A more robust definition which extends immediately to negative arguments, and allows the range above to be infinite, is instead B(n, k) == (n+k-1)_C_k - (n+k-1)_C_(k-1) ; naturally, the binomial coefficient n_C_k = 0 for k < 0 and all n . A short table is appended.
Do the numbers in the 2 o'clock sector have any interesting combinatorial significance? The only instance I have come across so far --- prompted by OEIS A000096, A005581 --- is that (-1)^k B(-n, k) apparently counts convex k-gons inscribed in a convex (n+k)-gon, with former vertices subset of latter and former edges disjoint from latter (proof?).
For n > 0 NJAS has collected relevant material under A009766 .
Fred Lunnon
# Maple program for Feller ballot number B(n, k) extended to n,k integer # counts number of positive paths from (0, 0) to (n+k-1, n-k-1) ballot := proc (n, k) binom(n+k-1, k) - binom(n+k-1, k-1) end;
m := 7; matrix([seq([seq(ballot(n, k), k = -m..m)], n = -m..m)]);
[0, 0, 0, 0, 0, 0, 0, 1, -8, 27, -50, 55, -36, 13, -2] [0, 0, 0, 0, 0, 0, 0, 1, -7, 20, -30, 25, -11, 2, 0] [0, 0, 0, 0, 0, 0, 0, 1, -6, 14, -16, 9, -2, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1, -5, 9, -7, 2, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1, -4, 5, -2, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1, -3, 2, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1, -2, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1, -1, -1, -1, -1, -1, -1, -1] [0, 0, 0, 0, 0, 0, 0, 1, 0, -1, -2, -3, -4, -5, -6] [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, -2, -5, -9, -14, -20] [0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 0, -5, -14, -28, -48] [0, 0, 0, 0, 0, 0, 0, 1, 3, 5, 5, 0, -14, -42, -90] [0, 0, 0, 0, 0, 0, 0, 1, 4, 9, 14, 14, 0, -42, -132] [0, 0, 0, 0, 0, 0, 0, 1, 5, 14, 28, 42, 42, 0, -132] [0, 0, 0, 0, 0, 0, 0, 1, 6, 20, 48, 90, 132, 132, 0]
--what do these have to do with "ballots"?