整数方程-星形和条形
在组合学中经常出现的一个问题是,当计算将相同物体分组的方法的数量时,例如将无法区分的球放入标记好的瓮中。我们讨论一种组合计数技术,称为星星和酒吧或球和骨灰盒为了解决这些问题,不可区分的物体用星形表示,分组用条形表示。
这允许我们将要计数的集合转换为另一个更容易计数的集合。因为我们有一个双射,这些集合的大小相同。
简介
考虑这个等式 在哪里 都是非负整数。我们要求的是这个方程解的个数。起初,我们不太清楚该如何处理这个问题。一种方法是蛮力:确定一个变量的可能性,并分析其他变量的结果。但我们想要更好,更优雅的东西。我们使用上面提到的策略:通过显示双射将一个集合转换为另一个集合,这样第二个集合更容易计数。
假设我们有 我们放置的地方 明星和 酒吧,一个地方一件。关键是这个构型代表了方程的解。例如, 代表解决方案 .因为我们有 星号,然后是横线(代表加号),然后 星星,同样是条线,类似的 而且 明星效仿。同样的, 表示解 因为我们一开始没有星号,然后有条杠,推理和前面类似。
我们看到,任何这样的构型都代表这个方程的解,而这个方程的任何解都可以转化成这样的星条形级数。所以我们已经在方程的解和构型之间建立了双射 明星和 酒吧。所以我们的问题归结为“我们可以用多少种方式来放置。 明星和 酒吧 的地方吗?”这和固定是一样的 以外的地方 在其他地方填满星星。当然,我们可以这样做, 的方式。所以方程的解的个数是
星条定理
星条/球和瓮技术如下所述。
放置方法的数量 难辨球进 有标签的骨灰盒
下面是上述定理的证明。
我们代表 球的 相邻的星星,考虑插入 在恒星之间把这些条分开 组。例如,对于 而且 ,下面是一组的表示 5个瓮中无法区分的球,其中瓮1、2、3、4和5的大小分别为2、4、0、3和3:
注意,在分组中,可能会有空的骨灰盒。总共有 职位,其中 是星星和 是酒吧。由此可见,摆放方式的数量 难辨球进 标记骨灰盒的方法是一样的 之间的位置 星星的空格,所有剩余的位置都作为条。有很多方法可以做到这一点
注意: 可以解释为选择位置的方法的数量 酒吧和采取所有剩余的位置是明星。
请看下面的例子:
有多少个有序的非负整数集 是否存在这样的情况
我们首先在的解之间创建一个双射 长度为13的序列由10组成 's和3 换句话说,我们将每个解与一个唯一的序列相关联,反之亦然。
给定一个4个整数的集合 ,我们创建开始的序列 的,然后有一个 ,则有 的,然后有一个 ,则有 的,然后有一个 ,则有 例如,if ,则关联序列为 .现在,如果我们加上这个限制 ,关联序列将由10组成 (从 )及3 's(来自我们的手动插入),因此总长度为13。
相反,给定一个由10组成的长度为13的序列 's和3 的,让 的初始字符串的长度 ’s(在第一个字母之前 ),让 是下一个1的字符串的长度(在第一个和第二个之间 ),让 的第三根弦的长度 在第二和第三之间 ),并让 的最后一根弦的长度 (在第三个之后 ).这些值给出了方程的解 .
这种构造将每个解与唯一的序列相关联,反之亦然,因此给出了双射。
现在我们有了一个双射,这个问题相当于计算由10个序列组成的长度为13的序列的数量 's和3 ,我们使用星形和条形技术进行计数。有 我们选择的位置 位置为1,其余位置为0。通过星星和酒吧,有 不同的选择。
注意:解决这个问题的另一种方法是方法生成函数.
解决问题
本节包含示例,然后给出需要尝试的问题。
求的非负整数解的个数
我们有 变量,因此 +的迹象。根据星形和条形,答案是
有多少种方法可以从26个字母的英语字母表中选择一个5个字母的单词,这些单词被认为是相同的字谜?
观察一下,由于字谜被认为是相同的,我们感兴趣的特征是每个字母在单词中出现的次数(忽略字母出现的顺序)。为了将其转化为星号和横条问题,我们考虑将5写成26个整数的和 而且 在哪里 次数是字母吗 是选择, 次数是字母吗 被选中,等等。
因此, = 5和 = 26。
然后根据星形和柱形,5个字母的单词数为
对于某些问题,星形条法并不能立即应用。在这些情况下,问题的解决方案必须首先映射到另一个问题的解决方案,然后可以通过星形和条形来解决。我们用下面的例子来说明一个这样的问题:
有多少正整数的有序集合 是否存在这样的情况 为 而且
由于不平等,这个问题不能直接映射到星条框架。接下来,考虑整数之间的双射 满足条件和整数 令人满意的 而且
现在通过设置 为 ,我们想要找到整数的集合 这样 而且
由星形和横条,这等于 .
尝试以下问题: