An interesting question on the bird site:

How do we know, arithmetically, that nCk is an integer? Why should both k! and (n-k)! simultaneously divide into n! ?


Cancel the (n-k)!, and we're left with "why does k! divide the falling factorial \(n^{\underline{k}}\)?" (notation aside). And that can be answered, I think, with an understanding of divisibility by prime powers in ranges of consecutive integers.

· · Web · 2 · 0 · 0

@bmreiniger You can show that each factor in the denominator divides the numerator, but showing that they all do so without fatally interfering with each other is a little trickier.

@ColinTheMathmo @bmreiniger that was my personal stumbling block with the factorial definition. You can divide \(n!\) by \(k!\), and you can divide \(n!\) by \((n-k)!\), but being able to divide \(n!\) by both... that was the surprise.

@ColinTheMathmo (cc @tpfto)
Trickier, sure, but I think my vague approach above works. Lemme try to describe some more (maybe a proofinatoot later); it's similar to the classic exercise that shows that the power of prime \(p\) in \(k!\) is \(\sum_{i\geq1} \left\lfloor\frac k{p^i}\right\rfloor\) \) (which I now realize has a name, "Legendre's formula"). The idea extends to say that the power of prime \(p\) in the falling factorial \(n^{\underline{k}}\) is _at least_ that quantity.

To be clear, I agree with the other thread here, that the other definitions are more natural. I'm approaching this from "how can we show this directly?".

@bmreiniger I agree that this approach can be pushed through, but it's not immediately obvious, and does require care. The question then is: "How clear *can* this be made?"

The discussion on Twitter has been interesting:

Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!