当集合中包含唯一实体时，帕斯卡(Pascal)的计算集合子集的规则非常有用。

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

例如，当我尝试查找字母A，B，C，D的组合的数量时，很容易看到它是1 + 4 + 6 + 4 + 1(从Pascal的三角形中得出)= 16，或者15我删除了"不使用字母"条目。

现在，如果字母集是A，B，B，B，C，C，D怎么办？通过手工计算，我可以确定子集的总和为：1 + 4 + 8 + 11 + 11 + 8 + 4 + 1 = 48，但这与我所知道的三角形不符。

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

解决方案

一组仅包含唯一项。如果有重复项，则不再是集合。

即使数学集合确实包含唯一项，我们也可能在编程的现实世界中遇到"集合"中重复项的问题。有关示例，请参见有关Lisp联合的该线程。

我们根本不需要修改Pascal的Triangle。研究C(k，n)，我们将发现-我们基本上需要对原始结果进行划分，以考虑等价字母的排列。

例如A B1 B2 C1 D1 == A B2 B1 C1 D1，因此我们需要将C(5,5)除以C(2,2)。

没有重复项(如先前的张贴者所述，在一组中)，每个元素或者在子集中或者在子集中。所以你有2 ^ n个子集。对于重复项(在"多组"中)，必须考虑每个元素在"子多组"中的次数。如果m_1，m_2 ... m_n表示每个元素重复的次数，则子袋的数量为(1 + m_1)(1 + m_2)...(1 + m_n)。

是的，如果我们不想考虑集合，请考虑"因素"的概念。有多少因素起作用：

p1^a1.p2^a2....pn^an

如果p1是不同的素数，则具有。如果ai全部为1，则数字为2 ^ n。通常，答案是(a1 + 1)(a2 + 1)...(an + 1)，如David Nehme所说。

哦，请注意，我们手动输入的答案是错误的，如果我们不想计算空集，则应该为48，或者为47.

我们似乎想知道有多少个子多集，例如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

如果要在代码中生成这些数字，我将使用多项式技巧来组织思考和代码。 (我们将要使用系数数组。)