Factorials in Pascals Triangle - MathOverflow

Factorials in Pascals Triangle

2010-03-04T05:30:34Z

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.

Answer by Ben Weiss for Factorials in Pascals Triangle

2010-03-04T09:31:54Z

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.

Answer by Greg Kuperberg for Factorials in Pascals Triangle

2010-05-20T06:17:17Z

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.

Answer by Gerhard Paseman for Factorials in Pascals Triangle

2010-05-22T05:12:19Z

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.

Gerhard "Ask Me About System Design" Paseman, 2010.05.21

Answer by Denis Serre for Factorials in Pascals Triangle

2010-10-04T13:28:50Z

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)$.