分区中可能的组合数

Question

给定一个大小为 n 的集合 S，它被划分为大小为 n1,...,nk 的类 (s1,..,sk)。 自然，n=n1+...+nk。

我有兴趣找出可以组合此分区的元素的方法数量，以便每个组合恰好包含每个类的一个元素。

由于我可以从 s1 中选择 n1 个元素，从 s2 中选择 n2 个元素，依此类推，我正在寻找任意 n1,..nk 的 max(n1*..*nk) 的解决方案，其中它保持 n1+..+nk =n。

我感觉这是一个线性优化问题，但自从我本科生学习这些东西以来已经太久了。 我希望有人记得如何计算这个。

Answer 1

您正在寻找每个分区中一个元素的组合数量？

这只是 n1*n2*...*nk。

编辑：
您似乎还提出了一个单独的问题：

给定 N，我如何分配 n1，n2，...，nk 以使它们的乘积最大化。 这实际上不是一个线性优化问题，因为您的变量相乘。

它可以通过一些微积分来解决，即通过在约束下使用拉格朗日乘子对每个变量进行偏导数。

结果是 n1 .. nk 应尽可能接近相同的大小。

if n is a multiple of k, then n_1 = n_2 = ... = n_k = n/k

otherwise, n_1 = n_2 = ... = n_j = Ceiling[n/k]
      and  n_j+1 = ... = n_k = floor[n/k]

基本上，我们尝试将元素尽可能均匀地分布到分区中。 如果它们均匀分布，那就太好了。 如果没有，我们尽可能均匀地划分，并且对于剩下的任何内容，我们为第一个分区每个提供一个额外的元素。 （不一定是第一个分区，这个选择是相当任意的。）这样，任何两个分区拥有的元素数量最多相差一个。

详细信息：

这是我们希望最大化的乘积函数：

P = n1*n2*...nK

我们使用拉格朗日乘子定义一个新函数：

Lambda = P + l(N - n1 - n2 ... -nk)

并在每个 k n_i 变量中取偏导数：

dLambda/dn_i = P/n_i - l

和在 l 中：

dLambda/dl = N - n1 -n2 ... -nk

设置所有偏导数 = 0，我们得到一个 k + 1 个方程组，当我们求解它们时，我们会得到 n1 = n2 = ... = nk

一些有用的链接：

拉格朗日乘数

优化

Answer 2

floor(n/k)^(k - n mod k)*ceil(n/k)^(n mod k)

——马库斯

Q 对于您给出的 S = {1,2,3,4}, n = 4, k = 2 的示例，这给出：

floor(4/2)^(2 - 4 mod 2)*ceil(4/2)^(4 mod 2)
floor(2)^(2 - 0)*ceil(2)^(0)
2^2 * 2^0
4 * 1
4

...如您所愿。

为了澄清起见，该公式给出了通过最大可能排列数的划分生成的排列数。 当然还会有其他不太理想的分区。

对于给定的周长，面积最大的矩形是最接近正方形的矩形（在更高的维度中也是如此），这意味着您希望边的长度尽可能接近相等（例如，所有边都可以）平均长度向上或向下舍入）。 那么公式可以看出：

   (length of short sides)^(number of short sides)
times
   (length of long sides)^(number of long sides)

这就是满足这个约束的超矩形的体积。

请注意，以这种方式查看时，它还告诉您如何构建最大分区。