Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$ - MathOverflow

Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$

2012-12-14T01:43:49Z

At MIT all departments have numbers, and math is 18. Last year MIT math majors produced a tee shirt that said ${i\choose 18}$ ("I choose 18") on the front, and on the back $$ \frac{34376687+1499084559i}{14485008384}. $$ With the more natural denominator $18!$ this is $$ \frac{15194495654000+662595375078000i}{18!}. $$ This suggests the question: for any $n\geq 1$ find a "nice" combinatorial interpretation of the real and imaginary parts of $i(i-1)(i-2)\cdots (i-n+1)=f_n+ig_n$. It is easy to express $f_n$ and $g_n$ as certain alternating sums of Stirling numbers of the first kind, but I don't consider this "nice." The $g_n$'s seem to alternate in sign beginning with $n=5$. The $f_n$'s alternate in sign up to $n=17$ and then seem to alternate in sign beginning with $n=18$. It is curious that $i(i-1)(i-2)(i-3)=-10$, a real number. One could ask the same question with $i$ replaced by any Gaussian integer $a+bi$. One can also ask about the asymptotic rate of growth of $f_n$ and $g_n$. Clearly $f_n^2+g_n^2\sim C\cdot (n-1)!^2$, so one would expect $f_n$ and $g_n$ to be roughly of the size of $(n-1)!$.

Answer by Eric Naslund for Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$

2012-12-14T04:14:07Z

Asymptotics: Lets look at the quantity

$$S(n)=(-1)^{n}(n+1)\binom{i}{n+1}=i\prod_{k=1}^{n+1}\left(1-\frac{i}{k}\right).$$ It's just your binomial coefficient above with the $(-1)^{n+1}$ factored in, and an extra $n+1$ so it factors nicely as a product.

Claim: We have that

$$S(n)=\sqrt{\frac{\sinh{\pi}}{\pi}}e^{iC_{0}}e^{-i\log n}\left(1+O\left(\frac{1}{n}\right)\right),$$ where

$$C_{0}=\frac{-\pi}{2}-1+\int_0^\infty \frac{\{x\}}{1+x^2}dx =\arg(\Gamma(i))\approx -1.872.$$

In particular, the angle moves around the circle like $\log n$.

Application to your question: The above claim shows that $$f_{n+1} = (-1)^{n+1} n! \sqrt{\frac{\sinh{\pi}}{\pi}}\cos(-\log n+C_0)\left(1+O\left(\frac{1}{n}\right)\right)$$ and $$g_{n+1} \sim (-1)^{n+1} n! \sqrt{\frac{\sinh{\pi}}{\pi}} \sin(-\log n+C_0)\left(1+O\left(\frac{1}{n}\right)\right).$$

In particular, the ratio $g_n/f_n$ can be made arbitrarily large or small.

Proof of the claim: We first note that the size is

$$\sqrt{\prod_{k=1}^{n}\left(1+\frac{1}{k^{2}}\right)}=\sqrt{\prod_{k=1}^{\infty}\left(1+\frac{1}{k^{2}}\right)}+O\left(\frac{1}{n}\right).$$ To evaluate this product, recall the Weierstrass product for the Gamma function $$\left(\Gamma(z)\right)^{-1}=ze^{\gamma z}\prod_{k=1}^{\infty}\left(1+\frac{z}{k^{2}}\right)e^{-\frac{z}{r}}.$$ From this it follows that $$\frac{1}{|\Gamma(i)|^{2}}=\frac{1}{\Gamma(i)\Gamma(-i)}=\prod_{k=1}^{\infty}\left(1+\frac{1}{k^{2}}\right).$$ Using the identity $$\Gamma(x)\Gamma(-x)=-\frac{\pi}{x\sin\left(\pi x\right)},$$ we now have that $$\frac{1}{\Gamma(i)\Gamma(-i)}=\frac{-i\sin(i\pi)}{\pi}=\frac{\sinh(\pi)}{\pi},$$ which gives rise to the $\sqrt{\frac{\sinh(\pi)}{\pi}}$ term. Moving on to the evaluation of the angle, by looking at each triangle, and noting that the argument is additive when multiplied, we get that the argument equals

$$-\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right).$$

The negative sign arises since we are working in the fourth quadrant. By looking at the Taylor series for $\tan^{-1}$ we see that the above is $\log n+O(1)$, however, I would like to compute this argument more precisely, and obtain the constant. Lets compare our $\tan^{-1}$ series to the harmonic series. Rewriting things in terms of a Riemann Stieltjes integral, and using summation by parts, we have that

$$\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right)=\int_{0}^{n}\tan^{-1}\left(\frac{1}{x}\right)d\left[x\right]=[n]\tan^{-1}(1/n)\int_{0}^{n}\frac{\left[x\right]}{1+x^{2}}dx. $$

