Multinomial coefficients

[sylee957]

I think that multinomial coefficient can be added
It won't be difficult, but the conflicting notations between mathematica and maple is making it confusing.

Some people prefer to use

• 

while some other people prefer to use

• 

assuming that n is loosely the summation of each k.

So it should be chosen that which kind if definition is the best
And if the second one is chosen, I think that I should rather make it like
mechanically, so it won't really be much convenient than choosing the first one. But this can be consistent with the definition of binomial.

Some references:

• https://en.wikipedia.org/wiki/Multinomial_theorem
• https://dlmf.nist.gov/26.4
• http://functions.wolfram.com/GammaBetaErf/Multinomial/
• https://www.maplesoft.com/support/help/Maple/view.aspx?path=combinat%2Fmultinomial
• https://reference.wolfram.com/language/ref/Multinomial.html

[Arpan612]

Sir, I would like to work on this issue. I will be sending a PR soon.

[sylee957]

Yes, but I'd expect it to be presented as a class multinomial(Function): rather than loose function. I think that there are already lots of same stuff implemented for computing mutinomial only for integers, but only not as a symbolic function

[Arpan612]

Sure sir.

[Arpan612]

Except for integers, where all should multinomial be applicable?

[sylee957]

In the wolfram function repository, I see they are using a generalized definition using gamma functions. So it can be defined all over the complexes and differentiable.

And I already see that factorial or binomial in sympy are using the definition from gamma, so the definition from wolfram can be used.

[Arpan612]

http://functions.wolfram.com/GammaBetaErf/Multinomial/02/
Sir, do you mean this one?

[sylee957]

Yes

[iammosespaulr]

@sylee957 would it be preferred to write the Multinomial from scratch or just implement it as a product of binomials ?

[sylee957]

@sylee957 would it be preferred to write the Multinomial from scratch or just implement it as a product of binomials ?

In my opinion, I'd just implement it from scratch because expanding a multinomial into a product of binomials may not have a unique representation.
But the computation can be done internally by dispatching them to binomials.

[czgdp1807]

Please try to avoid off topic discussions. Some comments here were not relevant to the issue and hence are marked hidden. Even this comment is not going to solve the issue in any way but it has to be made to clarify things.

[iammosespaulr]

@sylee957 what about printing multinomials ... like print_binomial in latex.py and mathml.py ?
those are needed too right ?

[czgdp1807]

Some people prefer to use

• 

I think this is better than other options as it isn't redundant, won't require, n = Sum(k1, k2, k3, k4, ..., kn).

[czgdp1807]

And binomial coefficients are multinomial coefficients. So, if they both are represented by classes then former should inherit the later.

[iammosespaulr]

And binomial coefficients are multinomial coefficients. So, if they both are represented by classes then former should inherit the later.

That's what I asked @sylee957 ... but he was talking about writing one from scratch ...

In my opinion, I'd just implement it from scratch because expanding a multinomial into a product of binomials may not have a unique representation.
But the computation can be done internally by dispatching them to binomials.

[iammosespaulr]

Okey 👍

[czgdp1807]

Though I am not sure which design scheme should be followed. I think that, having general classes subclassed in specialised classes help in getting things done with little code. Like, a truck is a vehicle so we should go for vehicle being subclassed in truck. Though if there is any other compelling reason to do the reverse then that should be presented here.

[sylee957]

When inheriting the class, the args structure must be coherent or other issues can arise.

I agree that multinomial without n looks better. However, it can make more difficult to keep the consistent structure with classes, so they should not inherit each other.

But I’d rather have other ideas like Binomial automatically evaluate to multinomial and keep binomial a stub class for notational purpose, if it should be

[czgdp1807]

