10

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.

Community
  • 1
Joe Silverman
  • 45,660
  • 7
    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
  • 7
    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
  • 1
    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 04 '19 at 19:47

2 Answers2

15

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}.$$

Gjergji Zaimi
  • 85,056
  • 1
    Nice! Do you know analogues of Kummer's formula for more exotic integer-valued ratios of factorials as in http://mathoverflow.net/questions/26336/integer-valued-factorial-ratios ? 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
  • 3
    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
  • 3
    @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
6

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}$$

JMP
  • 1,226
  • 5
  • 13
  • 21