2
$\begingroup$

I am trying to compute the best growth rate for the following sequence $$ a_n=\prod_{k=0}^{n-1}\frac{(3k+1)!}{(n+k)!} $$

This sequence counts the number of $n\times n$ alternating sign matrices: http://en.wikipedia.org/wiki/Alternating_sign_matrix

It also counts the number of descending plane partitions of order $n$.

I am looking for an asymptotic growth rate (even just using $\Theta$ notation).

I found the following statement about logarithmic growth (http://rsta.royalsocietypublishing.org/content/364/1849/3183.full.pdf+html): $$ \log a_n\sim \sqrt{\frac{27}{16}}n^2 $$

However, my limited knowledge of this kind of thing doesn't help me get a precise growth rate for the whole function.

EDIT: To clarify: I am not looking for an explanation of how to obtain the logarithmic growth rate. I only included this to show what I have been able to find towards answering the question, which is the following. What is a "simple" function that represents the asymptotic growth of $a_n$? Alternatively, I would be happy with a "simple" function representing the $\Theta$ class of $a_n$.

$\endgroup$
  • $\begingroup$ So what you already have got does not solve the problem? $\endgroup$ – Mhenni Benghorbal Aug 14 '14 at 19:43
  • $\begingroup$ No. For example let $a_n=2^{n^2}$ and $b_n=2^{n^2-n}$. Then $\log a_n\sim\log b_n$, even though $a_n$ and $b_n$ are not even in the same $\Theta$ class. $\endgroup$ – Gabe Conant Aug 14 '14 at 19:59
3
$\begingroup$

$$\log a_n = \sum_{k=0}^{n-1} \left(\log((3k+1)!) - \log((n+k)!\right)$$

Next use Stirling's approximation. Note e.g. that $$\sum_{k=1}^n k \log(k) \approx \int_1^n k \log(k)\; dk \approx \dfrac{n^2 \log(n)}{2} - \dfrac{n^2}{4}$$

EDIT: Ah, the Robbins numbers: OEIS sequence A005130. It seems (R.W. Gosper's approximation) $$ a_n \sim \dfrac{2^{5/12-2n^2}\; 3^{-7/36+3 n^2/2} \exp(\zeta(1, -1)/3))\;\pi^{1/3}} {n^{5/36}\; \Gamma(1/3)^{2/3}}$$

$\endgroup$
  • $\begingroup$ Could you elaborate a little more? Right now I don't understand how your answer gives more than only a justification for the logarithmic growth statement from the paper I linked. $\endgroup$ – Gabe Conant Aug 14 '14 at 20:52
1
$\begingroup$

Here are some possible steps.

Let $n$ be a positive integer. The functions $t \mapsto \log\Gamma (3t-1) $ and $t \mapsto \log\Gamma (n+t) $ are increasing for the interval $[1, \infty)$, so by summing areas of rectangles under and over the curves, you may easily obtain $$ \begin{align} & \int_{1}^{n} \log\Gamma (3t-1) \mathrm{d}t \leq \sum_{k=0}^{n-1} \log((3k+1)!) \leq \int_{1}^{n+1} \log\Gamma (3t-1) \mathrm{d}t, \tag 1\\ & \int_{1}^{n+1} \log\Gamma (n+t) \mathrm{d}t - \log\left( (2n)!/n!\right) \leq \sum_{k=0}^{n-1} \log((n+k)!) \leq \int_{1}^{n+1} \log\Gamma (n+t) \mathrm{d}t. \tag 2 \end{align} $$ Now, using the fact that $$ \int_{0}^{z} \log\Gamma (t) \:\mathrm{d}t =\frac{z(1-z)}{2}+\frac{z}{2}\log(2\pi)-(1-z)\log\Gamma(z) -\log G(z) \tag 3 $$ where $G$ is the Barnes' G-function verifying, as $z \rightarrow +\infty$, $$ \log G(z+1) \! = \! \frac{z^2}{4} +z\log\Gamma(z+1)\!-\!\left(z(z+1)/2+1/12\right)\log(z)-\log A \!+\! \mathcal{O}\!\left(\frac{1}{z^2}\!\right) \tag 4 $$ and recalling Stirling's approximation $$ \log\Gamma(z) = \! \left(z-1/2\right)\log(z)-z+\frac{1}{2}\log(2\pi) +\frac{1}{12z}+\mathcal{O}\!\left(\frac{1}{z^2}\!\right) \tag 5 $$ leads to the expected result, $A$ denoting the Glaisher-Kinkelin constant.

Without using $(1)$ and $(2)$, we may handle discrete sums via integrals by the Euler-MacLaurin summation formula: $$ \sum_{k \mathop = 0}^{n-1} f \left({k}\right) = \!\int_0^{n-1} \!\!f \left({x}\right) \mathrm dx \!+\! \frac{f(n-1)+f(0)}{2}- \!\frac{f'(n-1)-f'(0)}{12}+\!\frac{1}{2}\int_0^{n-1}\!\!f''(x)B_2(\left\{x\right\})\mathrm dx. $$ Here $a_n=\prod_{k=0}^{n-1}\frac{(3k+1)!}{(n+k)!}$, thus we may apply the previous formula to $$ \log a_n = \sum_{k=0}^{n-1} \log((3k+1)!) -\sum_{k=0}^{n-1} \log((n+k)!) = \sum_{k=0}^{n-1} f(k) $$ and use $(3), (4), (5)$. These are straightforward but somewhat lengthy calculations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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