Singmaster's conjecture

Last updated November 09, 2024

Unsolved problem in mathematics:

Does every entry (apart from 1) of Pascal's triangle appear fewer than N times for some constant N?

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 (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.

Statement

Let N(a) be the number of times the number a > 1 appears in Pascal's triangle. In big O notation, the conjecture is:

N(a)=O(1).

Known bound

Singmaster (1971) showed that

N(a)=O(\log a).

Abbot, Erdős, and Hanson (1974) (see References) refined the estimate to:

N(a)=O\left({\frac {\log a}{\log \log a}}\right).

The best currently known (unconditional) bound is

N(a)=O\left({\frac {(\log a)(\log \log \log a)}{(\log \log a)^{3}}}\right),

and is due to Kane (2007). Abbot, Erdős, and Hanson note that conditional on Cramér's conjecture on gaps between consecutive primes that

N(a)=O\left((\log a)^{2/3+\varepsilon }\right)

holds for every $\varepsilon >0$ .

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 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

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

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

where F_j is the jth Fibonacci number (indexed according to the convention that F₀ = 0 and F₁ = 1). 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 ${a \choose 1}$ and ${a \choose a-1}.$

Elementary examples

2 appears just once; all larger positive integers appear more than once;
3, 4, 5 each appear two times; infinitely many 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;
(it is in principle not excluded that such a coefficient would appear 5, 7 or more times, but no such example is known)
all numbers of the form ${p \choose 2}$ for prime $p>3$ appear four times;
Infinitely many appear exactly six times, including each of the following:

120={120 \choose 1}={120 \choose 119}={16 \choose 2}={16 \choose 14}={10 \choose 3}={10 \choose 7}

210={210 \choose 1}={210 \choose 209}={21 \choose 2}={21 \choose 19}={10 \choose 4}={10 \choose 6}

1540={1540 \choose 1}={1540 \choose 1539}={56 \choose 2}={56 \choose 54}={22 \choose 3}={22 \choose 19}

7140={7140 \choose 1}={7140 \choose 7139}={120 \choose 2}={120 \choose 118}={36 \choose 3}={36 \choose 33}

11628={11628 \choose 1}={11628 \choose 11627}={153 \choose 2}={153 \choose 151}={19 \choose 5}={19 \choose 14}

24310={24310 \choose 1}={24310 \choose 24309}={221 \choose 2}={221 \choose 219}={17 \choose 8}={17 \choose 9}

The next number in Singmaster's infinite family (given in terms of Fibonacci numbers), and the next smallest number to occur six or more times, is

a=61218182743304701891431482520

:^[1]

a={a \choose 1}={a \choose a-1}={104 \choose 39}={104 \choose 65}={103 \choose 40}={103 \choose 63}

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:

3003={3003 \choose 1}={78 \choose 2}={15 \choose 5}={14 \choose 6}={14 \choose 8}={15 \choose 10}={78 \choose 76}={3003 \choose 3002}

It is not known whether infinitely many numbers appear eight times, nor even whether any other numbers than 3003 appear eight times.

The number of times n appears in Pascal's triangle is

∞, 1, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 2, 4, 2, 2, 2, 2, 3, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 2, 2, 2, 2, 4, 2, 2, ... (sequence A003016 in the OEIS )

By Abbott, Erdős, and Hanson (1974), the number of integers no larger than x that appear more than twice in Pascal's triangle is O(x^1/2).

The smallest natural number (above 1) that appears (at least) n times in Pascal's triangle is

2, 3, 6, 10, 120, 120, 3003, 3003, ... (sequence A062527 in the OEIS )

The numbers which appear at least five times in Pascal's triangle are

1, 120, 210, 1540, 3003, 7140, 11628, 24310, 61218182743304701891431482520, ... (sequence A003015 in the OEIS )

Of these, the ones in Singmaster's infinite family are

1, 3003, 61218182743304701891431482520, ... (sequence A090162 in the OEIS )

Open questions

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. It is also unknown whether numbers appear exactly five or seven times.

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial $(x + y) n$ into a sum involving terms of the form $ax b y c$ , where the exponents $b$ and $c$ are nonnegative integers with $b + c = n$ , and the coefficient $a$ of each term is a specific positive integer depending on $n$ and $b$ . For example, for $n = 4$ ,

In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. So, two combinations are identical if and only if each combination has the same members. If the set has n elements, the number of k-combinations, denoted by $or, is equal to the binomial coefficient$

In mathematics, the factorial of a non-negative integer $,$ denoted by $,$ is the product of all positive integers less than or equal to $.$ The factorial of also equals the product of $with the next smaller factorial: For example, The value of 0! is 1, according to the convention for an empty product.$

The Sierpiński triangle, also called the Sierpiński gasket or Sierpiński sieve, is a fractal with the overall shape of an equilateral triangle, subdivided recursively into smaller equilateral triangles. Originally constructed as a curve, this is one of the basic examples of self-similar sets—that is, it is a mathematically generated pattern that is reproducible at any magnification or reduction. It is named after the Polish mathematician Wacław Sierpiński, but appeared as a decorative pattern many centuries before the work of Sierpiński.

In mathematics, Pascal's triangle is an infinite triangular array of the binomial coefficients which play a crucial role in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in Persia, India, China, Germany, and Italy.

In mathematics, a multiset is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that element in the multiset. As a consequence, an infinite number of multisets exist that contain only elements $a$ and $b$ , but vary in the multiplicities of their elements:

<span class="mw-page-title-main">Tetrahedral number</span> Polyhedral number representing a tetrahedron

A tetrahedral number, or triangular pyramidal number, is a figurate number that represents a pyramid with a triangular base and three sides, called a tetrahedron. The $n$ th tetrahedral number, $Te n$ , is the sum of the first $n$ triangular numbers, that is,

In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials.

In mathematics, the binomial series is a generalization of the polynomial that comes from a binomial formula expression like $for a nonnegative integer . Specifically, the binomial series is the MacLaurin series for the function, where and . Explicitly,$

In mathematics, Pascal's pyramid is a three-dimensional arrangement of the trinomial numbers, which are the coefficients of the trinomial expansion and the trinomial distribution. Pascal's pyramid is the three-dimensional analog of the two-dimensional Pascal's triangle, which contains the binomial numbers and relates to the binomial expansion and the binomial distribution. The binomial and trinomial numbers, coefficients, expansions, and distributions are subsets of the multinomial constructs with the same names.

In number theory, a pentatope number is a number in the fifth cell of any row of Pascal's triangle starting with the 5-term row 1 4 6 4 1, either from left to right or from right to left. It is named because it represents the number of 3-dimensional unit spheres which can be packed into a pentatope of increasing side lengths.

In mathematics the nth central binomial coefficient is the particular binomial coefficient

In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for positive natural numbers n and k, $where is a binomial coefficient; one interpretation of the coefficient of the x k term in the expansion of (1 + x) n . There is no restriction on the relative sizes of n and k, since, if n < k the value of the binomial coefficient is zero and the identity remains valid.$

In mathematics, Pascal's simplex is a generalisation of Pascal's triangle into arbitrary number of dimensions, based on the multinomial theorem.

In matrix theory and combinatorics, a Pascal matrix is a matrix containing the binomial coefficients as its elements. It is thus an encoding of Pascal's triangle in matrix form. There are three natural ways to achieve this: as a lower-triangular matrix, an upper-triangular matrix, or a symmetric matrix. For example, the 5 × 5 matrices are:

The Leibniz harmonic triangle is a triangular arrangement of unit fractions in which the outermost diagonals consist of the reciprocals of the row numbers and each inner cell is the cell diagonally above and to the left minus the cell to the left. To put it algebraically, $L (r, 1) = 1/ r$ (where $r$ is the number of the row, starting from 1, and $c$ is the column number, never more than r) and $L (r, c) = L (r - 1, c - 1) - L (r, c - 1).$

<span class="mw-page-title-main">Star of David theorem</span> Mathematical result on arithmetic properties of binomial coefficients

The Star of David theorem is a mathematical result on arithmetic properties of binomial coefficients. It was discovered by Henry W. Gould in 1972.

Gould's sequence is an integer sequence named after Henry W. Gould that counts how many odd numbers are in each row of Pascal's triangle. It consists only of powers of two, and begins:

Bernoulli's triangle is an array of partial sums of the binomial coefficients. For any non-negative integer n and for any integer k included between 0 and n, the component in row n and column k is given by:

References

↑ De Weger, Benjamin M.M. (August 1995). "Equal binomial coefficients: some elementary considerations" (PDF). Econometric Institute Research Papers: 3. Retrieved 6 September 2024.

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" (PDF), Fibonacci Quarterly , 13 (4): 295–298, doi:10.1080/00150517.1975.12430610, 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" (PDF), INTEGERS: The Electronic Journal of Combinatorial Number Theory , 7: #A53, MR 2373115 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] De Weger, Benjamin M.M. (August 1995). "Equal binomial coefficients: some elementary considerations" (PDF). Econometric Institute Research Papers: 3. Retrieved 6 September 2024.

[1]