Let $n\geq 1$ be a total number of objects that must be taken from $m\geq 1$ sets of objects.
For all $i \in \{1,\cdots,m\}, \ M_i \in \mathbb{N}^*$ denotes the number of objects present in the set $i$.
We assume that:
$\forall i \in \{1,\cdots,m\}, \ \ \ M_i \leq n$
And that:
$\sum\limits_{i=1}^{m}M_i\geq n$
In this context, we introduce the variables $n_i \in \mathbb{N}$ for all $i \in \{1,\cdots,m\}$: the number of objects taken from the set $i$. It means that we need to choose the $n_i$ variables under the constraint:
$\sum\limits_{i=1}^{m}n_i = n$
I am interested in chosing the $n_i$ variables in a way that maximizes the product of the numbers of permutations of size $n_i$ taken from each set $i$ of size $M_i$, that is:
$\text{Maximize } \displaystyle \prod\limits_{i=1}^{m}\dfrac{M_i!}{(M_i-n_i)!}$
My intuition, that I did not manage to prove, is that the sets $i$ must be sorted in decreasing order of their size $M_i$: the idea is to use the biggest sets to reach high individual factors in the maximized product. We start by setting, for the biggest set $i_1$, $n_{i_1}=M_{i_1}-1$ (and not $M_{i_1}$ because the resulting number of permutations is the same and it "leaves" more objects for the next sets). The overall number of objects to extract is updated, the set $i_1$ removed from the analysis, and the process is repeated until there is no more objects to extract.
Do you think this actually leads to the maximal number aimed ? How could we prove it ?
Thanks !
Consider this example: $n=4,m=3,M_1=5,M_2=4,M_3=3$. Your algorithm suggests the solution $n_1=4,n_2=0,n_3=0$, which gives a product of 120. But the choice $n_1=2,n_2=2,n_3=0$ yields a product of 240.
Your problem is equivalent to the following: Label the balls in set $i$ with the integers $1 \ldots M_i$. Now select $n$ balls from the entire set, and maximize the product of the labels on these balls. In this formulation, it is clear you should take the $n$ balls with the largest labels.
In your original problem, this can be implemented algorithmically by sequentially picking $n$ balls, at each step picking from the set with the largest number of balls remaining at that step.
Note that this analysis would not work if you were summing the number of permutations for each $i$. By looking at the product, there is no incentive to take "lower value" balls from a large set to goose the number of permutations from that set, since taking an element from another set has the same effect.