math - 非唯一集的帕斯卡定理？

Question

Pascal's rule当集合包含唯一实体时，计算集合的子集效果很好。

当集合包含重复项时，是否对此规则进行了修改？

例如，当我尝试计算字母 A、B、C、D 的组合数时，很容易看出它是 1 + 4 + 6 + 4 + 1(来自帕斯卡三角形)= 16，或者如果我删除了“不使用任何字母”条目。

现在，如果字母集是 A、B、B、B、C、C、D 呢？手工计算，我可以确定子集的总和是:1 + 4 + 8 + 11 + 11 + 8 + 4 + 1 = 48，但这不符合我所知道的三角形。

问题:如何修改 Pascal 三角形以考虑集合中的重复实体？

Answer 1

看起来你想知道有多少子多集有，比如 3 个元素。这个的数学计算变得非常棘手，非常快。这个想法是你想把所有到达那里的方法组合加在一起。所以你有 C(3,4) = 4 种没有重复元素的方法。 B 可以以 C(1,3) = 3 种方式重复两次。 B 可以用 1 种方式重复 3 次。并且 C 可以以 C(1,3) = 3 种方式重复两次。共 11 个。 (你亲手得到的 10 是错误的。对不起。)

一般来说，试图做到这种逻辑太难了。跟踪它的更简单方法是写出一个多项式，其系数具有您想要的项，然后乘以。对于帕斯卡三角形，这很容易，多项式是 (1+x)^n。 (您可以使用重复平方来更有效地计算。)在您的情况下，如果一个元素重复两次，您将拥有 (1+x+x^2) 因子。 3 次是 (1+x+x^2+x^3)。因此，您的具体问题将按如下方式解决:

(1 + x) (1 + x + x^2 + x^3) (1 + x + x^2) (1 + x)
  = (1 + 2x + 2x^2 + 2x^3 + x^4)(1 + 2x + 2x^2 + x^3)
  = 1    + 2x   + 2x^2 +  x^3 +
    2x   + 4x^2 + 4x^3 + 2x^4 +
    2x^2 + 4x^3 + 4x^4 + 2x^5 +
    2x^3 + 4x^4 + 4x^5 + 2x^6 +
    x^4  + 2x^5 + 2x^6 +  x^7
  = 1 + 4x + 8x^2 + 11x^3 + 11x^4 + 8x^5 + 4x^6 + x^7

如果您想在代码中生成这些数字，我会使用多项式技巧来组织您的思维和代码。 (您将使用系数数组。)