Product of binomial coefficients and interesting properties

76 Views Asked by At

I recently encounter the following quantity

\begin{eqnarray} \frac{n^+!n^-!}{n!}\frac{k!}{k^+!k^-!}\frac{l!}{l^+!l^-!} \end{eqnarray}

$n^\pm,n,k^\pm,k,l^\pm,l$ are all non-negative integers. There are some relations between these variables: \begin{eqnarray} n=n^++n^-,\quad k=k^++k^-,\quad l=l^++l^-,\\ n^+=k^++l^+,\quad n^-=k^-+l^- \end{eqnarray} we define the above quantity as a function of $n^\pm,k,k^+$ \begin{eqnarray} f_{n^\pm}(k,k^+)=\frac{n^+!n^-!}{(n^++n^-)!}\frac{k!}{k^+!(k-k^+)!}\frac{(n^++n^—k)!}{(n^+-k^+)!(n^- -k+k^+)!} \end{eqnarray} by applying the relations, where we always treat $n^\pm$ as parameters.

I checked experimentally that for all choices in $0\leq n^\pm\leq 6$, the maximal value of $f_{n^\pm}$ always happens at either $k=0$ or $k=n$ ($l=0$), and the maximal value always equals 1.

The above result always true in all experiments I did, although I don’t know how to prove it in general.

I expect that for all choice of $n^\pm$, $f_{n^\pm}$ should always approach its maximum at either $k=0$ Or $k=n$, with $Max(f_{n^\pm})=1$.

Does anyone have an idea for a proof?

1

There are 1 best solutions below

0
On

I am going to change your notation a little to make it a little clearer for myself.

Here are the replacements I will make (in each case, they are equal based on the equalities you provided in the original post):

$$\begin{array}{c|c}\text{Your notation} & \text{My notation} \\ \hline n & n \\ k & k \\ l & n-k \\ k^+ & a \\ l^+ & b \\ k^- & k-a \\ l^- & (n-k)-b \\ n^+ & a+b \\ n^- & n-(a+b)\end{array}$$

Note: The reason I prefer this notation is because it takes your nine variables and condenses them down to four, and four variables is MUCH easier to work with than nine.

Now, plugging these values into your original formula, we have:

$$\dfrac{(a+b)!(n-(a+b))!}{n!} \dfrac{k!}{a!(k-a)!} \dfrac{(n-k)!}{b!(n-k-b)!} = \dfrac{\dbinom{k}{a}\dbinom{n-k}{b}}{\dbinom{n}{a+b}}$$

Now, we can start talking about what this expression means. The numerator is the number of ways to select $a+b$ things from a set, but $a$ of them must come from an already chosen subset of size $k$ things while $b$ of them must come from the rest set. The denominator is the number of ways to select $a+b$ things from a set of $n$ things without restrictions.

It should be clear that this ratio will be nonnegative so long as you choose valid numbers for $a,b,k,n$ (because there is a nonnegative number in the numerator and denominator). It should also be clear that any result you get from the method of splitting the set up and then choosing $a$ items from one set and $b$ from the other will net you $a+b$ items from the original set. So, the numerator is less than or equal to the denominator.

When $k=a=0$, you have:

$$\dfrac{\dbinom{0}{0}\dbinom{n-0}{b}}{\dbinom{n}{0+b}} = \dfrac{\dbinom{n}{b}}{\dbinom{n}{b}} = 1$$

This shows the expression can reach a value of one.

There you go! This is an outline for a combinatorial proof that the ratio has a maximum value of 1.