4

1

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?

flag
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 2011 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 2011 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 2011 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 2011 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 2011 at 20:36

2 Answers

5

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$.

link|flag
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 2011 at 13:49
And I actually meant $\lfloor\log_2s\rfloor$ instead of $\lceil\log_2s\rceil$ – phlipsy Oct 19 2011 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 2011 at 8:50
0

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.

link|flag
Does your approach include the fact that these $i_k$ are integers? – phlipsy Oct 19 2011 at 7:14
But anyway this approach sounds very appealing to me since it seems to respect the fact that I'm only interested in asymptotics. So it really boils down to the question in my preceding comment. – phlipsy Oct 19 2011 at 7:41
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 2011 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 2011 at 17:09

Your Answer

Get an OpenID
or

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