How $a+b$ can grow when $a!b! \mid n!$ Let $a,b,n$ be natural numbers such that $a!b! \mid n!$. I am looking for a (somehow best) upper bound of $a+b$ in terms of $n$ (for large values on $n$). For example it is clear to see that we must have $a+b \leq 2n$. But unfortunately I am looking for much smaller bound ! Any idea would be helpful.   
 A: FWIW here are the first examples of $a!b! \mid n!$ with $a+b-n = v$
for each $v=1,2,3,\ldots,14$:
 1 [1, 1, 1]
 2 [3, 5, 6]
 3 [6, 7, 10]
 4 [11, 29, 36]
 5 [14, 47, 56]
 6 [47, 59, 100]
 7 [59, 110, 162]
 8 [23, 241, 256]
 9 [31, 239, 261]
10 [187, 239, 416]
11 [447, 620, 1056]
12 [239, 1853, 2080]
13 [1439, 1775, 3201]
14 [1663, 2735, 4384]

This was computed with the following gp code that recursively
computes row $m=a+b=n+v$ of Pascal's triangle, reduces mod $m!/(m-v!)$,
and returns $(a,b,m)$ once ${m \choose a} \equiv 0$:
allocatemem(2^28)
{
M(v, P,Q) =
  m = v;  P = vector(v+1,i,binomial(v,i-1));
  while(1,
    m++;  P = concat(0,P) + concat(P,0);  Q = P % prod(i=0,v-1,m-i);
    for(a=1,m\2, if(Q[a+1]==0, return([a,m-a,m-v])))
  )
}
for(v=1,14,print(v,M(v)))

I actually asked for $v \leq 20$, but stopped at $14$ after
it took about 10 seconds to do each $v \leq 13$, 
then 20 seconds for $v=14$, and then no output for 15 minutes for $v=15$ 
$-$ apparently the binomial coefficients are getting too large 
even for reducing each one modulo $m!/(m-v)!$.  In any case this method
takes time at least $M^3$ to try all $m \leq M$;
it should take time only $M^{2+\epsilon}$ 
to check for each $a\leq m/2$ and $m \leq M$
the divisibility of $m \choose a$ by every prime factor of 
$m!/(m-v)!$, but that would take longer to code...
A: The product of $x$ consecutive numbers has $2$-adic valuation at least $x - \ln_2 x-1$, which means we can improve GH's explicit form of Seva's result to $a+b \leq n + \log_2 (n) + O( \log \log n)$. Improving the coefficient of $\log_2 n$ further seems to require at least a little bit of deep mathematics. I'll sketch out why.
First note that this bound is best possible if one relaxes the condition $a! b! | n!$ to $(a!)_2 + (b!)_2 \leq (n!)_2$, where $x_2$ is the $2$-adic valuation of $x$. This is because $n=2^k$, $a=k+1$, $b=2^k-1$ satisfies this weaker condition, and $a+b=n+\log_2 n$.
Thus to do better we need to include divisibility by other primes in our argument. If we just use a single prime $p$, running the same argument gives us the bound $a+b-n = 1 + p \log_p n $ or $a+b-n = 1 + (p-1) \log_p n + O(\log \log n)$. This bound is worse, and it is best possible $p$-adically.
So to do better we need to include multiple primes. For instance, we might use divisibility at both $2$ and $3$. But this runs into trouble when a power of $2$ and a power of $3$ are very close together. If $2^x$ and $3^y$ are in the interval $[n-c,n]$, then setting $a=x$ and $b=n-c-1$, so we need at least a little bit of separation between powers of $2$ and $3$ to have a hope of getting a better constant by this method. So perhaps Baker's Theorem needs to be used?
On the other hand, one could combine the valuations of all primes with some appropriate weight function $w_p$, relaxing the problem to the inequality $\sum_p (a!)_p w_p + \sum_p (b!)_p w_p \leq \sum_p (n!)_p w_p$. Clearly choosing $w_p= \ln p$ gives a very bad bound, but perhaps a slower-growing function could prove effective. Controlling this kind of sum seems like an analytic number theory question, although I don't have any rigorous argument that this impression is accurate.
A: Here are a few computed examples, but first comments which move things along, although not very far.
I'll write examples as $\frac{n!}{a!b!}$ with $a \ge b.$ We might define the virtue of such an example  to be $v=a+b-n.$ Then we know that $\frac{(k!)!}{(k!-1)!k!}$ has virtue $k-1.$
One can look the denominators (after reduction to lowest terms) of $\frac{n!}{a!(b+1)!},\frac{n!}{(a+1)!b!}$ and $\frac{(n-1)!}{a!b!}$ to see what primes it was which denied a slightly more virtuous example. My observation from small cases is that, perhaps unsurprisingly, is is frequently just $2$ or some few small primes.
An trivial yet helpful equivalent condition which keeps the numbers smaller is that $b!$ divide $(a+1)(a+2)\cdots(a+b-v).$ So we are looking for the product of relatively few consecutive integers to be a multiple of $b!$ 
I was excited by the fact that $7!=71^2-1=70\cdot 72$ giving virtue $4$ to $\frac{72!}{69!7!}$ which is ahead of $\frac{120!}{119!5!}.$ However the first examples with virtue $4$ are actually $\frac{36!}{23!17!}$ and $\frac{36!}{29!11!}.$ Observe that $\frac{35!}{23!17!},\frac{36!}{24!17!}$ and $\frac{36!}{23!18!}$ have denominators $4,8$ and $2$. The best examples seem to have $b$ much larger than $v.$
There are three more values of $n$ giving virtue $4$ before 


