# p-adic valuation for multinomial coefficients

Kummer's formula
https://en.wikipedia.org/w/index.php?title=Kummer%27s_theorem&oldid=745783657 says that $$\text{ord}_p \binom{n}{k}$$ is the number of carries required when adding the base-$p$ expansions of $k$ and $n-k$. Is there a similar formula for the $p$-adic valuation of a multinomial coefficient $$\binom{n}{k_1,\ldots,k_r} := \frac{n!}{k_1!\cdots k_r!} ?$$ If so, is there a good reference (free online for preference, but failing that, in a book)?

There is a related question Reference needed for Lucas' Theorem for multinomial coefficients modulo a prime, but it involves the value of the multinomial coefficient modulo $p$, not the $p$-adic valuation.

• Isn't it just going to be the total number of carries required when first adding $k_1$ and $k_2$, then adding $k_1+k_2$ and $k_3$, then adding $k_1+k_2+k_3$ and $k_4$, etc.? – Tom Goodwillie Mar 28 '17 at 18:08
• Tom's argument also shows the total number of carries does not depend on the order of summation. If one asked me to prove that last statement, I don't know how one would start without having Joe's question in mind. – Abdelmalek Abdesselam Mar 28 '17 at 18:21
• If I had to prove the statement @Abdelmalek made regarding order of summation, I would use induction on the number of summands, making sure I did the case of three summands carefully. Gerhard "Is Feeling Rather Recursiony Today" Paseman, 2017.03.28. – Gerhard Paseman Mar 28 '17 at 18:31
• @Gerhard: maybe with general Witt vectors? – Abdelmalek Abdesselam Mar 28 '17 at 18:39
• Yes, this is just the total carry. Reminds me of the following result due to Steve Doty: When we view the space of homogeneous polynomials of degree $n$ in $r$ variables as a module over $SL_r(\overline{\Bbb{F}_p})$, acting on the variables by linear substitutions, the various carry patters (=which carrys appear at which digit positions) determines the irreducible composition factors. Yours truly had the pleasure of extending and refining (to the extent it was feasible) those results to algebraic groups of types $B,C,D$. – Jyrki Lahtonen Feb 4 '19 at 19:47

Denote the sum of the digits of $n$ in base $b$ by $S(n)$. Then the number of carries when adding $k_1+k_2$ is $$\frac{1}{b-1}\big(S(k_1)+S(k_2)-S(k_1+k_2)\big).$$ This shows that the number of carries when successively adding $(((k_1+k_2)+k_3)+\cdots +k_r)$ is $$\frac{1}{b-1}\left(\sum_{i=1}^r S(k_i)-S\left(\sum_{i=1}^r k_i\right)\right),$$ and this last expression is clearly independent of the order in which they are added. The formula for the multinomial coefficient can thus be written as $$\operatorname{ord}_p \binom{n}{k_1,\ldots,k_r}=\frac{\sum_{i=1}^rS(k_i)-S(n)}{p-1}.$$

• Nice! Do you know analogues of Kummer's formula for more exotic integer-valued ratios of factorials as in mathoverflow.net/questions/26336/… ? meaning a relation between order in $p$ and carries when doing arithmetic with arguments of the factorials. – Abdelmalek Abdesselam Mar 28 '17 at 22:41
• Using the formula ${\rm ord}_p(n!) = (n - S(n))/(p-1)$, your last formula follows from taking the $p$-adic valuation of each factorial appearing in the multinomial coefficient: $(n - S(n))/(p-1) - \sum_{i=1}^r (k_i - S(k_i))/(p-1)$: since $n = k_1 + \cdots + k_r$, in that difference the $n$ and $\sum k_i$ cancel out. Also it shows the order of subtraction in your formula is backwards: it should be $(\sum_{i=1}^r S(k_i) - S(n))/(p-1)$. – KConrad Mar 28 '17 at 23:05
• @KConrad Thank you! It was backwards, and it's fixed now. – Gjergji Zaimi Mar 28 '17 at 23:16
• @GjergjiZaimi I hope you won't mind that I added this formula to the Wikipedia page on Kummer's theorem. – Joe Silverman Mar 29 '17 at 18:30

You can write:

$$\binom{n}{k_1,\ldots,k_r} = \frac{n!}{k_1!\cdots k_r!}$$

as:

$$\binom{n}{k_1,\ldots,k_r} = \binom{n}{k_1}\binom{n-k_1}{k_2}\ldots\binom{n-k_1\ldots-k_{r-1}}{k_r}$$

• What does this have to do with the question being asked about p-adic valuations? – Yemon Choi Mar 28 '17 at 19:23
• @YemonChoi; apply $ord_p$ to each component on the RHS – JMP Mar 28 '17 at 19:37
• this is basically the idea given by Tom in a comment above. – Abdelmalek Abdesselam Mar 28 '17 at 22:42