Singmaster's conjecture
Singmaster's conjecture is a conjecture in combinatorial number theory, named after the British mathematician David Singmaster who proposed it in 1971. It says that there is a finite upper bound on the multiplicities of entries in Pascal's triangle. It is clear that the only number that appears infinitely many times in Pascal's triangle is 1, because any other number x can appear only within the first x + 1 rows of the triangle.
Statement
Let N be the number of times the number a > 1 appears in Pascal's triangle. In big O notation, the conjecture is:Known bound
Singmaster showed thatAbbott, Erdős, and Hanson refined the estimate to:
The best currently known bound is
and is due to Kane. Abbott, Erdős, and Hanson note that, conditional on Cramér's conjecture on gaps between consecutive primes,
holds for every.
Singmaster showed that the Diophantine equation
has infinitely many solutions for the two variables n, k. It follows that there are infinitely many triangle entries of multiplicity at least 6: For any non-negative i, a number a with six appearances in Pascal's triangle is given by either of the above two expressions with
where Fj is the jth Fibonacci number. The above two expressions locate two of the appearances; two others appear symmetrically in the triangle with respect to those two; and the other two appearances are at and
Elementary examples
- 2 appears just once; all larger positive integers appear more than once;
- 3, 4, 5 each appear two times; infinitely many numbers appear exactly twice;
- all odd prime numbers appear two times;
- 6 appears three times, as do all central binomial coefficients except for 1 and 2;
- all numbers of the form for prime appear four times;
- Infinitely many appear exactly six times, including each of the following:
- The smallest number to appear eight times – indeed, the only number known to appear eight times – is 3003, which is also a member of Singmaster's infinite family of numbers with multiplicity at least 6:
By Abbott, Erdős, and Hanson, the number of integers no larger than x that appear more than twice in Pascal's triangle is.
The smallest natural number greater than 1 that appears n times in Pascal's triangle is
The numbers which appear at least five times in Pascal's triangle are
Of these, the ones in Singmaster's infinite family are