CODEWITHSUNDEEP
pythonscipy
TristanMatthews
TristanMatthews

Reputation: 2571

Scipy calculate of multinomial coefficents

Short version: Title kind of says it all.

Log Version:

I'm calculating multinomial coefficents for the first few elements in. Looking at a wiki, the math is fairly simple. 

N! / (k1! * k2! * ....)

For mediums sized N the numbers get fairly silly quickly if you just brute force it. For example,

500!/ (495! * 4! * 1!)

has 500! in it, and math.log(factorial(500), 10) ~= 1134 when the expression reduces too:

500!/ (495! * 4! * 1!) = 500 * 499 * 498 * 497 * 496 / 24

I tried playing with scipy.misc.comb, which works great for binomial. For my use case k1 is much larger then ki (i != 1), so I could calculate the binomial coefficient and then convert that to the corresponding multinomial coefficient, but that seems a little round about.

I assume there is a much better way.

Upvotes: 3

Views: 876

Answers (1)

giles
giles

Reputation: 352

This is answered on the math stackexchange, and looks reasonable.

I think what the original answer is doing is just enumerating all the terms and cancelling, then computing the final result. So sort of 1-step removed from the brute force, but doesn't look like it overflows.

Maybe this is the same as computing the bionomial coefficients. Anyway there is also a logarithm algorithm cited there that I didn't comprehend at first glance.

https://math.stackexchange.com/questions/204085/how-do-i-compute-multinomials-efficiently

Upvotes: 2

Related Questions