2
$\begingroup$

I would like to maximize $n_1! n_2! \cdots n_k!$ under the constraint $n_1 + n_2 + \cdots + n_k = N$ and $n_i > 0$ for all $i$. Intuitively, I think the maximum occurs when all $n_i$ are $1$ except for one of them: $$(1!)( 1!) \cdots (1!)( (N-(k-1))!)$$ but I am unsure how to show this because I can't take the derivative of this kind of function. Could someone point me in the right direction? Thanks!


Edit: perhaps induction on $k$ will work?

If $k=2$, it is a little easier to see that the maximum of $n_1!n_2!=n_1! (N-n_1)!$ is $N!$ (how to rigorously show this still escapes me). Then it follows by induction, I believe.

$\endgroup$
  • $\begingroup$ Maybe you could use the more general definition of the factorial using the Gamma Function $\Gamma (n)$. It is differentiable everywhere except for negative integers. $\endgroup$ – Xoque55 Nov 13 '13 at 15:27
  • $\begingroup$ @Xoque55 I was thinking about that as well, but it seems like overkill for such an innocent-looking problem... is that the only way? $\endgroup$ – angryavian Nov 13 '13 at 15:28
2
$\begingroup$

Since there are only finitely many possibilities for the $n_i$, there is (at least) one configuration that maximises $\prod\limits_{i=1}^k n_i!$.

Now showing that a configuration in which there are at least two $i$ with $n_i > 1$ does not maximise the product yields the conclusion. So suppose there are two (or more) $n_i > 1$. Without loss of generality, assume $n_1 \geqslant n_2 > 1$. Then

$$\frac{(n_1+1)!(n_2-1)!\prod\limits_{i=3}^kn_i!}{\prod\limits_{i=1}^k n_i!} = \frac{n_1+1}{n_2} > 1,$$

so the configuration $(n_1+1,n_2-1,n_3,\dotsc,n_k)$ yields a greater product.

$\endgroup$
2
$\begingroup$

Increasing the largest $n_i$ by 1 and simultaneously decreasing the smallest $n_j$ by 1 respects the condition $n_1 + n_2 + \cdots + n_k = N$ and increases the product. Therefore you can make all of the factors equal to 1 except the biggest one.

$\endgroup$
-1
$\begingroup$

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$ $\ds{{\cal F} \equiv \sum_{\ell = 1}^{k}\ln\pars{\Gamma\pars{n_{\ell} + 1}} - \mu\pars{\sum_{\ell = 1}^{k}n_{\ell} - N}}$ $$ 0 = \partiald{{\cal F}}{\tilde{n}_{\ell}} = \Psi\pars{\tilde{n}_{\ell} + 1} - \mu\,, \quad\forall\ \ell\quad\imp\quad \tilde{n}_{\ell} = {N \over k}\,,\quad\forall\ \ell $$

$\endgroup$
  • $\begingroup$ That gives a minimum, not a maximum. $\endgroup$ – Mikhail Katz Nov 13 '13 at 17:25
  • $\begingroup$ @user72694 $0$ k. I'll check a little later. Thanks. $\endgroup$ – Felix Marin Nov 13 '13 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.