[math-fun] Extending ballot numbers / Catalan triangle
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]
Here's something I posted to the domino forum back in 1996: The recurrence relation C_n = ((4n-2)/(n+1)) C_{n-1} for the Catalan numbers can be turned backwards into the "precurrence" C_{n-1} = ((n+1)/(4n-2)) C_{n}. This formula eventually gives us zero (when n+1 vanishes) and gives us zero forever afterwards, but interestingly, with its "dying breath" the formula confides to us that the negative first Catalan number is -1/2. Is this just deathbed raving, or does this actually mean something? Jim On Wed, Aug 7, 2013 at 6:14 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
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]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For one thing, redefining C(-1) = -1/2 (?) has the consequence that the convolution C(n) = \sum{0 <= j < n} C(j) C(n-1-j) for n <> 0 could be rewritten \sum_j C(j) C(n-j) = 0 for n <> 0,1 (?) On the other hand, C(n) = (2n)_C_n - (2n)_C_(n-1) would then fail for n = -1 , whether you're bi-sectoral or (perish the thought) tri-sectoral ... Which reminds me, pace RWG --- my observations on bi-/tri-sectorality have been uploaded to https://www.dropbox.com/s/anykne0pd55ehjg/binomial.pdf Fred Lunnon On 8/8/13, James Propp <jamespropp@gmail.com> wrote:
Here's something I posted to the domino forum back in 1996:
The recurrence relation C_n = ((4n-2)/(n+1)) C_{n-1} for the Catalan numbers can be turned backwards into the "precurrence" C_{n-1} = ((n+1)/(4n-2)) C_{n}. This formula eventually gives us zero (when n+1 vanishes) and gives us zero forever afterwards, but interestingly, with its "dying breath" the formula confides to us that the negative first Catalan number is -1/2.
Is this just deathbed raving, or does this actually mean something?
Jim
On Wed, Aug 7, 2013 at 6:14 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
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]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Fred Lunnon <fred.lunnon@gmail.com> [Aug 08. 2013 16:01]:
[...]
Which reminds me, pace RWG --- my observations on bi-/tri-sectorality have been uploaded to https://www.dropbox.com/s/anykne0pd55ehjg/binomial.pdf
That'll go to arxiv.org, yes?
Fred Lunnon
[...]
On 08/08/2013 06:42, James Propp wrote:
Here's something I posted to the domino forum back in 1996:
The recurrence relation C_n = ((4n-2)/(n+1)) C_{n-1} for the Catalan numbers can be turned backwards into the "precurrence" C_{n-1} = ((n+1)/(4n-2)) C_{n}. This formula eventually gives us zero (when n+1 vanishes) and gives us zero forever afterwards, but interestingly, with its "dying breath" the formula confides to us that the negative first Catalan number is -1/2.
Is this just deathbed raving, or does this actually mean something?
Well, it simplifies the generating function from (1 - sqrt(1-4x)) / 2x to -sqrt(1-4x) / 2x. I'm not sure that's much more than raving, though. -- g
Only tenuously related, I suppose, but... Consider a race between N candidate c_N down to c_1, in which Each candidate c_i receives a total of i votes. Each candidate c_i receives his first vote before c_(i-1) and thereafter remains >= 1 vote ahead of c_(i-1). For N = 4, there are 12 voting sequences meeting these criteria: 4444333221 4444332321 4443433221 4443432321 4443343221 4443342321 4443324321 4434433221 4434432321 4434343221 4434342321 4434324321 Now suppose the race follows these rules Each candidate c_i receives a total of i votes. Each candidate c_i receives his first vote before c_(i-1) and thereafter remains 0 or 1 vote ahead of c_(i-1). For N = 4, there are again 12 voting sequences meeting these criteria: 4342341234 4342314234 4342312434 4342134234 4342132434 4324341234 4324314234 4324312434 4324134234 4324132434 4321434234 4321432434 It turns out that for both types of races, the number of voting sequences for N candidates is A003121(N). Colin Mallows termed the first type of voting sequence a "strict ballot" sequence, because each candidate stays strictly ahead of the next. He called the latter type "interleaved ballot" sequences because the votes of any two adjacent candidates are interleaved. I might call the latter type "close ballot" sequences, since each candidate stays close in votes to the next candidate. Dr. Mallows long ago submitted A003121 to count the first type of voting sequences, and later submitted a second, different sequence counting the second type of voting sequences. Yet later I stumbled on the latter sequence and in trying to extend it, found that some of the submitted values were incorrect, and when corrected seemed to agree with A003121. I related this to Dr. Mallows, who had the latter sequence removed from the OEIS, and soon sent me a very clever proof that both types voting sequences have the same counts (which I remember but have never published, being put off by LaTeX).
participants (5)
-
David Wilson -
Fred Lunnon -
Gareth McCaughan -
James Propp -
Joerg Arndt