当前位置：文江博客话题详情

非唯一集合的帕斯卡定理？

发布于 2024-07-05 21:22:45 字数 441 浏览 13 评论 0原文

当集合包含时，帕斯卡规则在计算集合的子集时效果很好独特的实体。

当集合包含重复项目时，此规则是否有修改？

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

无悔心 2024-07-12 21:22:46

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

回复收藏 0 原文

尴尬癌患者 2024-07-12 21:22:46

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

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

回复收藏 0 原文

凉墨 2024-07-12 21:22:46

是的，如果您不想考虑集合，请考虑“因子”的概念。多少个因数

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

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

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

Yes, if you don't want to consider sets, consider the idea of 'factors.' How many factors does:

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

have if p1's are distinct primes. If the ai's are all 1, then the number is 2^n. In general, the answer is (a1+1)(a2+1)...(an+1) as David Nehme notes.

Oh, and note that your answer by hand was wrong, it should be 48, or 47 if you don't want to count the empty set.

回复收藏 0 原文

牛↙奶布丁 2024-07-12 21:22:46

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

回复收藏 0 原文

审判长 2024-07-12 21:22:46

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

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

It looks like you want to know how many sub-multi-sets have, say, 3 elements. The math for this gets very tricky, very quickly. The idea is that you want to add together all of the combinations of ways to get there. So you have C(3,4) = 4 ways of doing it with no duplicated elements. B can be repeated twice in C(1,3) = 3 ways. B can be repeated 3 times in 1 way. And C can be repeated twice in C(1,3) = 3 ways. For 11 total. (Your 10 you got by hand was wrong. Sorry.)

In general trying to do that logic is too hard. The simpler way to keep track of it is to write out a polynomial whose coefficients have the terms you want which you multiply out. For Pascal's triangle this is easy, the polynomial is (1+x)^n. (You can use repeated squaring to calculate this more efficiently.) In your case if an element is repeated twice you would have a (1+x+x^2) factor. 3 times would be (1+x+x^2+x^3). So your specific problem would be solved as follows:

(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

If you want to produce those numbers in code, I would use the polynomial trick to organize your thinking and code. (You'd be working with arrays of coefficients.)

回复收藏 0 原文