Number of different ways to represent a positive integer as a binomial coefficient

binomial-coefficientsdiophantine equationselementary-number-theory

For each positive integer $x$, let $f(x)$ be the number of different ways that $x$ can be expressed in the form $x={\large{\binom{n}{k}}}$, where $n,k$ are integers with $2 \le k \le {\large{\frac{n}{2}}}$.

For each positive integer $m$, let $X_m = \{x\mid f(x) \ge m\}$.

A restated version of a recent question

IS IT POSSIBLE TO REPRESENT EVERY POSITIVE INTEGER AS NcR(N CHOOSE R) OTHER THAN THE TRIVIAL FORM "N choose N-1""

asks whether every integer greater than $1$ is in $X_1$.

The OP provided no context, so predictably, the question was put on hold, and most likely, the question will soon be closed, and eventually deleted.

It's easily shown that for fixed $n$, the values of the binomial coefficients ${\large{\binom{n}{k}}}$ are strictly increasing for $2 \le k \le {\large{\frac{n}{2}}}$.

It then follows easily that the least element of $X_1$ is ${\large{\binom{4}{2}}}=6$, which resolves the OP's question with an answer of "no".

In the comments to the linked question, JMoravitz provides an argument (which could have been an answer), showing that no primes are in $X_1$.

A quick program to get the initial elements of $X_1$ yields the values
$$6, 10, 15, 20, 21, 28, 35, 36, 45, 55, 56, 66, 70, 78, 84, 91$$
which matches the OEIS sequence

https://oeis.org/A006987

But some questions arise . . .

Question $(1)$:$\;$Is $X_2$ infinite?

I can answer this one, but not the others, at least not yet.

For question $(1)$, the answer is "yes".

Claim:

If $n,k$ are integers with $2 \le k \le {\large{\frac{n}{2}}}$, the equation
$$\binom{n}{k}=\binom{n+1}{k-1}$$
holds if and only if $5n^2+12n+8$ is a perfect square and
$$k=\frac{3n+4-\sqrt{5n^2+12n+8}}{2}$$

Proof:

The equation
$$\binom{n}{k}=\binom{n+1}{k-1}$$
reduces to the quadratic equation
$$k^2-(3n+4)k+(n^2+3n+2)=0$$
hence, the quadratic formula (together with constraint $2 \le k \le {\large{\frac{n}{2}}}$) clinches the claim.

But the diophantine equation $5n^2+12n+8 = h^2$ is a Pell-type equation with infinitely many solutions in positive integers $n,h$, hence the answer to question $(1)$ is "yes".

What about the elements of $X_2$ other than those determined as described above?

More precisely, let $W_2$ be the set of integers $x$ which can be expressed in the form ${\large{\binom{n}{k}}}$, where $n$ is a positive integer such that $5n^2+12n+8$ is a perfect square, and
$$k=\frac{3n+4-\sqrt{5n^2+12n+8}}{2}$$
Question $(2)$:$\;$Is $X_2{\setminus}W_2$ infinite?

Some data . . .

Here are the $5$ smallest elements of $W_2$:
\begin{align*}
{\small{\bullet}}\;&{\small{\binom{14}{6}}}={\small{\binom{15}{5}}}\\[4pt]
{\small{\bullet}}\;&{\small{\binom{103}{40}}}={\small{\binom{104}{39}}}\\[4pt]
{\small{\bullet}}\;&{\small{\binom{713}{273}}}={\small{\binom{714}{272}}}\\[4pt]
{\small{\bullet}}\;&{\small{\binom{4894}{1870}}}={\small{\binom{4895}{1869}}}\\[4pt]
{\small{\bullet}}\;&{\small{\binom{33551}{12816}}}={\small{\binom{33552}{12815}}}\\[4pt]
\end{align*}
Here are the elements of $X_2{\setminus}W_2$ that I've found so far:
\begin{align*}
{\small{\bullet}}\;&{\small{\binom{16}{2}}}={\small{\binom{10}{3}}}\\[4pt]
{\small{\bullet}}\;&{\small{\binom{21}{2}}}={\small{\binom{10}{4}}}\\[4pt]
{\small{\bullet}}\;&{\small{\binom{56}{2}}}={\small{\binom{22}{3}}}\\[4pt]
{\small{\bullet}}\;&{\small{\binom{120}{2}}}={\small{\binom{36}{3}}}\\[4pt]
{\small{\bullet}}\;&{\small{\binom{153}{2}}}={\small{\binom{19}{5}}}\\[4pt]
{\small{\bullet}}\;&{\small{\binom{221}{2}}}={\small{\binom{17}{8}}}\\[4pt]
\end{align*}
I don't know if there are any others.

Finally, what about $X_3$?

Note that $X_3$ has at least one element, since
$${\small{\binom{14}{6}}}={\small{\binom{15}{5}}}={\small{\binom{78}{2}}}$$
Question $(3)$:$\;$Is $X_3$ infinite?

Best Answer

OEIS entry A003015 lists the numbers that occur $5$ or more times in Pascal's triangle. It refers to Aart Blokhuis, Andries Brouwer, Benne de Weger, Binomial collisions and near collisions, INTEGERS, Volume $17$, Article A64, $2017$: “Blokhuis et al. show that there are no other solutions less than $10^{60}$, nor within the first $10^6$ rows of Pascal's triangle other than those given by the parametric solution mentioned above.” The paper expresses your infinite family in terms of Fibonacci numbers, conjectures that there are no collisions other than the ones you found, and discusses the state of this conjecture.

Related Question