Multinomial coefficient

Implement a function to compute the multinomial coefficient for given counts

combinatorics math division modular-arithmetic integer-arithmetic

Write a function `multinomial_coefficient(counts)` that takes a list of nonnegative integers `counts` and returns the multinomial coefficient: (sum(counts))! / (counts[0]! * counts[1]! * ... * counts[n-1]!).

For example, `multinomial_coefficient([2,1])` returns 3 because 3!/(2!*1!) = 3.

- The input list will contain at least one element.
- All elements are nonnegative integers.
- The total sum of elements will not exceed 1000.
- The result is guaranteed to be an integer and fits in Python's int (unbounded).

Constraints

Input constraints:
- `1 <= len(counts)` (list is non-empty)
- `0 <= counts[i] <= 1000` for each element
- `sum(counts) <= 1000`
- The result is always an integer and fits in Python's int.

Example

>>> multinomial_coefficient([2,1])
3
>>> multinomial_coefficient([1,1,1])
6
>>> multinomial_coefficient([0,5])
1
>>> multinomial_coefficient([5,2,3])
2520

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

The multinomial coefficient equals the product of binomial coefficients: C(n, k1) * C(n-k1, k2) * ...

You can compute it incrementally by factorials or by multiplying and dividing at each step.

To avoid large intermediate numbers, divide as you go using integer math.

Edge cases: zeros in counts, a single count, and all zeros.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.