Singmaster's conjecture is a conjecture in combinatorial number theory in mathematics, 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 (other than the number 1, which appears infinitely many times). 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. Paul Erdős said that Singmaster's conjecture is probably true but he suspected it would be very hard to prove.
Let N(a) be the number of times the number a > 1 appears in Pascal's triangle. In big O notation, the conjecture is:
Singmaster (1971) showed that
Abbot, Erdős, and Hanson (see References) refined the estimate. The best currently known (unconditional) bound is
holds for every .
Singmaster (1975) showed that the Diophantine equation
has infinitely many solutions for the two variables n, k. It follows that there are infinitely many entries of multiplicity at least 6. The solutions are given by
where Fn is the nth Fibonacci number (indexed according to the convention that F1 = F2 = 1).
Computation tells us that
- 2 appears just once; all larger positive integers appear more than once;
- 3, 4, 5 each appear two times;
- all odd prime numbers appear two times;
- 6 appears three times;
- Many numbers appear four times.
- Each of the following appears six times:
- The smallest number to appear eight times – indeed, the only number known to appear eight times – is 3003, which is also the first member of Singmaster's infinite family of numbers with multiplicity at least 6:
- The next number in Singmaster's infinite family, and the next smallest number known to occur six or more times, is 61218182743304701891431482520.
It is not known whether any number appears more than eight times, nor whether any number besides 3003 appears that many times. The conjectured finite upper bound could be as small as 8, but Singmaster thought it might be 10 or 12.
Do any numbers appear exactly five or seven times?
It would appear from a related entry, (sequence A003015 in OEIS) in the Online Encyclopedia of Integer Sequences, that no one knows whether the equation N(a) = 5 can be solved for a. Nor is it known whether any number appears seven times.
- Singmaster, D. (1971), "Research Problems: How often does an integer occur as a binomial coefficient?", American Mathematical Monthly 78 (4): 385–386, doi:10.2307/2316907, JSTOR 2316907, MR 1536288.
- Singmaster, D. (1975), "Repeated binomial coefficients and Fibonacci numbers", Fibonacci Quarterly 13 (4): 295–298, MR 0412095.
- Abbott, H. L.; Erdős, P.; Hanson, D. (1974), "On the number of times an integer occurs as a binomial coefficient", American Mathematical Monthly 81 (3): 256–261, doi:10.2307/2319526, JSTOR 2319526, MR 0335283.
- Kane, Daniel M. (2007), "Improved bounds on the number of ways of expressing t as a binomial coefficient", Integers: Electronic Journal of Combinatorial Number Theory 7: #A53, MR 2373115.