# How often does an integer occur as a binomial coefficient?

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/how-often-does-an-integer-occur-as-a-binomial-coefficient

- **Authors:** David Singmaster
- **Published:** 1971
- **Topic:** Mathematics
- **Original:** https://s3-us-west-1.amazonaws.com/fermatslibrary/uploads%2F1547144309469-f8captwk54a-ad9f0928139fdcf08fefb4848ea7c4b2%2Fpdfresizer.com-pdf-crop+%285%29.pdf
- **Pages:** 2
- **Annotations:** 4 comments in 4 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/how-often-does-an-integer-occur-as-a-binomial-coefficient

## Annotations

### Annotation 1 (page 1)

Beside the passage: “HOW OFTEN DOES AN INTEGER OCCUR AS A BINOMIAL COEFFICIENT? DAVID SINGMASTER, Polytechnic of the South Bank, London”

**Annotation** by Luís Batalha (2019-02-03):

> This paper is about the Sigmaster's Conjecture, which to this day still remains unsolved. The author, David Singmaster, is an American mathematician who is known for is mathematical puzzles as well as for his mathematical analysis of Rubik's Cube.
>
> ![](https://media.springernature.com/original/springer-static/image/art%3A10.1007%2Fs00283-018-9811-9/MediaObjects/283_2018_9811_Figa_HTML.jpg)
>
> To understand his conjecture let's first talk about Pascal's Triangle. Pascal's triangle is a number triangle with numbers arranged in staggered rows such that each number is the sum of the two numbers above (starting with 1) and also a binomial coefficient.
>
> His conjecture states that we can find a number $a$, so that no value occurs in Pascal’s triangle more than $a$ times ($a \neq 1$).
>
> $$
> N(a)< \infty
> $$
>
> ![](https://i.imgur.com/rInVEMh.png)

### Annotation 2 (page 2)

Beside the passage: “PROPOSITION. N(a) = O(log a).”

**Annotation** by Luís Batalha (2019-02-04):

> To prove the $O( \log a)$ bound we start by defining $N(a)$ as the number of solutions of $a=\binom{i+j}{j}=\binom{i+j}{i}$ , with $i,j \geq 1$ (since Pascal's triangle is symmetrical along its central column).
>
> Since, $\binom{i+j}{i}$ increases in each of $i$ and $j$ (in other words, if you pick a diagonal and follow it down or pick a column and follow it down the binomial coefficients will always increase), any choice of $i$ or $j$ admits a new solution value for $N(a)$.
>
> Now let's suppose that $a$ satisfies $a \leq \binom{2b}{b}$ implies that $i$ or $j < b$, so the solution count $N(a)≤ 2b$.
>
> Take the least such $b$. Then $2^{b-1} ≤\binom{2(b−1)}{b−1}≤ a$, $b ≤1+\log_2 a$, and $N(a) ≤ 2 + 2 \log_2 a = O(\log a)$

### Annotation 3 (page 2)

Beside the passage: “hence b ?<log2 a + 1, and N(a) ? 2 +2 log2 a = O(log a).”

**Annotation** by Luís Batalha (2019-02-04):

> In 2007, Daniel Kane, a mathematician from Harvard, was able to [improve the result and the current best bound](http://www.emis.de/journals/INTEGERS/papers/h53/h53.pdf) is:
>
> $$
> N(t) = O\big(\frac{(\log t)(\log \log \log t)}{
> (\log \log \ t)^2} \big)
> $$

### Annotation 4 (page 2)

Beside the passage: “Added in Proof: I have recently found that M(8) = 3003 and this is the only solution to N(a) > 8 with a < 223. There are six solutions to N(a) = 6 with a < 223, namely: 120, 210, 1540, 7140, 11628, and 24310.”

**Annotation** by Luís Batalha (2019-02-03):

> 3003 occurs twice in its own row, twice in row 78 and twice in rows 14 and 15.
> $$
> \binom{3003}{1} = \binom{78}{2} = \binom{15}{5} = \binom{14}{6}
> $$
>
> Additionally, it’s the only number known to appear 8 or more times. There are also no known integers which occur in the triangle exactly five or seven times.

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

1971] RESEARCH PROBLEMS 385

and so

2 (6) Z2 < I + 2 -

Since X, Y, Z are positive integers, inequality (6) implies that Z can take only a finite number of values. The same holds for Y (on using (5)) and X (on using (3) or the relation X < Y+Z). Since X+ Y+Z =,uA, A takes only a finite number of values. So do the sides a, b, c, in view of relations (2). Thus N(O) is finite for each positive X> 2. If 'X \2 (i.e., ,Zb 1), we obtain the same conclusion on using the second inequality in (4) and proceeding as before. We shall next show that N(X) = 0 for X> V8 (i.e., A> V2). For such a value of A we have from (6) that Z =1. The relation (5) then shows that Y= 1. Since X< Y+Z, we now have X= 1. Using relations (3) and (2), one obtains ;= 3, A=V\3, a=b=c=2. REMARKS. The remarks made at the beginning of this note show that N(1) = 5 and N(2) =1. Our theorem shows that N(3) = N(4) = * = 0. It would be interesting to consider a similar problem for a quadrilateral, and in general, a polygon of n sides (n> 2).

RESEARCH PROBLEMS EDITED By RICHARD GuY In this Department the Monthly presents easily stated research problems dealing with notions ordinarily encountered in undergraduate mathematics. Each problem should be accompanied by relevant references (if any are known to the author) and by a brief description of known partial results. Material should be sent to Richard Guy, Department of Mathematics, Statistics, and Computing Science, The University of Calgary, Calgary 44, Alberta, Canada.

HOW OFTEN DOES AN INTEGER OCCUR AS A BINOMIAL COEFFICIENT? DAVID SINGMASTER, Polytechnic of the South Bank, [Annotation 1] London

Let N(a) be the number of times a occurs as a binomial coefficient, (X). We have N(1) =oo, N(2) 1, N(3) =N(4) N(5) =2, N(6) =3, etc. Clearly, for a> 1, N(a) < oo. Below we establish that N(a) = O(log a). We conjecture that N(a) = 0(1), that is, that the number of solutions of () =a is bounded for a > 1. Erd6s, in a private communication, concurs in this conjecture and states that it must be very hard. In a later communication, he suggests trying to show N(a) = O(log log a).

If we let M(k) be the first integer a such that N(a) =-k, we have: M(1) =2, M(2) = 3, M(3) = 6, M(4) = 10, M(6) = 120. The next values would be interesting to know.

This content downloaded from 128.235.251.160 on Mon, 22 Dec 2014 21:33:41 PM All use subject to JSTOR Terms and Conditions

#### Page 2

386 R. A. DUKE [April

PROPOSITION. [Annotation 2] N(a) = O(log a).

Proof: Let b be the first b such that (2) > a. Now

is monotonically increasing in i and inj; hence

b+i+b+ ) b + b + 2b

Thus (+J) = a implies i < b or j < b. Again by monotonicity, for each value of i (orj),

has at most one solution. Hence N(a) < 2b. Now (>) _ 2", so we have

( b(b-1)

hence b ?<log2 a + 1, and N(a) ? 2 +2 log2 a = O(log [Annotation 3] a).

Added in [Annotation 4] Proof: I have recently found that M(8) = 3003 and this is the only solution to N(a) > 8 with a < 223. There are six solutions to N(a) = 6 with a < 223, namely: 120, 210, 1540, 7140, 11628, and 24310.

HOW IS A GRAPH'S BETTI NUMBER RELATED TO ITS GENUS?

R. A. DUKE, University of Washington

If a connected graph G has v vertices and e edges, the number 1 -v+e is called the (1-dimensional) Betti number of G, denoted by :l(G). This value, which is nonnegative for connected G, was one of the first numerical characteristics of a graph studied, having been introduced by von Staudt [11] and Kirchhoff [5]. The Betti number :l(G) is also the rank of the fundamental group of G (see [9], Ch. 6) and is related to the Euler characteristic of G, x(G), by the equation :3(G) = 1 -X(G). The genus of a graph is defined in terms of its embeddings in compact, closed, orientable 2-dimensional manifolds. Each such manifold can be formed by attaching an appropriate number of "handles" to a copy of the 2-sphere. For a manifold M, the number of handles required is called the genus of M, denoted by 'y(M), and is related to the Euler characteristic of M by the formula 2'y(M) = 2-x(M). Each graph can be embedded in some orientable 2-manifold by placing itsvertices on the 2-sphere and attaching one handle to accommodate each edge. In general, however, such a construction yields a manifold of unneces-

This content downloaded from 128.235.251.160 on Mon, 22 Dec 2014 21:33:41 PM

All use subject to JSTOR Terms and Conditions

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/how-often-does-an-integer-occur-as-a-binomial-coefficient. More annotated papers: https://fermatslibrary.com/llms.txt
