3

当集合包含唯一实体时， Pascal关于计算集合子集的规则非常有效。

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

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

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

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

4

6 回答 6

4

一个集合只包含独特的项目。如果有重复，那么它不再是一个集合。

于 2008-09-19T16:52:39.070 回答
4

是的，如果您不想考虑集合，请考虑“因素”的概念。有多少因素：

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

如果 p1 是不同的素数，则有。如果 ai 都为 1，则数字为 2^n。一般来说，答案是 (a1+1)(a2+1)...(an+1) 正如 David Nehme 所说。

哦，请注意，您的手动答案是错误的，如果您不想计算空集，则应该是 48 或 47。

于 2008-09-19T17:48:45.940 回答
4

看起来你想知道有多少子多集有，比如 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

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

于 2008-09-19T17:55:18.717 回答
2

您根本不需要修改帕斯卡三角。研究 C(k,n) 你会发现——你基本上需要除以原始结果来解释等价字母的排列。

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

于 2008-09-19T17:03:06.953 回答
1

如果没有重复项（如早期海报所指出的那样，在集合中），每个元素要么在子集中，要么在子集外。所以你有 2^n 个子集。对于重复项（在“多集合”中），您必须考虑每个元素在“子多集合”中的次数。如果它m_1,m_2...m_n代表每个元素重复的次数，那么子包的个数就是(1+m_1) * (1+m_2) * ... (1+m_n)。

于 2008-09-19T17:10:59.900 回答
0

尽管数学集合确实包含独特的项目，但在现实编程世界中，您可能会遇到“集合”中重复项目的问题。有关示例，请参见Lisp unions 上的此线程。

于 2008-09-19T17:00:02.453 回答