Sage: Ticket #17123: Extending binomial(n,k) to negative integers n, k.
https://trac.sagemath.org/ticket/17123
<p>
A simple and coherent extension of the binomial function
to negative integers n, k was outlined by M. J. Kronenburg in
The Binomial Coefficient for Negative Arguments,
<a class="ext-link" href="http://arxiv.org/abs/1105.3689"><span class="icon"></span>http://arxiv.org/abs/1105.3689</a>
(Thanks to John Palmieri for the reference.)
</p>
<p>
This extension amounts to define
</p>
<pre class="wiki">def BINOMIAL(n, k):
if n in ZZ and k in ZZ:
if n >= 0 and k >= 0:
return binomial(n, k)
if k >= 0:
return (-1)^k*binomial(-n+k-1, k)
if k <= n:
return (-1)^(n-k)*binomial(-k-1, n-k)
return 0
else:
return binomial(n, k)
</pre><p>
Here 'BINOMIAL' is the targeted version, 'binomial' the
implemented version. The targeted behaviour is identical
to the behaviour of the Maple and Mathematica function
for negative integers n, k.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/17123
Trac 1.1.6vbraunThu, 09 Oct 2014 16:57:37 GMT
https://trac.sagemath.org/ticket/17123#comment:1
https://trac.sagemath.org/ticket/17123#comment:1
<p>
You'll have our eternal gratitude if you can post a git branch with the change ;-)
</p>
TicketSimonKingThu, 09 Oct 2014 17:22:11 GMT
https://trac.sagemath.org/ticket/17123#comment:2
https://trac.sagemath.org/ticket/17123#comment:2
<p>
Certainly there should not be implemented a modified and renamed binomial function in addition to the existing monomial function. The existing should just be extended to the case of negative input.
</p>
TicketpluschnyThu, 09 Oct 2014 17:31:32 GMT
https://trac.sagemath.org/ticket/17123#comment:3
https://trac.sagemath.org/ticket/17123#comment:3
<p>
Volker, what is the reason for your sarcasm?
</p>
<p>
Simon, certainly. But only in this form I could test it against the implemented version without running into a recursion.
</p>
TicketvbraunThu, 09 Oct 2014 19:14:24 GMT
https://trac.sagemath.org/ticket/17123#comment:4
https://trac.sagemath.org/ticket/17123#comment:4
<p>
I'm not sarcastic, just trying to nudge you into the right direction ;-)
</p>
TicketSimonKingThu, 09 Oct 2014 19:18:17 GMT
https://trac.sagemath.org/ticket/17123#comment:5
https://trac.sagemath.org/ticket/17123#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:3" title="Comment 3">pluschny</a>:
</p>
<blockquote class="citation">
<p>
Volker, what is the reason for your sarcasm?
</p>
</blockquote>
<p>
It could be that he thinks that fixing the problem is a matter of not more than 30 minutes. But if I understand correctly you have no experience with Sage development, yet. And I think Volker should take this into account.
</p>
<blockquote class="citation">
<p>
Simon, certainly. But only in this form I could test it against the implemented version without running into a recursion.
</p>
</blockquote>
<p>
The implemented version just raises an error on negative input. Instead of raising the error, the binomial function should simply modify the given negative arguments according to the formula that you present in the ticket description.
</p>
<p>
Then, the documentation of the binomial function should be modified to contain a description and a test for the new behaviour. And to be on the safe side, the test suite should be run.
</p>
<p>
When working on a ticket, one ought to create a git branch for the ticket. The documentation will tell you how. For example, if you have the git trac scripts installed, you can do <code>git trac checkout 17123</code> on the commandline.
</p>
<p>
How to edit the binomial function?
First way: Find out in what module the function is defined.
</p>
<pre class="wiki">sage: binomial.__module__
'sage.functions.other'
</pre><p>
Hence, take your favourite editor and edit `SAGE_ROOT/src/sage/functions/other.py
</p>
<p>
Second way: In a running Sage session, do
</p>
<pre class="wiki">sage: edit(binomial, 'vim')
</pre><p>
where vim is your favourite editor. It will open the correct file in the correct line (if not, report a bug!).
</p>
<p>
After saving the change, leave Sage and do <code>make</code> (which will also build the changes in the documentation) or better <code>make test</code> in order to also run the test suite of Sage.
</p>
<p>
If everything works, commit your changes (<code>git commit -a</code>) and push them to this ticket (with the git trac scripts, this is <code>git trac push</code>).
</p>
TicketSimonKingThu, 09 Oct 2014 19:20:51 GMT
https://trac.sagemath.org/ticket/17123#comment:6
https://trac.sagemath.org/ticket/17123#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:5" title="Comment 5">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
The implemented version just raises an error on negative input.
</p>
</blockquote>
<p>
Oops, I stand corrected. No error.
</p>
TicketSimonKingThu, 09 Oct 2014 19:31:35 GMT
https://trac.sagemath.org/ticket/17123#comment:7
https://trac.sagemath.org/ticket/17123#comment:7
<p>
Volker, it actually seems to me that the change is not totally straight forward.
</p>
<p>
There is the <code>_eval_</code> method, and the <code>_evalf_</code> method. Probably both need to be changed.
</p>
<p>
And there is the <code>_binomial_sym</code> method. Will this need a change as well? It currently returns zero if the second argument is negative:
</p>
<pre class="wiki">sage: binomial._binomial_sym(x,-5)
0
</pre><p>
Should the return value be a different symbolic expression? After all, the value (according to the formula in the ticket description) is not zero if x evaluates to a negative number that is greater or equal to <code>-5</code>.
</p>
<p>
So, here I don't know a good answer.
</p>
TicketvbraunThu, 09 Oct 2014 21:11:38 GMT
https://trac.sagemath.org/ticket/17123#comment:8
https://trac.sagemath.org/ticket/17123#comment:8
<p>
I know that there is a learning curve, but once you figure it out it is a very efficient workflow. So what I'm trying to say is: Its worthwhile to figure out how to use git.
</p>
<p>
<code>_eval_</code> and <code>_evalf_</code> punt to either <code>_binomial_sym</code> (for symbolic expressions) or <code>sage.rings.arith.binomial</code> (for numbers), so both of the latter need to be changed.
</p>
TicketjhpalmieriThu, 09 Oct 2014 21:27:16 GMT
https://trac.sagemath.org/ticket/17123#comment:9
https://trac.sagemath.org/ticket/17123#comment:9
<p>
Note the current situation:
</p>
<pre class="wiki">sage: binomial(-1, -1)
0
</pre><p>
So presumably the change here would require a deprecation warning.
</p>
<p>
Apparently Maple and Mathematica use the proposed version. Is that sufficient justification to change our version? Note that currently we have <code>binomial(n-1, k-1) + binomial(n-1,k) == binomial(n,k)</code>, and I believe this change would break that identity. (So I'm not sure I would agree with the word "coherent" describing this extension of the binomial function.) If we want to make this change, then maybe we should bifurcate and have a separate Pascal's triangle function which still preserves the identity? See also <a class="ext-link" href="http://en.wikipedia.org/wiki/Pascal's_triangle#Extensions"><span class="icon"></span>http://en.wikipedia.org/wiki/Pascal's_triangle#Extensions</a>.
</p>
TicketvbraunThu, 09 Oct 2014 21:54:16 GMT
https://trac.sagemath.org/ticket/17123#comment:10
https://trac.sagemath.org/ticket/17123#comment:10
<p>
TFA talks about gamma functions in the abstract, so I would have thought that it matches the extension that we would all write down (and is in the wp article)... though I haven't read it ;-)
</p>
TicketpluschnyThu, 09 Oct 2014 23:40:50 GMT
https://trac.sagemath.org/ticket/17123#comment:11
https://trac.sagemath.org/ticket/17123#comment:11
<p>
Volker, acronyms are nice for those who understand. Do I have to understand 'TFA' or 'wp'?
</p>
TicketpluschnyThu, 09 Oct 2014 23:42:00 GMT
https://trac.sagemath.org/ticket/17123#comment:12
https://trac.sagemath.org/ticket/17123#comment:12
<p>
John, this is why I offered to discuss things first on sage-devel and hear more arguments.
</p>
<p>
"Apparently Maple and Mathematica use the proposed version. Is that sufficient justification to change our version?"
</p>
<p>
Of course not, although for me this is a strong hint that something is missing in the current Sage implementation.
</p>
<p>
But this is a reason:
</p>
<pre class="wiki">sage: binomial(-1, -1)
0
</pre><p>
More generally, binomial(z, z) != 1 is absurd, a bug IMO, and definitely a reason to change things. binomial(z, z) = 1 for all z is the first thing to be preserved.
Next the relation of the diagonals to the Fibonacci numbers is another important thing which should be preserved (and the proposed extension does this although apparently Kronenburg misses to mention this in his paper).
The additive formula is nice in the region where the formula applies, but the multiplicative formula is the more important one, a viewpoint taken by all major modern authors as far as I understand.
</p>
TicketdarijFri, 10 Oct 2014 03:43:15 GMT
https://trac.sagemath.org/ticket/17123#comment:13
https://trac.sagemath.org/ticket/17123#comment:13
<p>
Please do not change the current version. No, Peter, your convention is not standard in any way. Read anything by Knuth and you will see that <code>binomial(n, k) == 0</code> for negative k (no matter what n is) is standard, and this happens to be the current behavior (I don't know why people are saying that it is currently undefined). Having <code>binomial(z, z) != 1</code> is collateral damage, but there is no way that could be fixed reasonably.
</p>
<p>
Feel free to add <code>binomial_symmetrized</code> or whatever else you want to call your function, however!
</p>
TicketrwsFri, 10 Oct 2014 04:18:54 GMTcc set
https://trac.sagemath.org/ticket/17123#comment:14
https://trac.sagemath.org/ticket/17123#comment:14
<ul>
<li><strong>cc</strong>
<em>rws</em> added
</li>
</ul>
TicketvbraunFri, 10 Oct 2014 12:15:51 GMT
https://trac.sagemath.org/ticket/17123#comment:15
https://trac.sagemath.org/ticket/17123#comment:15
<p>
We could also have an optional keyword argument <code>binomial(n, k, extension='Knuth')</code>
</p>
TicketrwsFri, 10 Oct 2014 14:46:07 GMT
https://trac.sagemath.org/ticket/17123#comment:16
https://trac.sagemath.org/ticket/17123#comment:16
<p>
The pseudocode in the ticket description does not seem to fit the paper given as reference, quote:
</p>
<pre class="wiki">For nonnegative integer n and integer k this reduces to [1]:
(1.2) binomial(n,k) = n!/(k!(n-k)!) if 0<=k<=n, 0 otherwise
... This results in the following binomial coefficient identity,
which with identity (1.2) allows computation of the binomial coefficient for all integer
arguments.
(2.1) Theorem 2.1. For negative integer n and integer k:
binomial(n,k) = (-1)^k * binomial(-n+k-1,k) if k>0,
(-1)^(n-k) * binomial(-k-1,n-k) if k<=n,
0 otherwise
...
</pre><p>
so in my opinion the definition should rather be
</p>
<pre class="wiki">def BINOMIAL(n, k):
if n in ZZ and k in ZZ:
if n >= 0:
return binomial(n, k)
if k >= 0:
return (-1)^k*binomial(-n+k-1, k)
if k <= n:
return (-1)^(n-k)*binomial(-k-1, n-k)
return 0
else:
return binomial(n, k)
</pre><p>
This leaves a discrepancy between <code>binomial(*,k<0)</code> and <code>BINOMIAL(*,k<0)</code> in the area <code>n<0, k<n</code> and to get to the point I would ask darij to provide a Knuth reference that supports the behaviour of <code>binomial</code> for these values.
</p>
TicketpluschnyFri, 10 Oct 2014 19:32:57 GMT
https://trac.sagemath.org/ticket/17123#comment:17
https://trac.sagemath.org/ticket/17123#comment:17
<p>
Ralf, a quick numerical check did not show any difference:
</p>
<pre class="wiki"> for n in (-4..4):
print "plu", [n], [BINOMIAL (-n , -k) for k in (-6..6)]
print "rws", [n], [BINOMIALrws(-n , -k) for k in (-6..6)]
</pre><p>
So please give one counterexample (n,k) where the definitions differ.
</p>
<p>
But I do prefer my form over your form. I write
</p>
<pre class="wiki"> if n >= 0 and k >= 0:
return binomial(n, k)
</pre><p>
and this makes it perfectly clear that in this region nothing
changes, that all changes apply only to negative integers.
I think this lowers the burden of understanding the code.
Darij: "... your convention is not standard in any way."
</p>
<p>
(1) If it were standard it would be pointless to call
it an 'extension'.
(2) As an extension it is standard for more than a quarter
of a century due to the fact that both Maple and Mathematica
use this extension ever since the beginning.
</p>
<p>
(3) So even if you prefer not to use this extension in
your papers using Sage will give you different results
than many of your colleagues will get with different software.
</p>
<p>
And indeed this was for me the motivation to write this
ticket: I found the confusion annoying which shows up in
many places in the code on OEIS because the systems behave
differently and that this fact is often overlooked. Nobody
expects this to happen with a standard function like 'binomial'.
</p>
<p>
Therefore I would even prefer a "value error" (or what
it is called) for arguments not in the range 0<=k<=n
for integer k, n, over the current behaviour of Sage.
</p>
<p>
Darij: "I don't know why people are saying that it is
currently undefined."
</p>
<p>
This is the difference between a formal "... otherwise 0"
and a definition guided by mathematical considerations
which aims to enlarge relations to the largest possible
region of validity. (Instead accepting things like
binomial(z, z) != 1 as a collateral damage.)
</p>
TicketnbruinFri, 10 Oct 2014 23:46:53 GMT
https://trac.sagemath.org/ticket/17123#comment:18
https://trac.sagemath.org/ticket/17123#comment:18
<p>
Maxima's documentation on the matter is silent, so I'd be hesitant to take it as authoritative on the matter, but your proposed code is at odds with maxima's for (n,n) with n negative (maxima gives zero in that case). Deviating from maxima requires careful planning because expressions can quite easily end up in maxima.
</p>
<pre class="wiki">sage: [ (n,k) for n in [-10..10] for k in [-10..10] if BINOMIAL(n,k) !=maxima_calculus.binomial(n,k)]
[(-10, -10),
(-9, -9),
(-8, -8),
(-7, -7),
(-6, -6),
(-5, -5),
(-4, -4),
(-3, -3),
(-2, -2),
(-1, -1)]
</pre>
TicketdarijSat, 11 Oct 2014 02:07:33 GMT
https://trac.sagemath.org/ticket/17123#comment:19
https://trac.sagemath.org/ticket/17123#comment:19
<p>
Peter:
</p>
<p>
(1) If it is an extension, then call it <code>binomial_extension</code> or whatever; do not usurp <code>binomial</code>.
</p>
<p>
(2) Maple and Mathematica do not set standards in combinatorics.
</p>
<p>
The 0 definition does enlarge a relation to its largest possible domain of validity -- the recurrence relation, to the whole integer lattice. Unlike the symmetry, the recurrence actually is used all the time in proofs. The 0 definition also matches with the idea that (-1)<sup>k (-n choose k) is the number of k-element multisets of elements of {1, 2, ..., n}. It is most definitely guided by mathematical consideration; check, e.g., the identities (5.22) to (5.26) in Graham-Knuth-Patashnik, specifically (5.22) (Vandermonde's convolution, an extremely important identity). It might not be the most interesting definition, but we should not be aiming for that; I don't think we want 1 + 2 + 3 + ... to yield -1/12 just because the most interesting definition for summing powers of positive integers involves the zeta function. We should be going for the definition which is the most reliable and standard in *mathematical* literature. And here it is the 0 one.
</sup></p>
TicketpluschnySat, 11 Oct 2014 07:50:03 GMT
https://trac.sagemath.org/ticket/17123#comment:20
https://trac.sagemath.org/ticket/17123#comment:20
<p>
Darij: "If it is an extension, then call it <code>binomial_extension</code>
or whatever; do not usurp <code>binomial</code>."
</p>
<p>
Volker's proposal above is: "We could also have an optional
keyword argument binomial(n, k, extension='Knuth')". This
looks like a good idea to me, perhaps better with the name
'symmetrical' instead of 'Knuth'.
Darij: "Maple and Mathematica do not set standards in combinatorics."
</p>
<p>
But you can also not ignore them especially as Sage's
mission is to become a viable alternative to theses systems.
</p>
<p>
"We should be going for the definition which is the most
reliable and standard in *mathematical* literature. And
here it is the 0 one."
</p>
<p>
I agree. But this does not mean that we should block
interesting developments either. Volker's proposal shows
the way.
</p>
<p>
On a side note: Don Knuth is known to be happily hacking
with Mathematica for a long time
<a class="ext-link" href="http://www-cs-faculty.stanford.edu/~uno/screen.jpeg"><span class="icon"></span>http://www-cs-faculty.stanford.edu/~uno/screen.jpeg</a>
and reading his 'Convolution Polynomials' with it's many
implicit and explicit uses of the binomial function I
do not see him complain about the way Mathematica defines it.
</p>
TicketvbraunSat, 11 Oct 2014 10:43:59 GMT
https://trac.sagemath.org/ticket/17123#comment:21
https://trac.sagemath.org/ticket/17123#comment:21
<p>
As a string theorist, I approve of 1+2+3+... = -1/12 ;-)
</p>
TicketchapotonFri, 28 Jul 2017 13:56:38 GMT
https://trac.sagemath.org/ticket/17123#comment:22
https://trac.sagemath.org/ticket/17123#comment:22
<p>
I have just been hurt by that issue, and I would like to change the current behaviour. In the usual hypergeometric context, having binomial(-1,-1)=1 would be the only natural thing to do. The current binomial(-1,-1)=0 forces me to do special-casing everywhere in my code, which I take as a very good sign that this is a bad convention.
</p>
TicketpluschnyFri, 28 Jul 2017 15:14:24 GMT
https://trac.sagemath.org/ticket/17123#comment:23
https://trac.sagemath.org/ticket/17123#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:22" title="Comment 22">chapoton</a>:
</p>
<blockquote class="citation">
<p>
I have just been hurt by that issue, and I would like to change the current behaviour.
</p>
</blockquote>
<p>
This is great! I have also written on my OEIS blog about it:
<a class="ext-link" href="http://oeis.org/wiki/User:Peter_Luschny/ExtensionsOfTheBinomial"><span class="icon"></span>Extensions of the Binomial</a>
</p>
TicketjhpalmieriFri, 28 Jul 2017 15:36:49 GMT
https://trac.sagemath.org/ticket/17123#comment:24
https://trac.sagemath.org/ticket/17123#comment:24
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:22" title="Comment 22">chapoton</a>:
</p>
<blockquote class="citation">
<p>
I have just been hurt by that issue, and I would like to change the current behaviour. In the usual hypergeometric context, having binomial(-1,-1)=1 would be the only natural thing to do. The current binomial(-1,-1)=0 forces me to do special-casing everywhere in my code, which I take as a very good sign that this is a bad convention.
</p>
</blockquote>
<p>
As pointed out elsewhere on this ticket, making the proposed change breaks the identity <code>binomial(n-1, k-1) + binomial(n-1,k) == binomial(n,k)</code>, which suggests to me that the proposed change is a bad convention. That is, there are arguments on both sides. I think adding an optional argument to get the behavior you want might be the best solution.
</p>
TicketchapotonFri, 28 Jul 2017 16:01:05 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/17123#comment:25
https://trac.sagemath.org/ticket/17123#comment:25
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_info</em>
</li>
<li><strong>commit</strong>
set to <em>0c994379b150158c84ee583369f2ee4428a35f44</em>
</li>
<li><strong>branch</strong>
set to <em>u/chapoton/17123</em>
</li>
</ul>
<p>
I am not convinced at all by the desire (why ?) to get the usual recursion extend to all k and n. Instead, I am doing concrete and complicated hypergeometric computations right now, where I am put in trouble by the fact that sage currently says that binomial(-1,-1) is 0.
</p>
<p>
But I am worried by the different behaviour in Maxima, saying binomial(-1,-1)=0. We also have giac, that says binomial(-1,-1)=1.
</p>
<pre class="wiki">sage: a=ZZ(-1)
sage: a._giac_().binomial(-1)
1
sage: a._maxima_().binomial(-1)
0
sage: a.__pari__().binomial(-1)
0
</pre><hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=0c994379b150158c84ee583369f2ee4428a35f44"><span class="icon"></span>0c99437</a></td><td><code>trac 17123 change values of binomial(n, k) for negative k and n</code>
</td></tr></table>
TicketchapotonFri, 28 Jul 2017 16:02:30 GMT
https://trac.sagemath.org/ticket/17123#comment:26
https://trac.sagemath.org/ticket/17123#comment:26
<p>
And sympy does not know the answer:
</p>
<pre class="wiki">sage: a=ZZ(-1)
sage: a._sympy_().binomial(-1)
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
<ipython-input-11-c88f55965f06> in <module>()
----> 1 a._sympy_().binomial(-Integer(1))
AttributeError: 'NegativeOne' object has no attribute 'binomial'
</pre><p>
<strong>*EDIT</strong>*
</p>
<p>
Sympy doc says : For the sake of convenience for negative ‘k’ this function will return zero no matter what valued is the other argument.
</p>
TicketpluschnyFri, 28 Jul 2017 16:28:26 GMT
https://trac.sagemath.org/ticket/17123#comment:27
https://trac.sagemath.org/ticket/17123#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:24" title="Comment 24">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
As pointed out elsewhere on this ticket, making the proposed change breaks the identity <code>binomial(n-1, k-1) + binomial(n-1,k) == binomial(n,k)</code>, which suggests to me that the proposed change is a bad convention.
</p>
</blockquote>
<p>
This is not true. With the solution shown in my blog linked above the identity
remains valid. <a class="ext-link" href="http://luschny.de/temp/ExtendedBinomial.html"><span class="icon"></span>See here.</a>
</p>
<p>
And it would be far more sensible instead of offering different versions
because of some special cases to seek a consistent mathematical solution.
</p>
TicketchapotonFri, 28 Jul 2017 18:55:34 GMT
https://trac.sagemath.org/ticket/17123#comment:28
https://trac.sagemath.org/ticket/17123#comment:28
<p>
Summary:
</p>
<p>
One single natural idea : use the expression of Binomial in term of Gamma functions
</p>
<p>
==> this gives unique and well-defined values for all integers (n,k)
</p>
<p>
==> for k >= 0, these values are the same as the ones coming from the polynomiality in n
</p>
<p>
==> the addition rule works everywhere but for (-1,-1)+(-1,0) != (0,0)
</p>
<p>
==> this works very well in the context of hypergeometric series, where the natural way to extend binomials is to pass to Gamma products.
</p>
<p>
==> and this satisfies the symmetry property (n,k) = (n, n-k)
</p>
<p>
So it seems to me that we have very good reasons to change. I am also personnally totally convinced that this is the only <strong>correct convention</strong> and that setting blandly to 0 was just done by some kind of lazyness.
</p>
<p>
Would it be useful to ask the opinion of one of the great masters of hypergeometric series ?
</p>
TicketdarijFri, 28 Jul 2017 18:59:27 GMT
https://trac.sagemath.org/ticket/17123#comment:29
https://trac.sagemath.org/ticket/17123#comment:29
<p>
I am strongly against changing the results on the current domain of definition, whatever this is (it's been a while...). I don't remember whether it currently computes binomial(n, k) to 0 for k < 0, but if it does, we cannot just deprecate it. At the very least we need to create a function that replicates this behavior.
</p>
<p>
There are various sums in combinatorics which sort-of rely on the "zero for k < 0" behavior, because modifying their bounds to get rid of the k < 0 case is impractical (this leads to stupid bounds like floors and ceilings). I suspect that in many of these cases, the n on top of the binomial coefficient is nonnegative (and you are not making changes to this case, right?), but I wouldn't expect this to hold for ALL of these sums.
</p>
TicketchapotonFri, 28 Jul 2017 19:21:30 GMT
https://trac.sagemath.org/ticket/17123#comment:30
https://trac.sagemath.org/ticket/17123#comment:30
<p>
Hello, Darij. I hear your preoccupation, but I do not quite understand it. Do you have one concrete case to show me ?
</p>
<p>
I have one supporting the change : consider
</p>
<pre class="wiki">sum(binomial(n, i) * binomial(n - i - l - 1, i - 1) *
x ** i * y ** l for i in range(1, floor(n/2) + 1)
for l in range(n - 2 * i + 1))
</pre><p>
This gives for me the result that I expect if and only if binomial(-1,-1)=1.
</p>
<p>
The proposal would change the value when both n and k are negative, from 0 (now) to some integers obtained as limits of Gamma products.
</p>
<p>
Of course, we can easily propose either an "old_binomial" function or an "oldstyle" keyword. What would you prefer ?
</p>
TicketdarijFri, 28 Jul 2017 19:42:52 GMT
https://trac.sagemath.org/ticket/17123#comment:31
https://trac.sagemath.org/ticket/17123#comment:31
<p>
What would the expected result be?
</p>
<p>
Here is an example:
</p>
<pre class="wiki">binom = binomial
def lr(n, k):
return sum(binom(n+u-1, u) * binom(n, k-2*u) for u in range(k+1)) - binom(n+k-1, k)
</pre><p>
This should yield 0 for all n and k. (See <a class="ext-link" href="http://www.cip.ifi.lmu.de/~grinberg/QEDMO4P13.pdf"><span class="icon"></span>http://www.cip.ifi.lmu.de/~grinberg/QEDMO4P13.pdf</a> for a proof for n and k nonnegative. It then follows for all n because both sides are polynomials in n. Finally, the k < 0 case is simply a 0 = 0 statement.)
</p>
<p>
If your definition breaks it for negative k, okay. But if it breaks it for positive k and negative n, then your definition is bad. Changing the bound of the sum to something like floor(k/2) is exactly the kind of annoyance that a good definition avoids!
</p>
TicketchapotonFri, 28 Jul 2017 20:11:29 GMT
https://trac.sagemath.org/ticket/17123#comment:32
https://trac.sagemath.org/ticket/17123#comment:32
<p>
Well, this identity of yours stays true for all n and k>=0 if you use the floor bound.
</p>
<p>
I would like to argue that not using a floor bound is correct if n > 0, but is not the good way to go if n < 0.
</p>
<p>
Enough for today..
</p>
TicketrwsSat, 29 Jul 2017 06:32:53 GMT
https://trac.sagemath.org/ticket/17123#comment:33
https://trac.sagemath.org/ticket/17123#comment:33
<p>
From all this it seems to me the best way to resolve this issue is by providing an additional function. Deprecation can then be discussed in a new ticket. The name <code>C</code> comes to mind. Please give your naming ideas too.
</p>
TicketmantepseSat, 29 Jul 2017 07:16:43 GMT
https://trac.sagemath.org/ticket/17123#comment:34
https://trac.sagemath.org/ticket/17123#comment:34
<blockquote class="citation">
<p>
One single natural idea : use the expression of Binomial in term of Gamma functions
</p>
<p>
==> this gives unique and well-defined values for all integers (n,k)
</p>
</blockquote>
<p>
I must be misunderstanding: the function <code>f(x,y) = gamma(x + 1) / (gamma(y + 1)*gamma(x - y + 1))</code> is singular when <code>x</code> is a negative integer. See "The Binomial Coefficient Function, David Fowler, The American Mathematical Monthly, Vol. 103, No. 1 (Jan., 1996), pp. 1-17" for an analysis.
</p>
<p>
Still, I think it would be practical to define the binomial coefficient in this way, throwing an error when the limit does not exist. Then it becomes very easy for the user to extend it whenever necessary, because she can catch the exception. This
solution also has the advantage of making the conventions explicit in all methods.
</p>
<p>
I think the solution of defining the binomial coefficient as
<code>binomial(x0, y0)=limit(limit(f(x,y), y=y0), x=x0)</code>
(in this order) is inferior, because it yields surprising results, in particular <code>binomial(-1,-1)=0</code>.
</p>
TicketpluschnySat, 29 Jul 2017 07:26:59 GMT
https://trac.sagemath.org/ticket/17123#comment:35
https://trac.sagemath.org/ticket/17123#comment:35
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:34" title="Comment 34">mantepse</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
One single natural idea : use the expression of Binomial in term of Gamma functions
</p>
<p>
==> this gives unique and well-defined values for all integers (n,k)
</p>
</blockquote>
<p>
I must be misunderstanding: the function <code>f(x,y) = gamma(x + 1) / (gamma(y + 1)*gamma(x - y + 1))</code> is singular when <code>x</code> is a negative integer.
I think the solution of defining the binomial coefficient as
<code>binomial(x0, y0)=limit(limit(f(x,y), y=y0), x=x0)</code>
(in this order) is inferior, because it yields surprising results, in particular <code>binomial(-1,-1)=0</code>.
</p>
</blockquote>
<p>
Yes, you are misunderstanding. Try this:
</p>
<pre class="wiki">def limit_binomial(n, k):
return limit(gamma(n + x) / (gamma(k + x)*gamma(n - k + x)), x = 1)
for n in (-5..5): print [limit_binomial(n, k) for k in (-5..5)]
limit_binomial(-1,-1) = 1
</pre><p>
All been said in my blog post linked above.
</p>
TicketmantepseSat, 29 Jul 2017 08:23:22 GMT
https://trac.sagemath.org/ticket/17123#comment:36
https://trac.sagemath.org/ticket/17123#comment:36
<p>
OK, I thought that Frederic was referring to the other expression of the binomial in terms of the gamma function. I was further misled by another blog post saying that Mathematica uses the iterated limit definition.
</p>
<p>
So, one question is whether sage should use
</p>
<pre class="wiki">limit(gamma(x0 + h) / (gamma(y0 + h)*gamma(x0-y0+h)), h=1)
</pre><p>
or
</p>
<pre class="wiki">limit(gamma(x + 1) / (gamma(y + 1)*gamma(x-y+1)), (x,y)=(x0,y0))
</pre><p>
as definition, and you are saying that the first is better, because it is works always, right?
</p>
TicketpluschnySat, 29 Jul 2017 09:38:53 GMT
https://trac.sagemath.org/ticket/17123#comment:37
https://trac.sagemath.org/ticket/17123#comment:37
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:36" title="Comment 36">mantepse</a>:
</p>
<blockquote class="citation">
<p>
you are saying that the first is better, because it is works always, right?
</p>
</blockquote>
<p>
Yes. And I'm sure that Mathematica also uses it contrary to your information
because otherwise they would have similar problems as the ones you ran into.
But they do not have problems.
</p>
<p>
Note that this argument (embedding into C in conformance to hypergeometric
considerations) is only one argument.
</p>
<p>
Also from the combinatorial point of view it makes sense to define:
</p>
<pre class="wiki"> def Binomial(n, k):
if n in ZZ and k in ZZ:
if n >= 0:
return binomial(n, k)
if k >= 0:
return (-1)^k*binomial(-n+k-1, k)
if k <= n:
return (-1)^(n-k)*binomial(-k-1, n-k)
return 0
return binomial(n, k)
</pre><p>
You can use this definition with 'binomial' taking Sage's current binomial.
</p>
<p>
The reflection property of the binomial numbers is similar and
related to the reflection property of the Stirling numbers
{n,k} = [-k,-n] and of the Lah numbers L|n,k| = L| -k,-n|.
This has been observed by Riordan, Knuth and others.
</p>
TicketmantepseSat, 29 Jul 2017 11:39:06 GMT
https://trac.sagemath.org/ticket/17123#comment:38
https://trac.sagemath.org/ticket/17123#comment:38
<p>
I think that I dislike the fact that your definition (by the way: is it yours? otherwise, do you have a reference?) is not continuous.
</p>
<p>
Can we assume that everybody agrees that for <code>x</code> not negative integral, <code>gamma(x+1)/(gamma(y+1)*gamma(x-y+1))</code> is a good definition of <code>binomial(x,y)</code>?
</p>
<p>
Do (at least the more important) packages agree on these values, and disagreement is only for negative integral <code>x</code>?
</p>
<p>
If so, wouldn't it still be best to define <code>binomial</code> with an optional argument, <code>extension</code>, which defaults to <code>None</code>. Then we could even emulate the behaviour of other packages, whenever useful.
</p>
<p>
I think it is safest to have the optional argument being <code>None</code>, sage could throw a useful error in this case. Then we get an additional check of the usage of binomial in the sage library.
</p>
TicketpluschnySat, 29 Jul 2017 12:49:25 GMT
https://trac.sagemath.org/ticket/17123#comment:39
https://trac.sagemath.org/ticket/17123#comment:39
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:38" title="Comment 38">mantepse</a>:
</p>
<blockquote>
<p>
"..your definition (by the way: is it yours? otherwise,
do you have a reference?).."
</p>
</blockquote>
<p>
I do not claim any originality whatsoever with this definition.
For references see what I have written on my blog linked above,
and the references given there.
</p>
<p>
"Can we assume that everybody agrees that for <code>x</code> not negative integral,
</p>
<blockquote>
<p>
<code>gamma(x+1)/(gamma(y+1)*gamma(x-y+1))</code> is a good definition of <code>binomial(x,y)</code>?"
</p>
</blockquote>
<p>
Pardon me? No, what is g(x,y) for x = 1, y = -1 with this 'definition'?
</p>
<p>
An extension which does not give the reflection formula for the binomial
</p>
<p>
<code> binomial(-k, -n) = (-1)^(n-k) binomial(n-1, k-1) </code>
</p>
<p>
is completely worthless, potentially introducing new errors.
</p>
<p>
"I think it is safest to have the optional argument being <code>None</code>.. ""
</p>
<p>
Three years ago Volker Braun suggested above:
</p>
<p>
"We could also have an optional keyword argument binomial(n, k, extension='Knuth')."
</p>
TicketdarijSat, 29 Jul 2017 13:11:31 GMT
https://trac.sagemath.org/ticket/17123#comment:40
https://trac.sagemath.org/ticket/17123#comment:40
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:39" title="Comment 39">pluschny</a>:
</p>
<blockquote class="citation">
<p>
An extension which does not give the reflection formula for the binomial
</p>
<p>
<code> binomial(-k, -n) = (-1)^(n-k) binomial(n-1, k-1) </code>
</p>
<p>
is completely worthless, potentially introducing new errors.
</p>
</blockquote>
<p>
What's so great about this reflection formula that it has to hold for all integers n and k?
</p>
<p>
Here's another reason for (n choose k) to be 0 when n < 0 and k < 0: The coefficient in this case counts certain multisubsets of size k. There are none of them when k < 0.
</p>
<p>
I also don't buy the hypergeometric-functions argument. Graham, Knuth and Patashnik, in Chapter 5 of CM, define binomial coefficients to be 0 when k < 0, and this chapter does a good deal of hypergeometric manipulations. Sure, feel free to introduce another convention, but don't change the defaults!
</p>
TicketmantepseSat, 29 Jul 2017 13:31:43 GMT
https://trac.sagemath.org/ticket/17123#comment:41
https://trac.sagemath.org/ticket/17123#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:39" title="Comment 39">pluschny</a>:
</p>
<blockquote class="citation">
<p>
"Can we assume that everybody agrees that for <code>x</code> not negative integral,
</p>
<blockquote>
<p>
<code>gamma(x+1)/(gamma(y+1)*gamma(x-y+1))</code> is a good definition of <code>binomial(x,y)</code>?"
</p>
</blockquote>
<p>
Pardon me? No, what is g(x,y) for x = 1, y = -1 with this 'definition'?
</p>
</blockquote>
<p>
Sorry, I was sloppy. I should have added <code>extended by continuity</code>.
</p>
TicketpluschnySat, 29 Jul 2017 13:35:15 GMT
https://trac.sagemath.org/ticket/17123#comment:42
https://trac.sagemath.org/ticket/17123#comment:42
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:40" title="Comment 40">darij</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:39" title="Comment 39">pluschny</a>:
</p>
<blockquote class="citation">
<p>
An extension which does not give the reflection formula for the binomial
</p>
<p>
<code> binomial(-k, -n) = (-1)^(n-k) binomial(n-1, k-1) </code>
</p>
<p>
is completely worthless, potentially introducing new errors.
</p>
</blockquote>
<p>
What's so great about this reflection formula that it has to hold for all integers n and k?
</p>
</blockquote>
<p>
What a question!
</p>
<p>
As a short answer I cite GKP, CM on what they write in the Stirling case:
</p>
<p>
"In fact, a surprisingly pretty pattern emerges: The two kinds
of Stirling numbers are related by an extremely simple law:
</p>
<p>
[n, k] = {-k, -n}, integers k, n.
</p>
<p>
We have a "duality", something like the relations between min and max,
between floor(x) and ceiling(x), between falling factorial and rising
factorial, between gcd and lcm."
</p>
<p>
If such a relation exists for the binomial numbers, no CAS should presume to conceal it.
</p>
TicketmantepseSat, 29 Jul 2017 13:38:20 GMT
https://trac.sagemath.org/ticket/17123#comment:43
https://trac.sagemath.org/ticket/17123#comment:43
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:39" title="Comment 39">pluschny</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:38" title="Comment 38">mantepse</a>:
</p>
<blockquote>
<p>
"..your definition (by the way: is it yours? otherwise,
do you have a reference?).."
</p>
</blockquote>
<p>
I do not claim any originality whatsoever with this definition.
For references see what I have written on my blog linked above,
and the references given there.
</p>
</blockquote>
<p>
OK, I checked and found the definition in Section 3.2 of <a class="ext-link" href="https://arxiv.org/pdf/math/9502214.pdf"><span class="icon"></span>https://arxiv.org/pdf/math/9502214.pdf</a>. It would be nice to know who came up with this first.
</p>
TicketmantepseSat, 29 Jul 2017 13:44:04 GMT
https://trac.sagemath.org/ticket/17123#comment:44
https://trac.sagemath.org/ticket/17123#comment:44
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:39" title="Comment 39">pluschny</a>:
</p>
<blockquote class="citation">
<p>
Three years ago Volker Braun suggested above:
</p>
<p>
"We could also have an optional keyword argument binomial(n, k, extension='Knuth')."
</p>
</blockquote>
<p>
Yes, and I am saying that sage should have <code>binomial(n, k, extension=None)</code>, which should give the continuous version and raise an error for negative integral <code>n</code>, and then <code>binomial(n, k, extension='who_or_whatever')</code> for the various extensions.
</p>
<p>
(Assuming that all the extensions agree except for negative integral <code>n</code>.)
</p>
<p>
Is there any downside to this approach?
</p>
TicketpluschnySat, 29 Jul 2017 15:36:56 GMT
https://trac.sagemath.org/ticket/17123#comment:45
https://trac.sagemath.org/ticket/17123#comment:45
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:44" title="Comment 44">mantepse</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:39" title="Comment 39">pluschny</a>:
</p>
<blockquote class="citation">
<p>
Three years ago Volker Braun suggested above:
"We could also have an optional keyword argument binomial(n, k, extension='Knuth')."
</p>
</blockquote>
<p>
Yes, and I am saying that sage should have <code>binomial(n, k, extension=None)</code>, which should give the continuous version and raise an error for negative integral <code>n</code>, and then <code>binomial(n, k, extension='who_or_whatever')</code> for the various extensions. Is there any downside to this approach?
</p>
</blockquote>
<p>
This would effectively set the present state forever,
which I consider unsatisfactory.
</p>
<p>
Chapoton reopened this issue yesterday with the words:
"I have just been hurt by that issue."
</p>
<p>
And this issue will continue to hurt other users.
I have been hurt by that issue several times while
developing software for the OEIS. In the hypergeometric context
you 'feel' it, in many other cases it will bite unnoticed.
</p>
<p>
This is a bug and should be handled like a bug.
I therefore propose to follow Johan S. R. Nielsen suggestion on
<a class="ext-link" href="https://groups.google.com/forum/#!msg/sage-devel/elPsSq6uhvg/X65B7TuvAwAJ"><span class="icon"></span>sage-devel</a>:
</p>
<p>
I vote for having <a class="needs_info ticket" href="https://trac.sagemath.org/ticket/17123" title="enhancement: Extending binomial(n,k) to negative integers n, k. (needs_info)">#17123</a> as the default *in the long run*. If so, what
to do in the short run to mitigate user problems. We could
</p>
<p>
1) Return the value of <a class="needs_info ticket" href="https://trac.sagemath.org/ticket/17123" title="enhancement: Extending binomial(n,k) to negative integers n, k. (needs_info)">#17123</a> but print a deprecation warning on input
</p>
<blockquote>
<p>
with conflicting behaviour. The warning tells the user to explicitly
set the optional argument if he wants to disable the warning. Warning
is removed in ~1 year.
</p>
</blockquote>
<p>
2) Return the current value, but print a deprecation warning on input
</p>
<blockquote>
<p>
with conflicting behaviour. After one year, change the behaviour with
no more deprecation warnings.
</p>
</blockquote>
TicketmantepseSat, 29 Jul 2017 17:35:41 GMT
https://trac.sagemath.org/ticket/17123#comment:46
https://trac.sagemath.org/ticket/17123#comment:46
<blockquote class="citation">
<blockquote class="citation">
<p>
Yes, and I am saying that sage should have <code>binomial(n, k, extension=None)</code>, which should give the continuous version and raise an error for negative integral <code>n</code>, and then <code>binomial(n, k, extension='who_or_whatever')</code> for the various extensions. Is there any downside to this approach?
</p>
</blockquote>
<p>
This would effectively set the present state forever,
</p>
</blockquote>
<p>
This is not true:
</p>
<p>
<strong>currently <code>binomial(-1,-1)</code> gives <code>0</code>, while I propose that it raises an exception (possibly after a deprecation period), forcing you to use an explicit extension.</strong>
</p>
<p>
You and Frederic might use <code>binomial(-1, -1, extension='supertrooper')</code> whereas Darij might use <code>binomial(-1,-1, extension='themanwhosoldtheworld')</code>, but in any code you write, the extension chosen would be explicit!
</p>
<blockquote class="citation">
<p>
Chapoton reopened this issue yesterday with the words:
"I have just been hurt by that issue."
</p>
</blockquote>
<p>
Yes, because sage currently silently returns <code>0</code>, which is not what he expected.
</p>
<blockquote class="citation">
<p>
And this issue will continue to hurt other users.
</p>
</blockquote>
<p>
No, please read me proposal again.
</p>
<p>
Again, what is the downside to my approach?
</p>
<p>
Martin
</p>
TicketdarijSat, 29 Jul 2017 17:59:10 GMT
https://trac.sagemath.org/ticket/17123#comment:47
https://trac.sagemath.org/ticket/17123#comment:47
<p>
These look like good options, as long as:
</p>
<p>
1) the new default agrees with the old default on all values where both are defined (i.e., don't raise an error);
</p>
<p>
2) the new default includes (n choose k) = n (n-1) ... (n-k+1) / k! for k >= 0 (so the only disagreements are about what happens when k < 0) (e.g., this means that the Roman convention cannot be the default);
</p>
<p>
3) the case branching and string passing coming from the various conventions does not significantly slow down the function, OR each of the different conventions can be accessed through its own function without passing a string. (I'm not saying these functions need to be in the global namespace; it's enough if code can access them.)
</p>
<p>
BTW, the paper "A generalization of the binomial coefficients" by Loeb ( <a class="ext-link" href="http://www.sciencedirect.com/science/article/pii/0012365X92901386"><span class="icon"></span>http://www.sciencedirect.com/science/article/pii/0012365X92901386</a> and <a class="ext-link" href="https://arxiv.org/abs/math/9502218"><span class="icon"></span>https://arxiv.org/abs/math/9502218</a> ) seems to give a good overview of the different conventions (but the zero convention from Concrete Mathematics is not among them -- so there are four now: "zero", "Roman", "classical" and "Gamma"). I am still fairly convinced that the "zero" convention is the one that makes combinatorics the least painful, and that symmetry formulae are less important than the recursion.
</p>
TicketmantepseSat, 29 Jul 2017 18:46:45 GMT
https://trac.sagemath.org/ticket/17123#comment:48
https://trac.sagemath.org/ticket/17123#comment:48
<p>
I think it is calling for trouble not to raise an error for negative integral first argument. As much as I dislike python, I think "explicit is better than implicit" is a sensible rule.
</p>
<p>
If some functionality relies on <code>binomial(-1,-1)=1</code>, it will be much easier to maintain it if this stated explicitely, for example:
</p>
<pre class="wiki">def fun():
binomial = lambda x,y: binomial(x, y, extension='Gamma')
return binomial(-1,-1)
</pre>
TicketpluschnySat, 29 Jul 2017 19:02:45 GMT
https://trac.sagemath.org/ticket/17123#comment:49
https://trac.sagemath.org/ticket/17123#comment:49
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:47" title="Comment 47">darij</a>:
I am still fairly convinced that the "zero" convention is the one that makes combinatorics the least painful ...
</p>
<p>
pluschny wrote:
"I have been hurt by that issue several times while developing software for the OEIS.
In the hypergeometric context you 'feel' it, in many other cases it will bite unnoticed."
</p>
<p>
I will give an example for the latter. Consider:
</p>
<pre class="wiki">PartitionCoefficient = lambda p: mul(binomial(p[j], p[j+1]) for j in range(len(p)-1))
for n in (0..6):
for k in (0..n):
P = Partitions(n, max_part=k, inner=[k])
print sum(PartitionCoefficient(p) for p in P), binomial(n-1,k-1)
</pre><p>
What this code shows is for me inconsistency.
</p>
<p>
darij, you coined the famous sentence in this thread: "Having binomial(z, z) != 1
is collateral damage..." of your favourite definition.
</p>
<p>
This includes the damage of inconsistency?
</p>
TicketdarijSat, 29 Jul 2017 19:17:43 GMT
https://trac.sagemath.org/ticket/17123#comment:50
https://trac.sagemath.org/ticket/17123#comment:50
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:49" title="Comment 49">pluschny</a>:
</p>
<blockquote class="citation">
<p>
pluschny wrote:
"I have been hurt by that issue several times while developing software for the OEIS.
In the hypergeometric context you 'feel' it, in many other cases it will bite unnoticed."
</p>
<p>
I will give an example for the latter. Consider:
</p>
<pre class="wiki">PartitionCoefficient = lambda p: mul(binomial(p[j], p[j+1]) for j in range(len(p)-1))
for n in (0..6):
for k in (0..n):
P = Partitions(n, max_part=k, inner=[k])
print sum(PartitionCoefficient(p) for p in P), binomial(n-1,k-1)
</pre></blockquote>
<p>
You should be comparing with <code>binomial(n-1, n-k)</code>. These are really partitions of n-k you are summing over (the first part is just for convenience, as you clamp it to k).
</p>
<p>
Sorry, but it makes no sense on earth, in heaven and in other places to diverge from the (n choose k) = n(n-1)...(n-k+1)/k! standard for negative n as long as k >= 0. The binomial coefficients (n choose k) for a fixed k are a polynomial in n when n is nonnegative; why on earth would you want to break that?
</p>
TicketmantepseSat, 29 Jul 2017 19:29:27 GMT
https://trac.sagemath.org/ticket/17123#comment:51
https://trac.sagemath.org/ticket/17123#comment:51
<p>
Darij, are you sure that Peter proposal changes the default for <code>k>=0</code>?
</p>
TicketdarijSat, 29 Jul 2017 19:30:27 GMT
https://trac.sagemath.org/ticket/17123#comment:52
https://trac.sagemath.org/ticket/17123#comment:52
<p>
Oops, maybe not!
</p>
<p>
Sorry, this thread is a mess (and I'm part of it). Can anyone update me on whether the k >= 0 case is settled?
</p>
TicketmantepseSat, 29 Jul 2017 19:47:25 GMT
https://trac.sagemath.org/ticket/17123#comment:53
https://trac.sagemath.org/ticket/17123#comment:53
<p>
As far as I can see, Peter is proposing the "Gamma" convention from <a class="ext-link" href="https://arxiv.org/pdf/math/9502218.pdf"><span class="icon"></span>https://arxiv.org/pdf/math/9502218.pdf</a>. I think that this agrees with what is roughly the "classical" convention in the paper whenever the latter is defined, that is <code>limit(gamma(x+1)/(gamma(y+1)*gamma(x-y+1)), (x,y)=(n,k))</code> whenever the limit exists.
</p>
<p>
So they agree in particular for <code>k>=0</code>.
</p>
<p>
However, I still think it would be better to force users to make an explicit choice for negative integral <code>n</code>.
</p>
TicketmantepseSun, 30 Jul 2017 19:39:34 GMT
https://trac.sagemath.org/ticket/17123#comment:54
https://trac.sagemath.org/ticket/17123#comment:54
<p>
I'm afraid that I also added to the confusion, please let me correct my mistake.
</p>
<blockquote>
<p>
The truth is, <code>limit(gamma(x+1)/(gamma(y+1)*gamma(x-y+1)), (x,y)=(n,k))</code> does <strong>not</strong> exist for negative integral <code>n</code>, even if <code>k</code> is positive integral. Which means, that by default <code>binomial(-2, 41)</code> would be undefined instead of <code>-42</code>.
</p>
</blockquote>
TicketpluschnyTue, 01 Aug 2017 21:22:38 GMT
https://trac.sagemath.org/ticket/17123#comment:55
https://trac.sagemath.org/ticket/17123#comment:55
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:43" title="Comment 43">mantepse</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:39" title="Comment 39">pluschny</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:38" title="Comment 38">mantepse</a>:
</p>
<blockquote>
<p>
"..your definition (by the way: is it yours? otherwise,
do you have a reference?).."
</p>
</blockquote>
<p>
I do not claim any originality whatsoever with this definition.
For references see what I have written on my blog linked above,
and the references given there.
</p>
</blockquote>
<p>
OK, I checked and found the definition in Section 3.2 of <a class="ext-link" href="https://arxiv.org/pdf/math/9502214.pdf"><span class="icon"></span>https://arxiv.org/pdf/math/9502214.pdf</a>. It would be nice to know who came up with this first.
</p>
</blockquote>
<p>
Meanwhile I have found a reference for the reflexion formula:
Martin Aigner, Kombinatorik I, Springer 1975, exercise on page 149.
This book became part of his Combinatorial Theory, Grundlehren 234.
</p>
<p>
Since I learned from this book, it seemed always to me to be
self-evident and I do not understand to this day why one should
be reluctant to use it (or implement an extension which assures it).
</p>
TicketmantepseWed, 02 Aug 2017 10:01:21 GMT
https://trac.sagemath.org/ticket/17123#comment:56
https://trac.sagemath.org/ticket/17123#comment:56
<p>
let me please try to summarize:
</p>
<ol><li>all agree that it would be good to have the "gamma" convention from <a class="ext-link" href="https://arxiv.org/pdf/math/9502218.pdf"><span class="icon"></span>https://arxiv.org/pdf/math/9502218.pdf</a> accessible
</li></ol><ol start="2"><li>also the "zero" convention (I think that's equivalent to the iterated limit expression) should be accessible, and perhaps also other conventions
</li></ol><ol start="3"><li>some formulas involving binomial coefficients depend on the chosen convention, and different CAS make different choices
</li></ol><ol start="4"><li>we also need <code>binomial</code> for non-integral arguments
</li></ol><ol start="5"><li>a continuous definition is desirable, for example for analytic stuff, but <code>limit(gamma(x+1)/(gamma(y+1)*gamma(x-y+1)), (x,y)=(n,k))</code> only exists when <code>n</code> is not a negative integer, which is very restrictive
</li></ol><p>
possible solutions:
</p>
<ol class="loweralpha"><li>make some convention (very likely "gamma" - <code>limit(gamma(n+h)/(gamma(k+h)*gamma(n-k+h)), h=1)</code>) the default and make other conventions accessible
<ul><li>advantages: most users won't notice
</li><li>disadvantages: convention-mismatch will go unnoticed
</li></ul></li></ol><ol class="loweralpha" start="2"><li><code>binomial(n, k)</code> raises an error for negative integral <code>n</code> (even when <code>k</code> is a non-negative integer), and in this situation the convention must be chosen explicitly
<ul><li>advantages: convention-mismatch will go unnoticed
</li><li>disadvantages: slightly harder to use and routines calling binomial will probably need adjustment in some places, although these should be easy to find
</li></ul></li></ol>
TicketpluschnyWed, 02 Aug 2017 12:39:31 GMT
https://trac.sagemath.org/ticket/17123#comment:57
https://trac.sagemath.org/ticket/17123#comment:57
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:56" title="Comment 56">mantepse</a>:
</p>
<blockquote class="citation">
<p>
let me please try to summarize:
</p>
</blockquote>
<p>
I think there should be exactly two functions:
</p>
<ul><li>one defined on N X N where N = {0,1,2,..},
</li><li>the other defined on C where C are the complex numbers.
</li></ul><p>
This mirrors the case factorial / Gamma.
</p>
<p>
The first defined on N X N is the classical Pascal function
which is zero for all (n,k) which are not 0<=k<=n.
</p>
<p>
I leave open how the second is precisely defined, but it
should reduce on the ZZ-grid to the values described by the
Binomial function given above. This means in particular that
on the ZZ-grid the reflection formula is valid, all values
finite and Binomial(x, x) = 1 for all x.
</p>
<p>
For the naming: the first one could be called binomial(n,k)
and the second Binomial(x,y).
</p>
<p>
This means in particular that the existing Sage binomial function
needs not to be touched. No disadvantages, no deprecations.
</p>
TicketmantepseWed, 02 Aug 2017 13:02:20 GMT
https://trac.sagemath.org/ticket/17123#comment:58
https://trac.sagemath.org/ticket/17123#comment:58
<p>
Could you please comment on the advantages and disadvantages I listed.
</p>
<p>
Moreover, what is the disadvantage of <code>binomial(n,k,extension="Gamma")</code> over <code>Binomial(n,k)</code>?
</p>
<p>
Finally, how would you accommodate Darij's needs with your proposal?
</p>
TicketpluschnyWed, 02 Aug 2017 15:51:15 GMT
https://trac.sagemath.org/ticket/17123#comment:59
https://trac.sagemath.org/ticket/17123#comment:59
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:58" title="Comment 58">mantepse</a>:
</p>
<blockquote class="citation">
<p>
Finally, how would you accommodate Darij's needs with your proposal?
</p>
</blockquote>
<p>
Your question amazes me. Darij wrote: "Please do not change the current
version." Done. "Feel free to add binomial_symmetrized or whatever else
you want to call your function, however!" Fine.
So I think this will be OK with him. But he can take position himself, no?
</p>
<blockquote class="citation">
<p>
Could you please comment on the advantages and disadvantages I listed.
</p>
</blockquote>
<p>
I concur with what you say.
</p>
<blockquote class="citation">
<p>
Moreover, what is the disadvantage of <code>binomial(n,k,extension="Gamma")</code> over <code>Binomial(n,k)</code>?
</p>
</blockquote>
<p>
No big difference for me. I think it is the analogy with factorial/Gamma
which I like. Of course we could also drop the Gamma function and introduce
<code>factorial(n,extension="Gamma")</code>. Matter of taste.
</p>
TicketmantepseWed, 02 Aug 2017 15:58:01 GMT
https://trac.sagemath.org/ticket/17123#comment:60
https://trac.sagemath.org/ticket/17123#comment:60
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:59" title="Comment 59">pluschny</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:58" title="Comment 58">mantepse</a>:
</p>
<blockquote class="citation">
<p>
Finally, how would you accommodate Darij's needs with your proposal?
</p>
</blockquote>
<p>
Your question amazes me. Darij wrote: "Please do not change the current
version." Done. "Feel free to add binomial_symmetrized or whatever else
you want to call your function, however!" Fine.
So I think this will be OK with him. But he can take position himself, no?
</p>
</blockquote>
<p>
The current binomial is not defined on N x N, but on a larger domain. Above you proposed at the same time to leave it untouched and to define it on N x N, which confused me.
</p>
TicketpluschnyWed, 02 Aug 2017 16:28:24 GMT
https://trac.sagemath.org/ticket/17123#comment:61
https://trac.sagemath.org/ticket/17123#comment:61
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:60" title="Comment 60">mantepse</a>:
</p>
<blockquote class="citation">
<p>
The current binomial is not defined on N x N, but on a larger domain. Above you proposed at the same time to leave it untouched and to define it on N x N, which confused me.
</p>
</blockquote>
<p>
I see, that was not well expressed. In fact, I am now a little tired of this subject and have nothing else to say. May the issue get a good implementer. Bye.
</p>
TicketpluschnySat, 05 Aug 2017 19:30:37 GMT
https://trac.sagemath.org/ticket/17123#comment:62
https://trac.sagemath.org/ticket/17123#comment:62
<p>
I have just read an unpublished manuscript, which is the most detailed
and comprehensive analysis of the subject so far. It convinced me that
the approach defended by me is not adequate. I withdraw my request and
ask to close the subject.
</p>
TicketdarijSat, 05 Aug 2017 19:47:22 GMT
https://trac.sagemath.org/ticket/17123#comment:63
https://trac.sagemath.org/ticket/17123#comment:63
<p>
If any of you is interested in a fast review (at least from me), I suggest to implement whatever definitions you like as separate functions:
</p>
<p>
<code>def binomial_roman...</code>
</p>
<p>
<code>def binomial_gamma...</code>
</p>
<p>
etc. (without changing the existing <code>binomial</code> function), document their definitions in full and link them to each other via <code>.. SEEALSO:</code>. This way I'll be able to just review the maths without plunging into a debate I really don't want to take part in (nor do I have the time to).
</p>
TicketmantepseSun, 06 Aug 2017 07:55:04 GMT
https://trac.sagemath.org/ticket/17123#comment:64
https://trac.sagemath.org/ticket/17123#comment:64
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:62" title="Comment 62">pluschny</a>:
</p>
<blockquote class="citation">
<p>
I have just read an unpublished manuscript, which is the most detailed
and comprehensive analysis of the subject so far. It convinced me that
the approach defended by me is not adequate. I withdraw my request and
ask to close the subject.
</p>
</blockquote>
<p>
Could you share this, or maybe just the address of the author?
</p>
<p>
I am actually digging into the code and the details of the conventions,
to see how it goes.
</p>
TicketpluschnySun, 06 Aug 2017 09:42:23 GMT
https://trac.sagemath.org/ticket/17123#comment:65
https://trac.sagemath.org/ticket/17123#comment:65
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:64" title="Comment 64">mantepse</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17123#comment:62" title="Comment 62">pluschny</a>:
</p>
<blockquote class="citation">
<p>
I have just read an unpublished manuscript,
</p>
</blockquote>
<p>
Could you share this, or maybe just the address of the author?
</p>
</blockquote>
<p>
Several people urged the author to publish the paper.
But it is, of course, at the discretion of the author.
Nevertheless, it may one day appear in the
arXiv and you will recognize it by the excellent plots.
</p>
<p>
In his opinion, no path leads past the arguments of GKP in CM,
with the effect that all integer values on the left half-plane
have to be 0. In particular GKP writes:
</p>
<p>
"The symmetry identity fails for all other negative integers n, too. But
unfortunately it's all too easy to forget this restriction, since the
expression in the upper index is sometimes negative only for obscure
(but legal) values."
</p>
<p>
Meanwhile I read yet another paper which is much more critical about
the presentation of GKP:
</p>
<p>
David Fowler, The Binomial Coefficient Function,
The American Mathematical Monthly, Vol. 103, No. 1 (Jan., 1996), pp. 1-17
</p>
<p>
Fowler also makes the following interesting suggestion:
</p>
<p>
"One could generalise the standard binomial coefficients
to include an extra argument, the slope at which the directional
limit is to be taken, and thus extend such standard identities
to negative arguments and perhaps find new ones."
</p>
Ticket