Multiplicities of entries in Pascal's triangle

From Wikipedia, the free encyclopedia

In combinatorial number theory, it is clear that the only number that appears infinitely many times in Pascal's triangle is 1.

1 Preliminary computations
2 Results and questions
- 2.1 Do any numbers appear exactly five times in Pascal's triangle?
- 2.2 Singmaster's conjecture
3 See also
4 References
5 External links

[edit] Preliminary computations

Computation tells us that

2 appears just once; all larger positive integers appear more than once;

3, 4, 5 each appear 2 times;

6 appears 3 times;

Many numbers appear 4 times.

Each of the following appears 6 times:

${120 \choose 1} = {16 \choose 2} = {10 \choose 3}$

${210 \choose 1} = {21 \choose 2} = {10 \choose 4}$

${1540 \choose 1} = {56 \choose 2} = {22 \choose 3}$

${7140 \choose 1} = {239 \choose 2} = {36 \choose 3}$

${11628 \choose 1} = {153 \choose 2} = {19 \choose 5}$

${24310 \choose 1} = {221 \choose 2} = {17 \choose 8}$

The smallest number to appear 8 times is 3003:

${3003 \choose 1} = {78 \choose 2} = {15 \choose 5} = {14 \choose 6}$

[edit] Results and questions

David Singmaster (1971) (see References below) defined N(a) to be the multiplicity of the number a within Pascal's triangle. He proved that

$N(a) = O(\log a)\,$

(see big O notation). Abbot, Erdős, and Hanson (see References) refined the estimate.

Neither of those papers said whether any integer appears exactly five times or exactly seven times.

Singmaster (1975) showed that the diophantine equation

${n+1 \choose k+1} = {n \choose k+2},$

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

$n = F_{2i+2} F_{2i+3} - 1,\,$

$k = F_{2i} F_{2i+3} - 1,\,$

where F_n is the nth Fibonacci number (indexed according to the convention that F₁ = F₂ = 1).

[edit] Do any numbers appear exactly five times in Pascal's triangle?

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.

[edit] Singmaster's conjecture

Singmaster (1971) conjectured that there is a finite upper bound on the multiplicities (in the big O notation, N(a) = O(1)). He stated that Erdős concurred and said it could be difficult to prove.

[edit] See also

[edit] References

Singmaster, David, "How Often Does an Integer Occur as a Binomial Coefficient?", American Mathematical Monthly, volume 78, number 4, April 1971, pages 385—386.
Singmaster, David, "Repeated Binomial Coefficients and Fibonacci numbers", Fibonacci Quarterly, volume 13, number 4, pages 296—298, 1975.
Abbott, H.L., Erdős, P., and Hanson, D., "On the Number of Times an Integer Occurs as a Binomial Coefficient", American Mathematical Monthly, volume 81, number 3, March 1974, pages 256—261.