Extending binomial(n,k) to negative integers n, k.

[PeterLuschny]

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, http://arxiv.org/abs/1105.3689 (Thanks to John Palmieri for the reference.)

This extension amounts to define

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)

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.

CC: @rwst

Component: combinatorics

Keywords: binomial

Branch/Commit: u/chapoton/17123 @ 0c99437

Issue created by migration from https://trac.sagemath.org/ticket/17123

[darijgr]

comment:50

Replying to @PeterLuschny:

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."

I will give an example for the latter. Consider:

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) 

You should be comparing with binomial(n-1, n-k). These are really partitions of n-k you are summing over (the first part is just for convenience, as you clamp it to k).

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?

[mantepse]

comment:51

Darij, are you sure that Peter proposal changes the default for k>=0?

[darijgr]

comment:52

Oops, maybe not!

Sorry, this thread is a mess (and I'm part of it). Can anyone update me on whether the k >= 0 case is settled?

[mantepse]

comment:53

As far as I can see, Peter is proposing the "Gamma" convention from https://arxiv.org/pdf/math/9502218.pdf. I think that this agrees with what is roughly the "classical" convention in the paper whenever the latter is defined, that is limit(gamma(x+1)/(gamma(y+1)*gamma(x-y+1)), (x,y)=(n,k)) whenever the limit exists.

So they agree in particular for k>=0.

However, I still think it would be better to force users to make an explicit choice for negative integral n.

[mantepse]

comment:54

I'm afraid that I also added to the confusion, please let me correct my mistake. The truth is, limit(gamma(x+1)/(gamma(y+1)*gamma(x-y+1)), (x,y)=(n,k)) does not exist for negative integral n, even if k is positive integral. Which means, that by default binomial(-2, 41) would be undefined instead of -42.

[PeterLuschny]

comment:55

Replying to @mantepse:

Replying to @PeterLuschny:

Replying to @mantepse:

"..your definition (by the way: is it yours? otherwise, do you have a reference?).."

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.

OK, I checked and found the definition in Section 3.2 of https://arxiv.org/pdf/math/9502214.pdf. It would be nice to know who came up with this first.

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.

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).

[mantepse]

comment:56

let me please try to summarize:

1. all agree that it would be good to have the "gamma" convention from https://arxiv.org/pdf/math/9502218.pdf accessible

2. also the "zero" convention (I think that's equivalent to the iterated limit expression) should be accessible, and perhaps also other conventions

3. some formulas involving binomial coefficients depend on the chosen convention, and different CAS make different choices

4. we also need binomial for non-integral arguments

5. a continuous definition is desirable, for example for analytic stuff, but limit(gamma(x+1)/(gamma(y+1)*gamma(x-y+1)), (x,y)=(n,k)) only exists when n is not a negative integer, which is very restrictive

possible solutions:

a. make some convention (very likely "gamma" - limit(gamma(n+h)/(gamma(k+h)*gamma(n-k+h)), h=1)) the default and make other conventions accessible

• advantages: most users won't notice
• disadvantages: convention-mismatch will go unnoticed

b. binomial(n, k) raises an error for negative integral n (even when k is a non-negative integer), and in this situation the convention must be chosen explicitly

• advantages: convention-mismatch will go unnoticed
• disadvantages: slightly harder to use and routines calling binomial will probably need adjustment in some places, although these should be easy to find

[PeterLuschny]

comment:57

Replying to @mantepse:

let me please try to summarize:

I think there should be exactly two functions:

• one defined on N X N where N = {0,1,2,..},
• the other defined on C where C are the complex numbers.

This mirrors the case factorial / Gamma.

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.

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.

For the naming: the first one could be called binomial(n,k) and the second Binomial(x,y).

This means in particular that the existing Sage binomial function needs not to be touched. No disadvantages, no deprecations.

[mantepse]

comment:58

Could you please comment on the advantages and disadvantages I listed.

Moreover, what is the disadvantage of binomial(n,k,extension="Gamma") over Binomial(n,k)?

Finally, how would you accommodate Darij's needs with your proposal?

[PeterLuschny]

comment:59

Replying to @mantepse:

Finally, how would you accommodate Darij's needs with your proposal?

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?

Could you please comment on the advantages and disadvantages I listed.

I concur with what you say.

Moreover, what is the disadvantage of binomial(n,k,extension="Gamma") over Binomial(n,k)?

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 factorial(n,extension="Gamma"). Matter of taste.

[mantepse]

comment:60

Replying to @PeterLuschny:

Replying to @mantepse:

Finally, how would you accommodate Darij's needs with your proposal?

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?

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.

[PeterLuschny]

comment:61

Replying to @mantepse:

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.

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.

[PeterLuschny]

comment:62

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.

[darijgr]

comment:63

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:

def binomial_roman...

def binomial_gamma...

etc. (without changing the existing binomial function), document their definitions in full and link them to each other via .. SEEALSO:. 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).

[mantepse]

comment:64

Replying to @PeterLuschny:

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.

Could you share this, or maybe just the address of the author?

I am actually digging into the code and the details of the conventions, to see how it goes.

[PeterLuschny]

comment:65

Replying to @mantepse:

Replying to @PeterLuschny:

I have just read an unpublished manuscript,

Could you share this, or maybe just the address of the author?

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.

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:

"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."

Meanwhile I read yet another paper which is much more critical about the presentation of GKP:

David Fowler, The Binomial Coefficient Function, The American Mathematical Monthly, Vol. 103, No. 1 (Jan., 1996), pp. 1-17

Fowler also makes the following interesting suggestion:

"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."