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

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

-
As a prelude to this, it might help to consider i as an indeterminate, and look at the coefficients of the polynomial which would be the numerator of the expression. Gerhard "That Might Provoke Combinatorial Insights" Paseman, 2012.12.13 –  Gerhard Paseman Dec 14 '12 at 2:07
Thanks, Chandan, I have fixed the typo. If we consider $i$ as an indeterminate, then the coefficients are the Stirling numbers of the first kind, explaining the connection with these numbers. –  Richard Stanley Dec 14 '12 at 2:10
Thank you for not asserting that "This begs the question:" which is too useful a phrase in mathematical discussion to sacrifice to common usage. cafepress.com/begthequestion.38045148 –  Allen Knutson Dec 14 '12 at 2:51
The asymptotics can be obtained from the complex Stirling's formula. In particular, the $f_n$ and $g_n$ will usually alternate in sign, because ${i \choose n} \left/ {i \choose n-1} \right.$ is $\frac{i+1}{n} - 1$ which is nearly $-1$, but there'll be infinitely many exceptions (the next two are $g_{82},g_{83}>0$ and $f_{396},f_{397}>0$). I don't know of combinatorial interpretations, but do recognize that the identity $i(i-1)(i-2)(i-3) = -10$ is related with the identity $\tan^{-1}\frac12 + \tan^{-1}\frac13 = \frac\pi4$ that yields the earliest polynomial-time algorithm for computing $\pi$. –  Noam D. Elkies Dec 14 '12 at 3:44
Not really relevant to this question, but if $a$ and $b$ are integers and $\binom{a+bi}{k}= c+di$, where $c$ and $d$ are rational, then every prime dividing the denominator of $c$ or $d$ is congruent to 2 or 3 modulo 4. –  Ira Gessel Dec 14 '12 at 14:58

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

-
A closed form for $C_1 = 1.91731...$ is $1/|\Gamma(i)| = \sqrt{\frac{\textstyle\sinh\pi}{\textstyle\pi}}$. –  Noam D. Elkies Dec 14 '12 at 6:12
@Noam D. Elkies: Thank you for pointing this out. I have updated my answer and added a proof. –  Eric Naslund Dec 14 '12 at 6:56
@S. Carnahan: I don't believe so. –  Eric Naslund Dec 14 '12 at 9:43
Thanks for the edit and acknowledgement. One correction: it's the product over $k\geq 1$ of $\sqrt{1+\frac1{k^2}}$, not of $1+\frac1{k^2}$, that's equal to $1/|\Gamma(i)| = \sqrt{\frac{\textstyle\sinh\pi}{\textstyle\pi}}$. –  Noam D. Elkies Dec 14 '12 at 16:38
Sorry, my mistake (about the $n!$). Regarding your flag, I do not know why your post became Community Wiki. According to the documentation, the only way it could happen on the 8th (rather than the 10th) edit is if you clicked the Community Wiki check box. –  S. Carnahan Dec 15 '12 at 17:50

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

-
Thanks for sharing this answer. It is much cleaner, and it made me realize I previously have an error in the calculation of the constant $C_0$. (Also, it certainly looks much nicer to write $S(n)=\frac{1}{\Gamma(-i)}n^{−i}\left(1+O\left(\frac{1}{n}\right)\right).$) –  Eric Naslund Dec 15 '12 at 19:33
So ... it seems Stirling's approximation has a relation to Stirling numbers (of the first kind) ... –  Gerald Edgar Dec 20 '13 at 22:33