# Growth Rate of Alternating Sign Matrices

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

• So what you already have got does not solve the problem? – Mhenni Benghorbal Aug 14 '14 at 19:43
• 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. – Gabe Conant Aug 14 '14 at 19:59

$$\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}}$$

• 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. – Gabe Conant Aug 14 '14 at 20:52

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.