(no subject)
Some notation: I came upon this rant by Dijkstra a while ago, which says essentially, that the n choose m notation is dumb, and we should write P(i,j) for i+j choose i, instead. I was convinced. Since then, I've seen lots of other reasons that that notation is better, so I'm adopting it in this post. I'll probably also use it in other casual mathematical writings where I feel like it won't get in the way of what I'm trying to get across.
As usual, I'm sure someone has noticed all this before and made a better writeup, but what the hell.
For p prime, what is the power of p in (n!), denoted ordp(n!). The usual formulation is there are [n/p] multiples of p below n, [n/p2] multiples of p2, and so on, so
ordp(n!) = [n/p]+[n/p2]+[n/p3]+... = &Sigmak[n/pk]
Well, if n=dnpn+dn-1pn-1+...+d1p+d0 is the base p expansion of n, then
[n/pk] = dnpn-k+...+dk+1p+dk
So,
ordp(n!) = dn(pn-1+pn-2+...+p+1) + dn-1(pn-2+...+p+1)+...+d2(p+1)+d1p+d00 =
dn(pn-1)/(p-1)+...+d2(p2-1)/(p-1)+d1(p-1)/(p-1)+d0(1-1)/(p-1) =
(n-s)/(p-1)
Here, s=dn+...+d0, the sum of the digits of n in base p.
I think this is fairly cool by itself. It doesn't happen very often that adding up the digits in a number is actually useful, despite how often that sort of thing comes up in recreational math.
Now what's ordp(P(n,m))? Let r, s, and t be the sums of the digits in base p of n+m, n, and m respectively. Then,
ordp(P(n,m)) = ordp((n+m)!/(n!m!)) = ordp((n+m)!)-ordp(n!)-ordp(m!) = (n+m-r)/(p-1)-(n-s)/(p-1)-(m-t)/(p-1) = (s+t-r)/(p-1)
If you think about it, this is just the number of times that you carry a digit when you're adding n and m in base p. Weird.
As usual, I'm sure someone has noticed all this before and made a better writeup, but what the hell.
For p prime, what is the power of p in (n!), denoted ordp(n!). The usual formulation is there are [n/p] multiples of p below n, [n/p2] multiples of p2, and so on, so
ordp(n!) = [n/p]+[n/p2]+[n/p3]+... = &Sigmak[n/pk]
Well, if n=dnpn+dn-1pn-1+...+d1p+d0 is the base p expansion of n, then
[n/pk] = dnpn-k+...+dk+1p+dk
So,
ordp(n!) = dn(pn-1+pn-2+...+p+1) + dn-1(pn-2+...+p+1)+...+d2(p+1)+d1p+d00 =
dn(pn-1)/(p-1)+...+d2(p2-1)/(p-1)+d1(p-1)/(p-1)+d0(1-1)/(p-1) =
(n-s)/(p-1)
Here, s=dn+...+d0, the sum of the digits of n in base p.
I think this is fairly cool by itself. It doesn't happen very often that adding up the digits in a number is actually useful, despite how often that sort of thing comes up in recreational math.
Now what's ordp(P(n,m))? Let r, s, and t be the sums of the digits in base p of n+m, n, and m respectively. Then,
ordp(P(n,m)) = ordp((n+m)!/(n!m!)) = ordp((n+m)!)-ordp(n!)-ordp(m!) = (n+m-r)/(p-1)-(n-s)/(p-1)-(m-t)/(p-1) = (s+t-r)/(p-1)
If you think about it, this is just the number of times that you carry a digit when you're adding n and m in base p. Weird.