What is the closed form of this function?

Question

It is well-known that the binomial coefficient has some monotonicity, and that can be used to find the maximum and minimum of binomial coefficients.

Similarly, now let $\left(\delta_{i,j}\right)_{6\times6}$ be a binary matrix with $\delta_{i,i}=1$ and $\delta_{i,j}=\delta_{j,i}=1$ or $0$ when $i\ne j$ and $\delta_{i}=\sum_{j=1}^{6}\delta_{i,j}$. Let's define $$ f(k):=\min_{\delta_{1}+\delta_{2}+\delta_{3}+\delta_{4}+\delta_{5}+\delta_{6}=2k}\delta_{1}\delta_{2}\delta_{3}\delta_{4}\delta_{5}\delta_{6} $$ for integer $k$ , $3\le k\le18$, then what is the closed form or combinatorial expression of $f(k)$ as a function of $k$?

Thanks.

Answer 1

The minimum is achieved by filling as large an upper left square block as possible with entries 1, and partially filling the next row below that block (and, symmetrically, the next column to the right of that block) with the remaining available entries 1. The value of $f(k)$ achieved in this way is $$ f(k)=c(k)^{c(k)} \cdot [(c(k)+1)/c(k)]^{r(k)} \cdot [r(k)+1] $$ where the aforementioned upper left square block has size $c(k) \times c(k)$, and $2r(k)$ is the number of residual entries 1 available to partially fill the next row and column, as described. It remains to give explicit expressions for $c(k)$ and $r(k)$. There are probably prettier and more succinct forms, but quickly one could just specify $$ c(k)=1+\frac{k}{4}+\frac{k}{6}+\frac{k}{9}+\frac{k}{13}-\frac{k}{8}-2\left( \frac{k}{12} \right) -\frac{k}{18} $$ where division is to be interpreted as integer division, and $$ r(k)=k-3+(1-c(k))c(k)/2 $$ I have verified that these expressions give the correct minimal values by explicit computation of all possibilities.

An alternative expression for $c(k)$ is $$ c(k) = \mbox{int} \left[ \frac{1}{2} + \sqrt{\frac{1}{4} + 2k-6} \right] $$