Karim Belabas on Sat, 29 Oct 2022 18:29:35 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: binomial coefficient with negative args |
* Max Alekseyev [2022-10-28 21:33]: > The extension surely has its ground, but the problem is that it contradicts > the conventional use of binomial coefficients in combinatorics. Having > binomial(n,k) = 0 for k < 0 allows one to not care much about range for the > lower index and consider sums where some terms are zero just because k goes > out of range (which is quite convenient). And as Bill said, enabling the > possibility binomial(n,k) to be nonzero for k < 0 may break many existing > scripts (mine included). Hi, here's the situation as I see it: - the previous behaviour was consistent although arbitrary and undocumented: binomial(n, k < 0) := 0 else binomial(n, k) = gamma(n+1) / gamma(k+1) / gamma(n-k+1) whenever it made sense (as an integer if possible, else a float, else ...). For some reason (unknown to me; probably lack of usecase) this was not actually implemented unless k was an integer. - the new behaviour makes the second branch continuous, involving a limit binomial(n, k) = lim_{t->1} gamma(n+t) / gamma(k+t) / gamma(n-k+t) whenever it makes sense. This is still only implemented for integer k, although it would be easy to extend it. - there is no generally accepted convention for "extensions" of binomials (the fact that both Mathematica and Maple chose the same one, aka 'new behaviour' above, is only an indication) Depending on applications, either can be "right", both are certainly incompatible when n and k are both negative integers: this is a backward incompatible change. Finally, both can easily be implemented in GP in terms of the classical definition (0 <= k <= n); the new behaviour being harder to implement. The new definition can be traced back to Daniel Loeb (Sets with a negative number of elements. Adv. Math. 91 (1992), no. 1, 64–74.), who held a position in Bordeaux at the time. (He also studied Roman coefficients, using Steve Roman's factorial, and Knuth's generalization; our new definition is a limiting case of Knuth's.) So had we asked our local experts in combinatorics at the time the function was implemented, we might have chosen *that* extension. Finally some old scripts might fail when some new scripts adapted from Maple or Mathematica might "just happen work". See e.g., Peter Luschny's blog post advising against using Sagemath ('old behaviour') for OEIS work: http://oeis.org/wiki/User:Peter_Luschny/ExtensionsOfTheBinomial If this were Python ("Explicit is better than implicit"), I would propose binomial(x, k, extension="whatever"); (with an error if k < 0 !). This being GP, I'll just document the new behaviour, including a warning in "COMPAT" and let the user choose her favourite extension (and document it in her code). Cheers, K.B. > On Fri, Oct 28, 2022 at 2:34 PM Christian Krause <me@ckrause.org> wrote: > > > Some more info on the extension: it uses the gamma function as > > continuous version of factorial. The rest follows from the definition of > > the gamma function. Besides Wolfram Alpha, also the Maple Calculator app > > uses this definition: > > > > Wolfram Alpha: > > [image: Screenshot 2022-10-28 at 20.23.34.png] > > > > Maple Calculator: > > [image: image.png] > > > > Cheers, > > Christian > > > > On Fri, 28 Oct 2022 at 12:38, Bill Allombert < > > Bill.Allombert@math.u-bordeaux.fr> wrote: > > > >> On Wed, Oct 26, 2022 at 02:54:47PM -0400, Max Alekseyev wrote: > >> > I worry that this extension is not consistent with the definition of > >> > binomial(n,k) as the coefficient of x^k in (1+x)^n. > >> > According to this definition it should be zero for k < 0. > >> > >> To give an example where that makes a difference: > >> > >> ? sum(i=-5,5,binomial(-1,i)*x^i)==(1+x)^-1+O(x^6) > >> > >> pari 2.15: > >> %1 = 1 > >> pari 2.16: > >> %1 = 0 > >> > >> Cheers, > >> Bill > >> > >> K.B. -- Karim Belabas, IMB (UMR 5251), Université de Bordeaux Vice-président en charge du Numérique T: (+33) 05 40 00 29 77; http://www.math.u-bordeaux.fr/~kbelabas/ ` K.B. -- Karim Belabas, IMB (UMR 5251), Université de Bordeaux Vice-président en charge du Numérique T: (+33) 05 40 00 29 77; http://www.math.u-bordeaux.fr/~kbelabas/ `