0
$\begingroup$

Define a (set-valued) function $ n \to \{\dfrac{n!}{k!(n-k)!k}:k=1,2,...n-1,n\}$. Now let $f$ be a function that counts the number of natural numbers in the set $\{\dfrac{n!}{k!(n-k)!k}:k=1,2,...n-1,n\}$.

A question is: Is $f(n)=1$ for only a finite number of values of $n$?

Here, we study, for each natural number $n$, a set $\{\dfrac{n!}{k!(n-k)!k}:k=1,2,...n-1,n\}$ and seek to determine is there a finite number of natural numbers $n$ for which only the first term is a natural number.

I expect a finite number of natural numbers for which $f(n)=1$ because it seems to me that, although there will be much cancellations in calculation of a number $\dfrac{n!}{k!(n-k)!}$, there should be enough richness in a structure of $\dfrac{n!}{k!(n-k)!}$ that allows $\dfrac{n!}{k!(n-k)!k}$ to be a natural number for some $k \in \{1,2,...,n\} \setminus \{1\}$

This question (almost in the same form) was also asked here on MSE about five hours ago, and, I must admit that I was, kind of, in a dilemma should I post it on MO or MSE, but since there were no serious progress there, I am also posting it here.

There, Woett gave three constructive comments, but we still do not have a solution.

He also did computational check and wrote, that, if he did no mistakes, the only $n \leq 5 \cdot 10^5$ for which $f(n)=1$ are $1, 2, 3, 6, 7, 14, 15, 22, 23, 95$, which corresponds nicely with intuition of mine, that is, that there should be a finite number of such an $n$.

Steven Stadnicki gave OEIS link that gives values of $f(n)$ for $n=1,2,...,99$, here it is: https://oeis.org/A081372

$\endgroup$
2
  • 4
    $\begingroup$ You should wait at least 24 hours before considering cross-posting. 5 hours without progress is not unusual, given that 1/3 of the world has slept through that time! $\endgroup$
    – Wojowu
    Sep 14, 2018 at 20:58
  • $\begingroup$ Indeed. Five hours... Maths is rarely about instant gratification. $\endgroup$ Sep 14, 2018 at 20:59

1 Answer 1

2
$\begingroup$

First of all, let $p$ and $q$ be some prime numbers with $q/2<p<q$. Then $pq\mid\binom{n}{pq}$ if

$$n\equiv a \pmod {p^2}$$

and

$$n\equiv b \pmod {q^2}$$

with some $a,b>0$ and $a<p(q-p)$, $b<pq$. To prove this, apply Lucas's theorem on binomial coefficients and also note that $pq$ is a two-digit number $\overline{p0}$ in base $q$ and a three-digit number $\overline{1(q-p)0}$ in base $p$. Now lets assume $n$ is large enough.

It is a well-known fact that the interval $(x,x+x^{2/3})$ contains at least one prime for $x$ sufficiently large. Now let us choose $q$ to lie in the interval $(\sqrt{n}-n^{3/8},\sqrt{n}-n^{0.35})$ (which is clearly possible for $n$ large enough) and $p$ to lie in the interval $(q/2,\sqrt{n}/2)$.

Then we have the following:

$$q=\sqrt{n}-A$$

with $0<A<n^{3/8}$. Therefore,

$$q^2=n-2A\sqrt{n}+A^2,$$

so $0<n-q^2<2n^{7/8}=o(n)=o(pq)$, which is required. And we also have

$$p=\sqrt{n}/2-B$$

with $0<B<n^{0.35}$, therefore

$$0<n-4p^2=O(n^{0.85})=o(n)=o((q-p)p),$$

which is required. So, for $n$ large enough one can find some $k$ around $n/2$ that satisfies your condition, so $f(n)>1$ (and in fact even grows with $n$).

$\endgroup$
6
  • $\begingroup$ So, basically we just choose $p$ and $q$ to be primes with $q/2<p<q$ and both $q$ and $2p$ rather close to $\sqrt{n}$. $\endgroup$ Sep 15, 2018 at 0:19
  • $\begingroup$ In fact, I think one can use this sort of the argument (even without theorems on primes in short intervals: just classical formulas for $\pi(x)$ with nice enough remainder terms) to show that $f(n) \gg \frac{n}{\log^2 n}$. $\endgroup$ Sep 15, 2018 at 0:27
  • $\begingroup$ I am thinking about some purely combinatorial/number-theoretic approach without any use of analysis. $\endgroup$
    – Right
    Sep 15, 2018 at 0:40
  • $\begingroup$ That is, with minimal amount of analysis. $\endgroup$
    – Right
    Sep 15, 2018 at 0:46
  • 1
    $\begingroup$ I think that all the analytic results that I used can be replaced by results of the form "there are primes in $((1-\varepsilon)x,(1+\varepsilon)x)$" for some small enough $\varepsilon$. And these facts are known to have a purely combinatorial proof. $\endgroup$ Sep 15, 2018 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.