# 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
• @Abdelmalek , sorry, have not knowingly worked with Witt vectors. I would prove that the total number of carries is independent of summand order in much the same way I would prove the total is independent of summand order. Gerhard "Isn't Fond Of Mathematical Machinery" Paseman, 2017.03.28. – Gerhard Paseman Mar 28 '17 at 18:46

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