Pulling out the main term with the identity $[x]=x-\{x\}$, the above equals

$$\int_{0}^{n}\frac{x}{1+x^{2}}dx-\int_{0}^{n}\frac{\{x\}}{1+x^{2}}dx.$$

Since the first integral evaluates to $\frac{1}{2}\log(1+x^2)$, we have that $$\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right)=\log n +1-\int_0^\infty \frac{\{x\}}{1+x^2}dx +O\left(\frac{1}{n}\right).$$

Acknowledgements: I would like to thank Noam Elkies for pointing out that $$\prod_{k=1}^\infty \sqrt{1+\frac{1}{k^2}}=\frac{1}{|\Gamma(i)|}=\sqrt{\frac{\sinh(\pi)}{\pi}}$$ in the comments.

Edit: Fixed the constants appearing. Interestingly $$\Gamma(i)=\sqrt{\frac{\pi}{\sinh{\pi}}}\exp\left(i\left(\frac{-\pi}{2}-1+\int_0^\infty \frac{\{x\}}{1+x^2}dx \right)\right).$$

Answer by Noam D. Elkies for Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$

2012-12-15T02:14:01Z

There is no need to reinvent the wheel by estimating $\prod_{k<n}(1+\frac1{k^2})$ . The asymptotic formula for $f_n + i g_n$ follows readily from Stirling's approximation (as I already noted in my comment to the original question), and indeed the same is true for the asymptotics as $n \rightarrow \infty$ of $w \choose n$ for any $w \in {\bf C}$; the answer is simply $$ \phantom{*0000000000000000000} {w \choose n} = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) \frac{(-1)^n}{\Gamma(-w)} n^{-w-1} \phantom{0000000000000000000}(*) $$ (and the $O(1/n)$ can be refined to an asymptotic series in powers of $1/n$). Note that this gives zero precisely for the values $w=0,1,2,3,\ldots$ for which $-w$ is a pole of $\Gamma$, which are also the $w$ for which ${w \choose n} = 0$ for sufficiently large $n$. For $w=i$, we recover the observed behavior: $\Gamma(i)$ is a complex number of absolute value $(\pi / \sinh \pi)^{1/2}$ [in general $$|\Gamma(it)| = (\Gamma(it)\Gamma(-it))^{-1/2} = \left(\frac \pi {t \phantom. \sinh \pi t} \right)^{1/2} $$ for real $t \neq 0$], and $n^{-w-1}$ is a complex number of absolute value $1/n$ that goes once around the origin when $n$ increases by a factor $e^{2\pi}$. Thus each of $\lbrace f_n \rbrace$ and $\lbrace g_n \rbrace$ alternates in sign outside an infinite sequence of exceptions that's asymptotically a geometric sequence with common ratio $e^\pi$.

To prove (*), write $$ {w \choose n} = \frac{(-1)^n}{n!} \prod_{k=0}^{n-1} (k-w) = \frac{(-1)^n}{n!} \frac{\Gamma(n-w)}{\Gamma(-w)} = \frac{(-1)^n}{n\Gamma(-w)} \frac{\Gamma(n-w)}{\Gamma(n)}. $$ Now we understand $(-1)^n/n$, and the factor $1 / \Gamma(-w)$ is constant, so we're left with $\Gamma(n-w) / \Gamma(n)$. We apply the following form of Stirling's formula: there exists a constant $\varpi>0$ (known to equal $2\pi$, but we shall not need this) such that $$ \Gamma(z) = \bigl(1 + O(|z|^{-1}\bigr) z^z e^{-z} \sqrt{\varpi/z} $$ holds as $|z| \rightarrow \infty$ in the right half-plane, where $z^z = \exp (z \log z)$ and $\sqrt{\varpi/z}$ are defined using the principal branches of $\log z$ and $\sqrt z$. This gives $$ \frac{\Gamma(n-w)}{\Gamma(n)} = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) \frac{(n-w)^{n-w} e^{-(n-w)} (\varpi/(n-w))^{1/2}} {n^n e^{-n} (\varpi/n)^{1/2}} $$ $$ = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) \frac{(n-w)^{n-w}}{n^n} e^w \left(1-\frac{w}{n}\right)^{-1/2}. $$ Now the last factor is $1 + O(1/n)$; the factor $e^w$ is constant; and $$ (n-w)^{n-w} = (n-w)^{-w} (n-w)^n = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) n^{-w} (n-w)^n. $$ So we're left with $$ \frac{\Gamma(n-w)}{\Gamma(n)} = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) n^{-w} e^{-w} \left(1 - \frac{w}{n}\right)^n = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) n^{-w}. $$ This completes the proof of (*) (and the cancellation in the last step leads me to suspect that even this use of Stirling is more complicated than necessary).