# Upper bound of product of binomial coefficients

Given $$L$$ a constant positive integer, and $$1\leq k \leq L$$.

My question are:

(1) What is the upper bound of

$$\binom{m_1}{2}\binom{m_2}{2}\cdots\binom{m_k}{2}\leq \cdots$$

among all partitions $$(m_1,\cdots,m_k)$$ of integer $$n$$, i.e. $$m_1+\cdots+m_k=n$$, $$1\leq m_i\leq n$$?

Note: I define $$\binom{1}{2}$$ as $$0$$.

(2) I would like to understand how $$(m_1,\cdots,m_k)$$ influences the value of this quantity. Is it possible to see when will (what makes) this quantity to be small or large?

• I see that $m_i$ can be $1$, is $\binom{1}{2} = 0$ ? Commented Aug 24, 2023 at 12:18
• @DanielCunha Yes! I will now add it to the post. Commented Aug 24, 2023 at 12:19
• You can write $\binom{m}{2}=m(m-1)/2$. You can ignore the $2$ in the denominators (or collect them into a single constant factor $1/2^k$). Then the problem becomes a polynomial in the $m_i$, and you can turn this discrete problem into a continuous one. I'll switch from $m_i$ to $x_i$ to denote this change. From there you can use Lagrange multipliers to prove that the maximum occurs when $x_1=x_2=\ldots = x_k=n/k$ (ignoring the $1\leqslant m_i$ constraint).
– user520024
Commented Aug 24, 2023 at 12:51
• From here, as @julio_es_sui_glace said, the maximum will be as close as you can get to this point while obeying your constraints $1\leqslant m_i\leqslant n$ and $m_i$ are integers. Note that if $k>n$, there are no $m_i$ which satisfy your conditions, since $m_1+\ldots + m_k\geqslant 1+\ldots + 1 =k>n$.
– user520024
Commented Aug 24, 2023 at 12:54
• Quick beginner guide for asking a well-received question + please avoid "no clue" questions + focus on one question per post + clarify whether you are looking for the least upper bound for a fixed $k$ (as the comments and answer seem to interpret), or over all $k\le L$ (as the beginning of your post seems to mean). Commented Aug 24, 2023 at 15:13

I've got some partial results:

By definition: $$\boxed{n = m_1 + ... + m_k}$$ ; $$\boxed{m_k \geq 1}$$ ; $$\boxed{n \geq k}$$

$$f(m_1,...,m_k) = \binom{m_1}{2}\binom{m_2}{2}...\binom{m_k}{2}$$

$$\binom{m_i}{2} = \frac{[m_i-1]\,m_i}{2}$$

$$f(m_1,...,m_k) = \frac{[m_1\,m_2\,...\,m_k][m_1-1][m_2-1]...[m_k-1]}{2^k}$$

Let's first solve for the small cases:

If $$k \leq n < 2\,k$$, there is at least one $$m_i=1$$, so $$f(m_1,...,m_k)=0$$

If $$n = 2\,k$$, $$m_1=m_2=...=m_k=2$$ would yield the maximal value: $$f(m_1,...,m_k)=1$$

Now, let's assume $$\boxed{m_k\geq 2}$$, so that $$f(m_1,...,m_k)$$ is strictly positive.

If we would write this as an continuous maximization problem, we would get the following derivatives.

$$\nabla f = \frac{1}{2^k}\begin{bmatrix} [m_2\,m_3\,...\,m_k][m_2-1][m_3-1]...[m_k-1]\,[2\,m_1-1]\\ [m_1\,m_3\,...\,m_k][m_1-1][m_3-1]...[m_k-1]\,[2\,m_2-1]\\ \vdots\\ [m_1\,m_2\,...\,m_{k-1}][m_1-1][m_2-1]...[m_{k-1}-1]\,[2\,m_k-1]\\ \end{bmatrix}$$

$$g(m_1,...,m_k) = m_1+...+m_k - n = 0$$

$$\nabla g = \begin{bmatrix} 1\\ 1\\ \vdots\\ 1 \end{bmatrix}$$

From these derivatives, it can be shown that $$m_1=m_2=...=m_k=\frac{n}{k}$$ is a local maximum that can be achieved in the discrete original problem whenever $$\boxed{n = d\,k}$$, with $$d\in\{1,2,...\}$$.

For this particular cases, the local maximal value of $$f$$ would be:

$$\boxed{\frac{n^k\,[n-k]^k}{2^k\,k^{2k}}}$$

If we can now show that this is a global maximum for the relaxed continuous problem, then it will be an upper bound for the discrete original function!

Note that, if $$m_1=m_2=...=m_k=\frac{n}{k}$$ is the global solution of the optimization problem:

$$\text{maximize} \;\; m_1\,m_2\,...\,m_k$$ $$\text{subject to} \;\; m_1+m_2+...+m_k=n$$

Then, $$m_1-1 = m_2-1 = ... = m_k-1 = \frac{n-k}{k}$$ will solve:

$$\text{maximize} \;\; [m_1-1][m_2-1]...[m_k-1]$$ $$\text{subject to} \;\; [m_1-1] + [m_2-1] + ... + [m_k-1] = n-k$$

Since our function of interest is the product of these two (divided by $$2^k$$), this would mean that the presented local optimum is global!

So now the problem is reduced to prove that the product of $$k$$ positive values with fixed sum is maximal when all the factors are equal.