9
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ 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.? $\endgroup$ – Tom Goodwillie Mar 28 '17 at 18:08
  • 7
    $\begingroup$ 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. $\endgroup$ – Abdelmalek Abdesselam Mar 28 '17 at 18:21
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Mar 28 '17 at 18:31
  • $\begingroup$ @Gerhard: maybe with general Witt vectors? $\endgroup$ – Abdelmalek Abdesselam Mar 28 '17 at 18:39
  • $\begingroup$ @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. $\endgroup$ – Gerhard Paseman Mar 28 '17 at 18:46
15
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Abdelmalek Abdesselam Mar 28 '17 at 22:41
  • 3
    $\begingroup$ 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)$. $\endgroup$ – KConrad Mar 28 '17 at 23:05
  • $\begingroup$ @KConrad Thank you! It was backwards, and it's fixed now. $\endgroup$ – Gjergji Zaimi Mar 28 '17 at 23:16
  • 3
    $\begingroup$ @GjergjiZaimi I hope you won't mind that I added this formula to the Wikipedia page on Kummer's theorem. $\endgroup$ – Joe Silverman Mar 29 '17 at 18:30
5
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.