logo标签列表

非唯一集合的Pascal定理？

mathpascals-triangle
3

当集合包含唯一实体时，帕斯卡定理在计算子集数量方面非常有效。

如果集合包含重复项，是否有修改此规则的方法？

例如，当我尝试查找字母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，但这与我所知道的三角形不符。

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

6个回答
4

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

通常称为多重集合或袋。 - Hank
我觉得争论术语问题成为最受欢迎的回答令人沮丧。有人真的没有理解所提出的问题吗？ - user11318
数学建立在非常精确的定义之上，因此“术语”很重要。如果您随意更改集合的定义，则定义在集合上的操作可能会改变其含义，或者完全变得无意义。 - Dima
抱歉Dima，但你错了。多重集看起来像集合，但它们允许重复，并且“子集”、“成员”、“并集”和“交集”的含义与Pascal认为的一样。 - user11318
我们来说说这种语义上的较真吧，虽然在一些小的方面可能会有些好处（如果你绝对确定自己是正确的），但这并不能让别人把它标记为“最佳答案”。 - billjamesdev
显示剩余2条评论
4

如果您不想考虑集合，可以考虑“因子”的概念。以下数字有多少个因子:

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

如果p1是不同的质数，那么有a1个p1，a2个p2，以此类推。如果所有的ai都是1，那么这个数字就是2^n。一般来说，答案是(a1+1)(a2+1)...(an+1)，正如David Nehme所指出的。

另外，请注意你手动计算的答案是错误的，应该是48，如果不计算空集，则为47。

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

如果您想在代码中生成这些数字，我建议使用多项式技巧来组织思路和代码（您将使用系数数组）。
2
你不需要修改帕斯卡三角形。研究组合数 C(k,n) ，你会发现——基本上需要除以原始结果，以考虑等价字母的排列。
例如，A B1 B2 C1 D1 == A B2 B1 C1 D1，因此你需要将 C(5,5) 除以 C(2,2)。
这有助于您获取子多集的总数。但如果您想解决具有5个元素的子多集的总数，这是无济于事的。 - user11318
C(5,5) = 1，C(2,2)也是1...这距离我需要的还差得远。 - billjamesdev
1

不考虑重复项（如前面的帖子所述，使用集合），每个元素要么在子集中，要么不在。因此，你有2^n个子集。考虑重复项（在“多重集”中），你必须考虑每个元素在“子多重集”中出现的次数。如果m_1、m_2...m_n表示每个元素重复的次数，则子包的数量为(1+m_1) * (1+m_2) * ... (1+m_n)。

0

尽管数学集合包含唯一的项，但在编程的现实世界中，“集合”中可能会遇到重复项的问题。请参见Lisp联合的this thread示例。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接