I see, binomial is already there. May be then API for binomial can be extended to multinomial as well so that the consistency is maintained. It would be better if they both are compatible with each other.
P.S. In addition, I suggest to update the PR policy and add an issue policy(if it isn't already there) to SymPy wiki. It would help in making things clear. I would like to discuss this on Google groups.

[Arpan612]

So can we use the binomial class then?

[czgdp1807]

Can you please elaborate more on your question?

[Arpan612]

Could we implement the multinomial coefficient as a function or it is necessary to construct a separate class for it?

[czgdp1807]

I think that the APIs for binomial and multinomial should be similar with inter operability.

[Arpan612]

Sure sir.

[sylee957]

The only thing I'm concerned of making multinomial similar to binomial is that we will eventually see
and having to derive all the formula about it

[czgdp1807]

The only thing I'm concerned of making multinomial similar to binomial is that we will eventually see
and having to derive all the formula about it

IMHO, this isn't a really good representation. It is redundant, self-correcting i.e., if k1, k2, k3, k4, ...kn sum less than n then the last term in the denominator will correct that mistake. So, I think, what we can do to ensure inter operability between the two is if we want to represent binomial(n, k) in terms of multinomial by multinomial(k, n-k). Actually nCk is very popular as binomial(in fact I am not aware of better notations to represent binomial), however, as you have suggested multinomial has multiple representation and making it similar to binomial will lead to non-intuitive API.

[czgdp1807]

I think that the APIs for binomial and multinomial should be similar with inter operability.

Just for clarification, by similarity I mean that functions provided by multinomial and binomial should be same. Making them exactly same would not be possible due to the reasons mentioned above. Please don't this point wrongly. Inter operation is what matters more IMO.

[oscarbenjamin]

When inheriting the class, the args structure must be coherent or other issues can arise.

I think it is okay for subclasses to have different args. The important thing is that code should access properties rather than accessing the args directly. Then a subclass that changes the args structure just needs to override the properties that access the args.

[Arpan612]

@czgdp1807 @oscarbenjamin Could you please go through my PR?

[iammosespaulr]

>>> from sympy import *
>>> for i in range(10,15):
...     for j in range(10,15):
...             print(binomial(j,i), multinomial((i,j-i)))
... 
1 1
11 11
66 66
286 286
1001 1001
0 0
1 1
12 12
78 78
364 364
0 0
0 0
1 1
13 13
91 91
0 0
0 0
0 0
1 1
14 14
0 0
0 0
0 0
0 0
1 1
>>> multinomial(symbols('a b c'))
gamma(a + b + c + 1)/(gamma(a + 1)*gamma(b + 1)*gamma(c + 1))
>>> 

I've been working on this ... is this close to what you were expecting @sylee957 @czgdp1807 @oscarbenjamin

[czgdp1807]

IMO, it looks fine to me. Can you please make a PR to show whatever you have written for multinomial. I am not sure if multiple PRs are allowed but it is fine to make one, the better one can be kept.

[czgdp1807]

IMO, it looks fine. Can you please make a PR to show whatever you have written for multinomial. I am not sure if multiple PRs are allowed but it is fine to make one, the better one can be kept.
@iammosespaulr

[iammosespaulr]

I'll submit a pr ... in 6-7 hrs or so. I'm soo sleepy , btw I am yet to add support for expanding the expression and for .eval , the rest are almost done @czgdp1807

[sylee957]

The framework I'd begin with is

from sympy import *
from sympy.core.sympify import _sympify
from sympy.functions.combinatorial.factorials import CombinatorialFunction

class multinomial(CombinatorialFunction):
    @classmethod
    def eval(cls, *k):
        k = [_sympify(x) for x in k]
        n = Add(*k)
        if all(x.is_Integer for x in k):
            n = Add(*k)
            numer = factorial(n)
            denom = Mul(*(factorial(x) for x in k))
            return numer/denom
        
    def _eval_rewrite_as_factorial(self, *args, **kwargs):
        n = Add(*args)
        numer = factorial(n)
        denom = Mul(*(factorial(x) for x in args))
        return numer/denom
    
    def _eval_rewrite_as_binomial(self, *args, **kwargs):
        pass
    
    def _eval_rewrite_as_gamma(self, *args, **kwargs):
        pass

Actually, when following the sympy Function framework, I don't think that it's easy to access parameters via properties because it uses classmethod to evaluate. And other things like sorting the k is not easy with this framework.

[iammosespaulr]

@sylee957 I wrote something similar to that ... but It was just using gamma

[sylee957]

For integers only, it’s better to use factorials

[iammosespaulr]

Yes!

[iammosespaulr]

@sylee957 @czgdp1807 I've drafted a PR ... lmk what you think.

[sylee957]

From the wolfram's source, mutinomial is undefined when n is negative integer (Because the gamma and factorial gets division of infinity by infinity) So when this is encountered, it should raise an error.

[iammosespaulr]

Yeahh. I've removed test cases where n is negative. I'll add a check too.

[Arpan612]

@sylee957 Okay sir.

[Arpan612]

@sylee957 @czgdp1807 Sir, I believe my version of the PR is slightly better. Also, I have squashed the commits for easy readability. Due to the squash, checks are been performed all over again. I request you to wait for some time.

[Arpan612]

@sylee957 @czgdp1807 Please review and merge PR #18952

[smichr]

#18906 had code to calculate a given multinomial coefficient but it is stalled. It would be nice to have the ability to calculate a concrete coefficient. The following is an efficient version that could be used:

def multinomial_coefficient(*e):
    """Return the multinomial coefficient (e1 + e2 + ...)! / e1! / e2! / ..."""
    # https://stackoverflow.com/a/56856279/1089161
    if not e:  # no parameters
        return 1
    ibig = e.index(max(e))
    num = e[ibig] + 1
    rv = 1
    for n in e[:ibig] + e[ibig + 1:]:
        for den in range(1, n + 1):
            rv *= num // den
            num += 1
    return rv

Note that currently one can calculate all coefficients with multinomial_coefficients but if you only want a few (or one) then something like the above would be useful.