Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for some reading on when binomial coefficients are equal to $p^2$ for $p$ a prime. In general I imagine this is rare, as there are simply too many factors. Concretely, I am looking for pairs $(n, k)$ such that ${n + k - 1 \choose k} = p^2$.

share|improve this question
1  
You are right in the sense that usually there are too many factors. This guided me to my answer. –  Jyrki Lahtonen Jun 12 '13 at 21:19

2 Answers 2

up vote 9 down vote accepted

For the equality $$ {m\choose k}=p^2 $$ to hold for a prime $p$, we must obviously have $2p\le m$. Otherwise $m!$ won't be divisible by $p^2$ so neither will the binomial coefficient.

I claim that this implies $k=1$.

Without loss of generality we can assume that $k\le m/2$. If $2<k\le m/2$, then $$ {m\choose k}\ge {m\choose 3}=\frac{m(m-1)(m-2)}6, $$ which is larger than $m^2/4\ge p^2$ whenever $m\ge6$. This means that we must have $k=1$ or $k=2$ or $m<6$. The last possibility won't concern us - a brute force check tells in few seconds that there are no counterexamples.

So we need to take a look the case $k=2$. But $$ {m\choose2}=\frac{m(m-1)}2. $$ Here $m$ and $m-1$ have no common factors, so from $m(m-1)=2p^2$ we get that either $m-1=2, m=p^2$ or $m-1=p, m=2p$ and both are impossible. The claim follows from this.

Obviously you can arrange ${m\choose 1}=m$ to be anything you want.

share|improve this answer
    
many thanks for this response. A neat proof! However I wonder if you could elaborate on why it is necessary that $2p \leq m$, and not the more trivial bound that $p^2 \leq m$? –  Mike Jun 13 '13 at 14:19
1  
Never mind, I now see that you would need $2p \cdot (2p - 1) \cdots (p)(p-1)\cdots$. Thanks again –  Mike Jun 13 '13 at 14:38

No nontrivial pairs exist. According to the abstract of this paper, $\binom{n}{s}$ has at least as many distinct prime factors as $n$. If we desire $\binom{n}{s}=p^2$, it follows that $n$ must be a prime power. If $n=q^e$ for some prime $q$, then $q|\binom{n}{s}$ so that $q=p$, and $n=p^e$ with $e\ge 2$.

We have the solution $e=2$ with $s=1$ or $s=p^2-1$. If $e\ge 3$, it follows that:

$$\binom{p^e}{s}\ge p^e>p^2$$

if we exclude $s=0,p^e$. It follows that there are no solutions for $e\ge 3$.

share|improve this answer
    
I accepted Jyrki's answer, but I want to thank you for the referral to the paper, this is useful for the more general aspects of my project –  Mike Jun 13 '13 at 14:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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