Factorials in Pascals Triangle

Hi,

I asked this question of Keith Conrad, and he suggested that I try posting here. One of my students observed that the only instances of factorials in the interior of Pascal's triangle are $\binom{4}{2}=3!$ and $\binom{10}{3}=\binom{16}{2}=5!$. I checked the first 500 rows, and he's right up to that point.

This is a special case of the apparently unsolved problem of finding non-trivial solutions to n!=a!b!c!... The special feature here is that I need (a+b)!=a!b!c!, and that seems like a special enough case to have been treated by someone. Unfortunately, literature searches have been fruitless, because every paper about Pascal's triangle contains the word "factorial" somewhere.

My best idea (which I can't make work) is to show that the powers of 7 in the equation (a+b)!=a!b!c! can't be made to match up unless neither side is a multiple of 7. Then exhaustive searching can show that the above are the only non-trivial solutions.

Thanks greatly for any ideas that anyone might have.

-
More generally, Richard Guy talks about nontrivial representations of n! = a!b!c!. Start with his book "Unsolved Problems in Number Theory", and keep going. Gerhard "Ask Me About System Design" Paseman, 2010.03.03 – Gerhard Paseman Mar 4 2010 at 5:42
The $n!=a!b!c!\dots$ problem is B23 in Guy, Unsolved Problems In Number Theory. He says Chris Caldwell has shown that aside from 9! = 7! 3! 3! 2!, 10! = 7! 6! = 7! 5! 3!, and 16! = 14! 5! 2!, there are no nontrivial examples with n up to 1,000,000. – Gerry Myerson Mar 4 2010 at 5:50
The powers of any prime can be made to match up. It may be that it's hard for several powers of primes to match up simultaneously, or for the magnitudes to match up at the same time. – Douglas Zare Mar 4 2010 at 6:14
The more general problem Gerry mentions is considered, but not solved, in: MR2373957 (2008k:11105) Luca, Florian On factorials which are products of factorials. (English summary) Math. Proc. Cambridge Philos. Soc. 143 (2007), no. 3, 533--542. 11N64 (11D41). It shows that truth of the abc conjecture would imply there are only finitely many solutions, and also mentions the conjecture that 16!=14!5!2! is the largest nontrivial solution. – Jonas Meyer Mar 4 2010 at 6:24
You all know this, but let me just stress again that solving $n!=a!b!c!$ is well-known to be hard, and that questioner is asking a question that might be much easier than this. – Kevin Buzzard Mar 4 2010 at 6:44

Let us assume that $(a+b)!=a!b!c!$ with $a\le b$. According to the experiments mentioned already, we may suppose that $a+b$ is very large. Because of $c!\le 2^{a+b}$, together with the Stirling formula, we see that $c< < a+b$. Therefore every prime $p$ dividing the binomial $C_{a+b}^a$ is small, compared with $a+b$, and in particular is smaller than $b$. This implies that there is no prime power $p^\ell$ between $b+1$ and $a+b$. Because of the Prime Number theorem, $a$ must be an $O(\log b)$.

-
 Re my comment above, "Thus any binomial that is a factorial must be near the edges of Pascal's triangle, according to the maximum gaps between primes." – Greg Kuperberg Oct 4 2010 at 20:32

To add to Greg Kuperberg's observation, let n be given and p a prime so that log(factorial p) > n, where log is to the base 2. Then p! > (n choose k) for 0 <= k <= n, and so p! cannot divide (n choose k). Thus if (n choose k) is a product of factorials, then none of n, n-1, ..., n-k+1 must be prime, nor (for sufficiently large n) twice a prime, nor three times a prime, and so on. An efficient computer search to check for Greg's relaxed condition [ (smooth( n choose k) )factorial <= ( n choose k )] might check n, n-1, etc. for prime divisors p such that p log(p/e) > n and stop when it encountered (n-k) having such a "large" divisor. Alternatively, define an appropriate degree of smooth and look for intervals of such smooth integers. Greg's entry suggests there are no intervals with 4 small appropriately smooth numbers.

-

Here is a proposal along the lines of what Ben Weiss said: Let $s(n)$, the "smoothness" of $n$, be the largest prime factor of $n$. Then as a necessary condition, $$s\left[\binom{n}{k}\right]! \le \binom{n}{k}.$$ Otherwise you can say that the binomial coefficient is not smooth enough for its size to be a factorial. This criterion eliminates large swaths of Pascal's triangle from consideration. A boneheaded somewhat informed (see below) run with Sage up to $n = 10^7$ found the solutions $n=10$ and $50$ for $k=3$ to the above inequality, and the following values of $n$ for $k=2$: $$4\quad 9\quad 16\quad 25\quad 81\quad 126\quad 225\quad 2401\quad 4375\quad 9801\quad 123201$$ It did not find any solutions with $\min(k,n-k) \ge 4$.

Here is part of the idea that can be made rigorous. As I said, it is a generalization of Ben Weiss' remark. Let $p$ be the largest prime not more than $n$. Then $$p! \ge \lfloor n/2 \rfloor ! > \binom{n}{k},$$ where the second inequality holds for $n \ge 14$; the combined inequality happens to also hold for $n \ge 5$. Thus $\binom{n}{k}$ is not smooth enough for its size to be a factorial if $n-p < k \le n/2$. Thus any binomial that is a factorial must be near the edges of Pascal's triangle, according to the maximum gaps between primes. These surviving binomial coefficients are much smaller than the ones in the middle, and the idea can then be repeated with other large prime factors of numbers close to $n$.

Moreover, for the original question of a binomial coefficient equal to a factorial, the binomial values for small $k$ grow much more slowly than factorials do, so you also get a severe upper bound on the density of such coincidences in a finite part of Pascal's triangle. It means that there are only a handful of entries left to check, say with a computer search.

-

This is only a start, but maybe it'll suggest to others how to proceed. If $p$ is a prime number, then there is no integer $1 \le n < p$ and integer $m$ with $${p\choose{n}} = m!$$ This is because the LHS is divisible by $p$ but is less than $p!$ and the right hand side cannot be both divisible by $p$ and less than $p!$

I'm not sure how to generalize this, but I hope it helps.

-
The number of times a prime $p$ divides $a+b \choose a,b$ is the number of carries when you add $a$ to $b$ written in base $p$. The number of times $p$ divides $c!$ is $(c-d)/(p-1)$ where $d$ is the sum of the digits of $c$ in base $p$. This shows there is no problem matching up powers of any particular prime, since you can get any multiplicity in $a+b \choose a,b$ and most multiplicities in $c!$. – Douglas Zare Mar 4 2010 at 10:28