Re: binomial coefficient with negative args

[Christian Krause <me@ckrause.org>]

Hello,

I noticed that binomial(-2,-4) still yields 0 in PARI/GP 2.15.4 although Kronenburg's extension was apparently added to src/basemath/bibli2.c. The documentation appears not to include the behavior for negative k. Was there a decision to keep the old behavior for backward compatibility or why do I still get 0 as result?

Best regards,

Christian

On Sat, 29 Oct 2022 at 18:28, Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:

* 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/
`