Let P be a finite set with |P| elements and n the number of possible partitions of P. I want to find the maximum value of the product of the cardinalities of all the elements in each partition without including the partition: {{P}}. I am giving an example below of what I am looking for.
P = {1,2,3}
|P| = 3, n=5
Partition1: { {1}, {2}, {3} } Product: 1*1*1 = 1
Partition2: { {1, 2}, {3} } Product: 2*1 = 2
Partition3: { {1, 3}, {2} } Product: 2*1 = 2
Partition4: { {1}, {2, 3} } Product: 2*1 = 2
Partition5: { {1, 2, 3} } Product: = 3 [Do not include this partition]
In this case the maximum product is 2. I am aware that my description of the problem is not good (that is why I included an example).
Many thanks in advance.
We want to write the positive integer $n$ as a sum of positive integers $x_1,\dots,x_k$ so as to maximize the product $x_1\cdots x_k$. (We can ignore your requirement that $k\gt1$ because it's irrelevant when $n\gt3$, and the cases $n\le3$ can be handled separately.) To avoid a trivial exceptional case, we assume that $n\gt1$.
Suppose that $n=x_1+\cdots+x_k$ is an optimal decomposition, i.e., the product $x_1\cdots x_k$ is maximized.
We must have $x_i\le4$ for all $i$; if we had some $x_i\gt4$, then we could replace the term $x_i$ with the two terms $2,\ x_i-2$ and increase the product, since $2(x-2)\gt x$ when $x\gt4$. In fact, we may assume that $x_i\le3$ for all $i$, since a $4$ could be exchanged for two $2$s without changing the product.
Also, we must have $x_i\ne1$, since a $1$ could be combined with another term (recall our assumption $n\gt1$) increasing the product. Thus there is an optimal decomposition consisting only of $2$s and $3$s.
Finally, there are at most two $2$s, since three $2$s could be exchanged for two $3$s.
Therefore, the solution (for $n\gt1$) is: Find the unique $r\in\{0,1,2\}$ such that $2r\equiv n\pmod3$ and write $n=2r+3s$, making the maximum product $2^r3^s$.