Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T11:52:59Z http://mathoverflow.net/feeds/question/116336 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/116336/combinatorial-interpretation-of-i-choose-n-where-i2-1 Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$ Richard Stanley 2012-12-14T01:43:49Z 2012-12-15T23:41:19Z <p>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)!$.</p> http://mathoverflow.net/questions/116336/combinatorial-interpretation-of-i-choose-n-where-i2-1/116346#116346 Answer by Eric Naslund for Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$ Eric Naslund 2012-12-14T04:14:07Z 2012-12-15T23:41:19Z <p><strong>Asymptotics:</strong> Lets look at the quantity </p> <p><code>$$S(n)=(-1)^{n}(n+1)\binom{i}{n+1}=i\prod_{k=1}^{n+1}\left(1-\frac{i}{k}\right).$$</code> 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.</p> <blockquote> <p><strong>Claim:</strong> We have that </p> <p>$$S(n)=\sqrt{\frac{\sinh{\pi}}{\pi}}e^{iC_{0}}e^{-i\log n}\left(1+O\left(\frac{1}{n}\right)\right),$$ where</p> <p>$$C_{0}=\frac{-\pi}{2}-1+\int_0^\infty \frac{\{x\}}{1+x^2}dx =\arg(\Gamma(i))\approx -1.872.$$ </p> </blockquote> <p>In particular, the angle moves around the circle like $\log n$. </p> <p><strong>Application to your question:</strong> The above claim shows that <code>$$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)$$</code> and <code>$$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).$$</code> </p> <p>In particular, the ratio $g_n/f_n$ can be made arbitrarily large or small.</p> <p><em>Proof of the claim:</em> We first note that the size is</p> <p>$$\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</p> <p>$$-\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right).$$ </p> <p>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 </p> <p>$$\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.$$</p> <p>Pulling out the main term with the identity $[x]=x-\{x\}$, the above equals </p> <p>$$\int_{0}^{n}\frac{x}{1+x^{2}}dx-\int_{0}^{n}\frac{\{x\}}{1+x^{2}}dx.$$</p> <p>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).$$</p> <p><strong>Acknowledgements:</strong> 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.</p> <p><strong>Edit:</strong> 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).$$</p> http://mathoverflow.net/questions/116336/combinatorial-interpretation-of-i-choose-n-where-i2-1/116422#116422 Answer by Noam D. Elkies for Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$ Noam D. Elkies 2012-12-15T02:14:01Z 2012-12-15T02:14:01Z <p>There is no need to reinvent the wheel by estimating <code>$\prod_{k&lt;n}(1+\frac1{k^2})$</code>. 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 <code> $$\phantom{*0000000000000000000} {w \choose n} = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) \frac{(-1)^n}{\Gamma(-w)} n^{-w-1} \phantom{0000000000000000000}(*)$$ </code> (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$.</p> <p>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).</p>