Product of all binomial coefficients

Question

I was writing a research paper in Computer Science. I had to provide an upper bound for the number of steps of the algorithm I had found with my colleagues; the nature of the algorithm is totally irrelevant.

I considered the worst case scenario of my algorithm, and I started calculating the number of steps. I ended up with a big mess of binomial coefficients, but carefully, step after step, everything simplified down to just the following product: $$ \prod _{j = 0}^N {}\binom{N}{j}.$$ Initially, I assumed there was no better form for this product. In fact, there are several identities about binomial coefficients, but they all involve sums and not products. Nonetheless, I tried out of curiosity to read the Wikipedia page about Binomial coefficients. To my greatest surprise, there was a section exactly about the formula I sought. Namely, Wikipedia claims the following identity is true: $$ \prod _{j = 0}^N {}\binom{N}{j} = \prod_{k = 1}^N k^{2k - N -1}.$$

I couldn't believe my own eyes. This is precisely the formula I needed, and I had no idea it existed!

However, the Wikipedia page just claims its correctness, but doesn't add any citation. If I have to use this formula in the proof of the paper, I really need to know where it comes from. I might as well just try to prove it on my own, but I am afraid that will not be a solution: the editors have given us a very strict page limit, and there is no way we'll be able to stay within that limit if we add this proof as well. Similarly, I can't use an unproven formula in a paper. I really need to find a reference for this fact in a textbook or in a peer-reviewed article, and cite it in the paper.

I tried looking on the internet, but I couldn't find anything. Has anyone seen this before? Is this a well-known fact I just missed?

Thanks in advance.

Answer 1

The formula is rather trivial to deserve a reference. Factoring $\binom{N}j = \frac{1\cdot 2\cdots N}{(1\cdot 2\cdots j)\cdot(1\cdot 2\cdots (N-j))}$, we note that each $k\in [N]$ appears as a factor $N+1$ times in the numerator of the expansion (without cancelling) of $\prod_{j=0}^N \binom{N}j$, and $2(N-k+1)$ times in its denominator. Hence, $$\prod_{j=0}^N \binom{N}j = \prod_{k=1}^N k^{N+1-2(N-k+1)} = \prod_{k=1}^N k^{2k-N-1}.$$

Answer 2

I suggest you rewrite the identity as $$ \prod_{j=0}^N \binom{N}{j} = \frac{(\prod_{k=1}^N k^k)^2}{(N!)^{N+1}}, $$ and this is the version I will use below.

Before starting a proof, the key point to be aware of is that binomial coefficients admit the identity $$ \binom{a}{b} = \frac{a}{b}\binom{a-1}{b-1} $$ when $a\geq b \geq 1$.

You can check the identity holds at $N=1$. (I checked it up to $N = 4$ to make sure it wasn’t mistyped.) Assuming it holds at a positive integer $N$, we have \begin{align*} \prod_{j=0}^{N+1} \binom{N+1}{j} & = \prod_{j=1}^{N+1} \binom{N+1}{j} \\ & = \prod_{j=1}^{N+1} \frac{N+1}{j}\binom{N}{j-1}\\ & = \frac{(N+1)^{N+1}}{(N+1)!}\prod_{j=0}^N\binom{N}{j}. \end{align*} By induction, that last product can be rewritten and we get \begin{align*} \prod_{j=0}^{N+1}\binom{N+1}{j} & = \frac{(N+1)^{N+1}}{(N+1)!} \frac{(\prod_{k=1}^N k^k)^2}{(N!)^{N+1}} \\ & = \frac{(N+1)^{2(N+1)}(\prod_{k=1}^N k^k)^2}{(N+1)^{N+1}(N+1)!(N!)^{N+1}}. \end{align*} The numerator is what we want and the denominator is $(N+1)!((N+1)!)^{N+1}$, which is $(N+1)!^{N+2}$ and that is also what we want. QED

As long as you keep in mind that $\binom{a}{b} = \frac{a}{b}\binom{a-1}{b-1}$, I would consider the argument above to be a straightforward induction: no special tricks are needed. It is the kind of thing a reader can be expected to derive on their own when the journal is tight on space. So if nobody can point to a published proof and the journal does not let you cite this MO page, just say the identity can be proved by induction on $N$ while keeping in mind that $\binom{a}{b} = \frac{a}{b}\binom{a-1}{b-1}$ if $a\geq b \geq 1$.

Remark. There are few places in math where I have seen $k^k$ naturally show up (forget tetration, please). Besides the identity above, I can think of its role in Stirling’s estimate for $k!$ and in the Gauss—Legendre multiplication formula (distribution relation) $$ G(z)G(z+1/k)\cdots G(z+(k-1)/k) = \sqrt{k}\frac{G(kz)}{k^{kz}}, $$ where $G(z) = \Gamma(z)/\sqrt{2\pi}$.