Multinomial Coefficients
------------------------
Let us adopt the standard notation for multinomial coefficients.  That
is, for an integer n and a vector of integers m, define

         ---
    m! = | | m[j]!                                          [1a]
          j

          ---
    |m| = >   m[j]                                          [1b]
          ---
           j

                 n!
    C(n,m) = ----------                                     [1c]
             m!(n-|m|)!

If |m| > n or m[j] < 0 for any j, C(n,m) = 0.

For example,

                    7!
    C(7,[3,2]) = -------- = 210
                 3! 2! 2!

To compute the number of factors of a prime p in C(n,m), we start by
computing the number of factors of p in n!.

Counting Prime Factors of n!
----------------------------
Let us count the number of factors of a prime p in n!

A factor of p will come from each multiple of p less than n; that is,
floor(n/p).  This only counts the multiples of p^2 once, so we add 1 for
each multiple of p^2; that is floor(n/p^2).  This only counts the
multiples of p^3 twice, so we add 1 for each multiple of p^3; that is
floor(n/p^3).  Continuing this way, we get the number of factors of p in
n! to be

    oo
    ---        n
    >   floor(---)                                           [2]
    ---       p^j
    j=1

Write n in base p:

        ---     k
    n = >   n  p                                             [3]
        ---  k
         k

Then, for any j,

           n     ---     k-j
    floor(---) = >   n  p                                    [4]
          p^j    ---  k
                 k>j

Summing over all j >= 1, we get

    oo
    ---        n     ---    p^k-1
    >   floor(---) = >   n  -----
    ---       p^j    ---  k  p-1
    j=1               k

                          ---
                   = (n - >   n ) / (p-1)                    [5]
                          ---  k
                           k

Thus, the number of factors of p in n! is n, less the sum of the base p
digits of n, divided by p-1.

Counting Prime Factors of Multinomial Coefficients
--------------------------------------------------
Write m[j] in base p:

           ---        k
    m[j] = >   m [j] p                                       [6]
           ---  k
            k

Write r = n-|m| in base p:

        ---     k
    r = >   r  p                                             [7]
        ---  k
         k

The number of factors of p in C(n,m) is the number of factors of p in n!
minus the number of factors of p in (n-|m|)! minus the sum of the number
of factors of p in the m[j].  That is, using [5],

     1         ---            ---       ---         ---
    --- [ (n - >   n ) - (r - >   r ) - >   (m[j] - >   m [j]) ]
    p-1        ---  k         ---  k    ---         ---  k
                k              k         j           k

       1  ---
    = --- >   |m | + r - n                                   [8]
      p-1 ---   k     k   k
           k

Equation [8] follows since

            ---
    n - r - >   m[j] = n - (n-|m|) - |m| = 0
            ---
             j

Not only is [8] the number of factors of p in C(n,m), it is also the
number of base p carries that occur when adding the m[j] and r to get n.
That is because every time a carry takes p from the sum of one column
and adds 1 to the next column, the difference in the sum of the digits
increases by p-1.

For example, let p = 7 and consider the base 7 sum

    214
    146
      5
    ---
    401

The sum of the digits in the addends is 23 while the sum of the digits
in the sum is 5; a difference of 18 = 3(7-1).  There is a carry of 2
from the 1s column to the 7s column, and then a carry of 1 from the 7s
column to the 49s column; 3 carries.  Thus, there are 3 factors of 7 in
C(197,[109,83]) (verification left as an exercise for the reader).

Therefore, the only way that C(n,m) is not divisible by p is if there
are no base p carries when adding the m[j] and r to get n; that is, if

    |m_k| + r_k = n_k                                       [9a]

for every k.  Since r = n-|m|, this is the same as saying

    |m_k| <= n_k                                            [9b]

for every k.

Summary
-------
The number of factors of p in C(n,m) is given by

     1  ---
    --- >   |m | + r - n
    p-1 ---   k     k   k
         k

which is also the number of base p carries that occur when adding the
m[j] and n-|m| to get n.

C(n,m) is not divisible by p if and only if |m_k| <= n_k for every k.

Rob Johnson