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.

We will start by proving a simple lemma

Lemma
-----

Let p be a prime and a and b be integers.  Then

    (ap+b)!       a
    ------- = (-1)  b!          mod p                        [2]
    a! p^a

Proof
-----

Let <p> mean some multiple of p.

    (ap+b)!

         b             a     p-1
        ---           ---    ---
    = [ | |(ap+j) ] [ | | jp | | ((j-1)p+i) ]           juggling terms
        j=1           j=1    i=1

         b             a
        ---           ---
    = [ | |(ap+j) ] [ | | jp (-1 + <p>) ]       Since (p-1)! = -1 mod p
        j=1           j=1

    = (b! + <p>) a! p^a ((-1)^a +<p>)

Thus, dividing by a! p^a, we get

    (ap+b)!       a
    ------- = ((-1)  + <p>) (b! + <p>)
    a! p^a

                  a
            = (-1)  b!          mod p

QED

Corollary
---------

Let p be a prime and a and b be vectors of integers.  Then

     (ap+b)!       |a|
    -------- = (-1)    b!       mod p                        [3]
    a! p^|a|

Proof
-----
Multiply [2] for each component of ap+b, then use [1a] and [1b].

QED

Lemma
-----
Let p be a prime, a and b be integers, and c and d be vectors of
integers.  If b < p and d[j] < p for all j, then

    C(ap+b,cp+d) = C(a,c) C(b,d)        mod p                [4]

Proof
-----
First we handle the case where b >= |d|.

    C(ap+b,cp+d)

                (ap+b)!
    = ---------------------------
      (cp+d)! [(a-|c|)p+(b-|d|)]!

        p^|c|  (ap+b)!      p^{a-|c|}
    = -------- ------- -------------------
       (cp+d)!   p^a   [(a-|c|)p+(b-|d|)]!

      c! p^|c| (ap+b)! (a-|c|)! p^{a-|c|}      a!
    = -------- ------- ------------------- -----------
       (cp+d)! a! p^a  [(a-|c|)p+(b-|d|)]! c! (a-|c|)!

                  (-1)^a b!                 a!
    = --------------------------------- -----------     mod p
      (-1)^|c| d! (-1)^{a-|c|} (b-|d|)! c! (a-|c|)!

          b!         a!
    = ---------- ----------
      d!(b-|d|)! c!(a-|c|)!

    = C(a,c) C(b,d)

Note that we used the fact that b-|d| < p and d[j] < p for all j when we
used the inverse of [2] and [3] in the mod p step above; (b-|d|)! and d!
are invertible mod p if b-|d| and all components of d are less than p.

Suppose b < |d|.  The right side of [4] is 0, so we need to show that
C(ap+b,cp+d) = 0 mod p.

If a < |c|, then ap+b < |cp+d| and therefore C(ap+b,cp+d) = 0.

If a >= |c|, then in the base p expansion of ap+b the 1s digit, b, is
less than the sum of the 1s digits of the components of cp+d, |d|.
This implies a factor of p in C(ap+b,cp+d) (see the last line of the
article "Prime Multinomial Divisors").  Thus, C(ap+b,cp+d) = 0 mod p.

QED

Corollary (Multinomial Lucas Correspondence)
--------------------------------------------
Let p be a prime, n an integer, and m be a vector of integers.
Develop the base-p expansions of n and m[j]:

        ---     k
    n = >   n  p
        ---  k
         k

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

Then,

             ---
    C(n,m) = | | C(n ,m )       mod p                        [5]
              k     k  k

Proof
-----
Apply [4] for each k.

QED

Rob Johnson