# Number of tuples satisfying the following condition

I try to find an upper estimate of the number of integer tuples $(i_1,\ldots,i_M)$ such that $i_1!\cdots i_M!\leq s$ for a given real number $s$. I'm especially interested in asymptotics of this number for $M\rightarrow\infty$. Are there any well known results?

-
I would expect you can get a fairly good asymptotic passing to the logarithms and using the Stirling formula in the form $\log n! = n\log n - n + \frac12\log n + C + O(1/n)$. –  Seva Oct 18 '11 at 15:33
@Seva: But then you end up counting the tuples satisfying something like $i_1\log i_1+\ldots+i_M\log i_M\leq\log s$. I suspect this isn't much easier. –  phlipsy Oct 18 '11 at 15:37
Well, this should be about the volume of the $m$-dimensional body bouned by the hyperplanes $x_i=1$ and the surface $\sum x_i\log x_i=\log s$, which is just the appropriate integral. However, computing / estimating this integral can be messy, and for $M$ growing, the influence of the boundary can become critical - you never know without getting your hands durty. –  Seva Oct 18 '11 at 15:48
Have you tried setting up some recursions, say defining d_M(k) to be the number of ways k can be written as k=i1!...iM!? As well, is the problem even tractable without factorials? There are partition functions for ordered factorizations such as this: mathworld.wolfram.com/OrderedFactorization.html but you would have to modify them to only go up to M and include the degeneracy of tacking on 1!. –  Alex R. Oct 18 '11 at 20:33
@Seva: Actually I already tried but as a matter of fact this off cut from the border became critical. Although I got an upper and a lower bound for the number of tuples they were too rough. –  phlipsy Oct 18 '11 at 20:36

First I will assume that you don't count $0!$ and $1!$ as different.

If $s$ is a fixed number, and $M\to\infty$, the asymptotic number of solutions is $$\binom{M}{\lfloor \log_2 s\rfloor}.$$

Proof: Note that at most $\lfloor \log_2 s\rfloor$ of the $i_j$ values can be 2 or more. The rest, which is most of them, must be 1. Let $m(\ell)$ be the number of distinct products $i_1!\cdots i_\ell!\le s$ with each factor at least 2. Then the total number of solutions is $$\sum_{\ell=0}^{\lfloor \log_2 s\rfloor} \binom{M}{\ell} m(\ell).$$ Since $s$ is bounded, so $m(\ell)$ is uniformly bounded over all $\ell$, so the sum is asymptotically determined by its last term $\ell=\lfloor \log_2 s\rfloor$. Since $m(\lfloor \log_2 s\rfloor)=1$ (the only case is a lot of $2!$s), the claim follows.

If you want $0!$ and $1!$ to be counted as different, there are 2 possibilities for each value not at least 2. The same argument gives the asymptotic value as $$2^{M-\lfloor \log_2 s\rfloor}\binom{M}{\lfloor \log_2 s\rfloor}.$$

In both cases the relative error is $O(1/M)$ for fixed $s$. The question becomes more interesting if $s$ is not fixed but increases with $M$.

-
That's what you mean, don't you: The sum is asymptotically determined by its last term $\ell=\lceil\log_2s\rceil$ because if $M\rightarrow\infty$ soon or later $\binom{M}{\lceil\log_2s\rceil}$ will dominate all other terms. –  phlipsy Oct 19 '11 at 13:49
And I actually meant $\lfloor\log_2s\rfloor$ instead of $\lceil\log_2s\rceil$ –  phlipsy Oct 19 '11 at 13:50
Yes, the exact value is a polynomial in $M$ of degree $\lfloor\log_2 s\rfloor$, so it is dominated by its leading term. For fixed $s$, you can replace $\binom{M}{\lfloor\log_2 s\rfloor}$ by $M^{\lfloor\log_2 s\rfloor}/(\lfloor\log_2 s\rfloor)!$ if you like, as they are asymptotically the same. –  Brendan McKay Oct 20 '11 at 8:50
If you just care about asymptotics, then you can use central limit theorem or LDP techniques to get an exponential estimate. Here is how: let $x_1, \ldots, x_M$ be iid uniform random variables in $[0,\log s]$, and consider the random sum
$$\sum_{i=1}^M x_i (-1 + \log x_i) + \frac{1}{2} \log 2\pi x_i$$,
which should converge to some Gaussian with nonzero mean and some variance. You basically want to ask what is the probability that this is less than $\log s$. Since then you can just multiply the probability by $(\log s)^M$ to get an estimate of the form $\exp(f(M,s))$. I am pretty sure if you use Cramer's theorem in Large deviations principle you can compute the tail probability of the sum above. In fact there is a version of Stirling I believe that is a strict upper bound, i.e., something like $n! \le c\exp (n (\log n - 1) + \frac{1}{2} \log n)$ for some universal $c$ , which shouldn't matter much. If you want I can try to compute for you.
Does your approach include the fact that these $i_k$ are integers? –  phlipsy Oct 19 '11 at 7:14
Oh and just another question, sorry... Why do you think the above sum converges to a certain Gaussian random variable? We simply add the random variables and don't scale the sum with something depending on $M$. Or do you mean the mean an variance of this Gaussian depends on $M$? –  phlipsy Oct 19 '11 at 7:46
Yes $i_k$ being integer is not so important here, because fractional parts won't contribute too much to the final asymptotics. By converging to Gaussian I really mean after rescaling. But as far as asymptotics is concerned, you are really interested in the rescaled quantity. My approach would take care of the cases when either M or S (or both) are approaching infinity. –  John Jiang Oct 19 '11 at 17:09