Monday, 4 January 2010

co.combinatorics - Factorials in Pascals Triangle

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,
$$sleft[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$:
$$4quad 9quad 16quad 25quad 81quad 126quad 225quad 2401quad 4375quad 9801quad 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.

No comments:

Post a Comment