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

Answer 3

The left side counts structures of the form a|a,b|a,b,c|,..., where the $k$th grouping consists of $k$ distinct elements from $\{1,\dots,N\}$.

Counting another way: we pick the first element of each grouping (the a's above), with $N^N$ choices; then the second element of those groupings with at least two elements, giving $(N-1)^{N-1}$ choices, and so on, for a total of $\prod_{k=1}^N k^k$.

But oops: on the left side, order within a grouping doesn't matter. So on the right, we'd better divide by $2$ for each grouping with at least two elements (we could swap those two), of which there are $N-1$. Then we must additionally divide by $3$ for each grouping with at least three elements (after optionally swapping the first two, we could insert the third element in three different places), and so on. So we'd better divide by $\prod_{k=1}^N k^{N-k+1}$.

We get $\prod_{k=1}^N k^{k - (N-k+1)} = \prod_{k=1}^N k^{2k-N-1}$.

...

As a side note, we could have more simply corrected the double counting with the perhaps-more-appealing denominator $\prod_{k=1}^N k!$, which would yield the aesthetic identity $$ \prod_{k=1}^N {N \choose k} = \prod_{k=1}^N \frac{k^k}{k!} . $$

...

(Since this is MO, I'll hope it's generally on-topic when given an identity to post your favorite proof, even if that's not exactly the question.)