What is the math behind this Python program generating multinomial coefficients?

Question

I wrote a Python program that is using recursion to generate multinomial coefficients - see next section.

Mathematically it is also using recursion by 'decrementing down to the boundary'.

My motivation for coding this was reading the wiki paragraph

Generalized Pascal's triangle

One can use the multinomial theorem to generalize Pascal's triangle or Pascal's pyramid to Pascal's simplex. This provides a quick way to generate a lookup table for multinomial coefficients.

I am not sure what the math is behind the program or if this technique is known. But the 'slow decrementer program' would really 'crank out' on a quantum computer storing massive lookup tables in memory.

What mathematics is the Python program using?

I am going to post this on stack overflow as an answer to this question,

$\quad$ Does Python have a function which computes multinomial coefficients?

but will be able to explain it better after getting feedback from this site.

---

Python program

def da_multi(A):      # Multinomial
    if len(A) < 2:
        return 1
    n = sum(A)    
#                           # Remove the silly 1's
    for i in range(0, len(A)):
        if A[i] == 1:
            B = A.copy()
            del B[i]
            return n * da_multi(B)

#                           # OK, dealing with no 1's
    r = 0
    for i in range(0, len(A)):
        B = A.copy()
        B[i] = B[i] - 1
        r = r + da_multi(B)
    return r

A = [1,2,2,7,1] 
A_wrk =  A.copy()

print('multi:', A, da_multi(A_wrk))

The program calculates a multinomial and the answer agrees with the Wolfram calculation.

OUTPUT

multi: [1, 2, 2, 7, 1] 308880

Answer 1

I will preface by reminding that you asked for an explanation of the code as it is written currently, and are not asking for more efficient code or critiques in the code. I'm rather certain there is much more efficient code if you prefer to work with binomial coefficients rather than multinomial all the way down.

---

If it so happens that the number of elements is less than two, that implies that we are currently trying to calculate the binomial coefficient $\binom{n}{n}$ (recalling that $n$ here is the sum of the terms on the bottom, and with only one term on the bottom clearly they will match) which will always simplify to $1$. This explains the first if condition.

Recall that $$\binom{n}{a_1,a_2,a_3,\dots,a_k} = \binom{n}{a_1}\binom{n-a_1}{a_2,a_3,\dots,a_k}$$ To explain this identity, when counting the number of strings of length $n$ made up of $a_1$ characters of type $1$, $a_i$ characters of type $i$ in general, etc... we can first pick which spaces are occupied by the characters of type $1$ and then by ignoring those spaces treat the remaining spaces as a string of length $n-a_1$ made up of characters of type other than $1$ of the corresponding amounts as before.

Further you can permute the terms as you like, i.e. $$\binom{n}{a_1,a_2,a_3,\dots,a_k} = \binom{n}{a_{\pi(1)},a_{\pi(2)},a_{\pi(3)},\dots,a_{\pi(k)}}$$. After all, $\binom{n}{a_1,a_2,a_3,\dots,a_k} = \frac{n!}{a_1!a_2!a_3!\cdots a_k!}$ and multiplication is commutative. We can assume then without loss of generality that the values are in ascending order. We can also assume there are no $0$'s included (as seems to be the case for whoever coded that function, because otherwise the code breaks).

So... if it happens to be the case that there is a $1$ included in the values, i.e. that $a_1 = 1$, then we would have from the above identity that $$\binom{n}{1,a_2,a_3,\dots,a_k} = \binom{n}{1}\binom{n-1}{a_2,a_3,\dots,a_k} = n\cdot \binom{n-1}{a_2,a_3,\dots,a_k}$$ remembering that $\binom{n}{1}=n$. This explains the next if condition with the comment "remove the silly 1's"

Now, finally, in the case that there are no 1's, we can recognize that $$\binom{n}{a_1,a_2,a_3,\dots,a_k} = \binom{n-1}{a_1-1,a_2,a_3,\dots,a_k} + \binom{n-1}{a_1,a_2-1,a_3,\dots,a_k}+\dots+\binom{n-1}{a_1,a_2,a_3,\dots,a_k-1}$$.

To explain this identity, let us go back to what a multinomial coefficient represents. One of the most common of the many interpretations is that it is the number of different strings of length $n$ made up of $k$ characters where there are $a_i$ copies of character $i$ included. The above identity can be recognized as effectively breaking into cases based on what the first character of the string is and adding across the various cases, there being $n-1$ spaces left to fill with the same corresponding amounts of each type of character to be used except for what the first character was that you used needing one less.

---

(You could have coded it to note $\binom{n}{a_1,a_2,\dots,a_k} = \binom{n}{a_1}\binom{n-a_1}{a_2}\binom{n-a_1-a_2}{a_3}\cdots \binom{n-a_1-a_2-\dots-a_{k-1}}{a_k}$ and looped more efficiently over the binomial coefficients themselves.)