3
$\begingroup$

I've heard of a claim that when calculating the binomial formula with integer input:

$\mathrm{Bin}(n,k):=\prod^k_{i=1}\frac{n+1-i}{i}\in \mathbb{N}\ (\forall n,k\in\mathbb N)$

each denominator divides an unique numerator. since for calculating $n \choose k$ you divide $k$ many numerators ($n+1-k$ till $n$) by $k-1$ many denominators (numbers from $2$ to $k$), there obviously is a gap, where is it?

$\mathrm{Gap}(n,k):=\sum_{j=0}^{k-1}(n-j)-\sum^k_{i=2} n-(n \mod\ i)$

Remember, $n\mod i$ denotes the remainder from dividing $n$ by $i$. that means $i$ divides $n - (n \mod\ i)$. above formula $\mathrm{Gap}(n,k)$ just sums up all such expressions and calculates the number which isn't paired with a divisor. any other way to calculate this? the first sum has an explicit formula making it into a quadratic polynomial in $k$. anything known about the 2nd sum? did I make a mistake here?

I'd be already satisfied if someone could prove above claim that reason for the product $\mathrm{Bin}(n,k)$ of rational numbers being an integer is because there are pairs of numerator and denominator which are integers after the division, and that in such pairing no numerator is ever used twice.

$\endgroup$

1 Answer 1

16
$\begingroup$

The kind of pairing sought does not always exist. Take, for example, $$\binom{8}{4}=\frac{8\cdot7\cdot6\cdot5}{4\cdot3\cdot2\cdot1}.$$ The pair of $4$ must be $8$, the pair of $3$ must be $6$, and hence the pair of $2$ should be $7$ or $5$ which is not good.

On the other hand, it is possible to prove using unique factorization that the binomial coefficients are integers. Namely, for each prime $p$, one can show that the exponent of $p$ in $n!$ is at least the exponent of $p$ in $k!(n-k)!$. For more details, see here and here.

$\endgroup$
6
  • 4
    $\begingroup$ A slightly simpler example is $${7\choose3}={7\cdot6\cdot5\over3\cdot2\cdot1}$$ $\endgroup$ Dec 10, 2023 at 0:37
  • $\begingroup$ thanks for both examples! now I understand why there's no good implementation of integer-based Bin: you need to keep track of which numerator was already used! $\endgroup$ Dec 10, 2023 at 7:55
  • $\begingroup$ Note that while this is not true globally, it is true locally, that is, separately for each prime. $\endgroup$
    – tomasz
    Dec 10, 2023 at 10:44
  • $\begingroup$ @user11566470, what do you mean "there's no good implementation of integer-based Bin"? It's perfectly easy to implement. In C-like pseudocode, result = 1; for (int i = 0; i < k; i++) result = result * (n - i) / (i + 1); $\endgroup$ Dec 10, 2023 at 22:28
  • 1
    $\begingroup$ @user11566470 Please direct your last comment to Peter Taylor, otherwise he will not know about it. Use the @ symbol for that purpose. $\endgroup$
    – GH from MO
    Dec 17, 2023 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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