*

*$\frac{56!}{47!14!}$ , the first of $5$ values of $n$ giving virtue $5$ before:

*$\frac{100!}{59!47!}$ , the first of $10$ values of $n$ giving virtue $6$ before:

*$\frac{162!}{107!62!}$ and $\frac{162!}{110!59!}$, the first of $2$ values of $n$ giving virtue $7$ before:

*$\frac{256!}{142!122!},\frac{256!}{202!62!},\frac{256!}{239!25!}$ and $\frac{256!}{241!23!}$, the only  value of $n$ giving virtue $8$ before:

*$\frac{261!}{223!47!}$ and $\frac{261!}{239!31!}$ of virtue $9.$


Another example with virtue $9$ is $\frac{273!}{223!59!}.$ That is the only one for $n=273.$ I do not know if there are any other examples before the first of virtue $10.$
Note that $224=2^57$ and $240=2^43\ 5$ are just a bit too far for the denominator in more than one case.
Later
One might add that $225=15^2$ and $243=3^5$ along with $242=2\ 11^2$ are also potential obstacles in the denominator.
A: One has 
  $$ a+b < n+O(\log n), $$
which is best possible in view of $1!n!|n!$. For the proof, assuming that $a!b!|n!$ with $a+b>n$, consider the exponent of $2$ in the prime decomposition of the quotient $n!/(a!b!)$. This exponent is 
  $$ \sum_{1\le k\le\log_2(a+b)} \big(\lfloor n/2^k\rfloor-\lfloor a/2^k\rfloor-\lfloor b/2^k\rfloor \big) = \sigma_1-\sigma_2, $$
where
  $$ \sigma_1 = \sum_{1\le k\le\log_2(a+b)} \big(\lfloor(a+b)/2^k\rfloor-\lfloor a/2^k\rfloor-\lfloor b/2^k\rfloor \big) $$
and
  $$ \sigma_2 = \sum_{1\le k\le\log_2(a+b)} \big(\lfloor(a+b)/2^k\rfloor - \lfloor n/2^k\rfloor \big). $$
We thus have $\sigma_1\ge\sigma_2$. On the other hand, it is well known that $\sigma_1\le\log_2(a+b)$ (for, every summand in $\sigma_1$ is either $0$ or $1$). The sum $\sigma_2$ can be estimated by
  $$ \sigma_2 \ge \sum_{1\le k\le\log_2(a+b)} \big((a+b)/2^k - n/2^k -1 \big)
       \ge a+b-n - \log_2(a+b) - O(1). $$
As a result, we get
  $$ a+b-n \le O(\log_2(a+b)), $$
implying the assertion.
A: This is a small variation of Seva's argument yielding a slightly more explicit result. 
Assume that $a+b>n$ with $a!b!$ dividing $n!$. Then
$$ \prod_{n-a<m\leq b}m=\frac{b!}{(n-a)!} \ \ \text{divides}\ \  \frac{n!}{(n-a)!a!}= \binom{n}{a}. $$
Looking at the exponent of $2$ in the prime decomposition of the two sides, we infer (e.g. by Kummer's theorem)
$$ \frac{b-(n-a)-1}{2} \leq \log_2(n),$$
whence
$$ a+b-n \leq 1+2\log_2(n). $$
Of course the same result is trivial when $a+b\leq n$.
A: This is really a comment, but given all the interest in the question it seemed a good idea to write it as an answer.   Apparently what was discussed earlier (in the answers of Seva and GH from MO) is an old result of Erdos! The reference is Aufgabe 557, Elemente Math. (1968) 111-113, which may be found here: http://retro.seals.ch/digbib/view?rid=elemat-001:1968:23::117&id=browse&id2=browse4&id3= . I found this reference in an interesting paper of Erdos, Graham, Ruzsa and Strauss from 1975, which you can find here (see bottom of page 90): http://math.ucsd.edu/~ronspubs/75_03_prime_factors.pdf 
Erdos, Graham, Ruzsa and Strauss also comment that there is a constant $c>0$ such that for all $n$ except a set of density zero we have 
$$ 
\frac{(2n)!}{n!(n+[c\log n])!} \in {\Bbb N}.
$$ 
Thus the bound of $2n+O(\log n)$ is best possible. 
This is also in Erdos's exercise linked above. Note on the history:  Erdos proposed as an exercise to show the upper bound $a+b\le n+C\log n$ (part 1) and that this is best possible (part 2).  Part 1 was solved by P. Bundschuh  (same solution as in GH from MO's response).  The solution printed for Part 2 was that sent by the proposer Erdos.  
They also raise a "curious problem" in this paper:  Namely it is possible that $n!/(a!b!)$ is not an integer for $a+b \ge n+c\log n$ only because of small primes.  In other words for every $c$ it is asked whether there exists a $k$ such that for infinitely many (or even all sufficiently large $n$) there are suitable $a$ and $b$ with $a+b>n+c\log n$ and such that $n!/(a!b!)$ has no prime factor $>k$ in its denominator.  
