整数方程-星形和柱形

组合学中经常出现的一个问题是，在计算将相同的物体分组的方法的数量时，例如将无法区分的球放入有标记的瓮中。我们讨论一种组合计数技术称为恒星和酒吧或球和骨灰盒为了解决这些问题，不可区分的物体用星形表示，分组用条形表示。

这允许我们将要计数的集合转换为另一个集合，这更容易计数。我们有一个双射，这些集合的大小相同。

考虑方程 $a + b + c + d = 12$在哪里 $a, b, c, d$非负整数。我们要求这个方程有多少个解。一开始，我们并不清楚该如何解决这个问题。一种方法是使用蛮力:确定一个变量的可能性，并分析其他变量的结果。但我们想要更好的，真正优雅的东西。我们使用上面提到的策略:通过显示双射将一个集合转换为另一个集合，从而使第二个集合更容易计数。

假设我们有 $15$我们放置的地方 $12$明星和 $3.$酒吧，每个地方一个物品。关键思想是这个位型代表方程的一个解。例如, $\{*|*****|****|**\}$代表解决方案 $1 + 5 + 4 + 2 = 12$．因为我们有 $1$星号，然后是横条(代表加号)，然后 $5$星星，同样是条，类似 $4$而且 $2$明星效仿。同样的, $\{|*****|***|****\}$表示解决方案 $0 + 5 + 3 + 4 = 12$因为我们一开始没有星号，然后是横条，推理和前面一样。

我们看到，任何这样的构型代表方程的一个解，而方程的任何解都可以转换成这样的星柱序列。我们已经在方程的解和构型之间建立了一个双射 $12$明星和 $3.$酒吧。所以我们的问题归结为“我们可以用多少种方式放置。 $12$明星和 $3.$酒吧 $15$的地方吗?”这和固定是一样的 $3.$的地方的 $15$到处都是星星。当然，我们可以在， $\ dbinom {15} {3}$的方式。所以方程的解的个数是 $\ dbinom{15}{3} = 455。$

星星和棒/球和瓮技术如下所述。

放置方式的数量 $n$无法区分球进 $k$标签骨灰盒是

$\ binom {n + k - 1} {n} = \ binom {n + k - 1} {k - 1}。\ _ \广场$

下面是上述定理的证明。

我们代表了 $n$球的 $n$相邻的星星，考虑插入 $k - 1$酒吧之间的星星把酒吧分成 $k$组。例如,对于 $n = 12$而且 $k = 5$，下面是一组的表示 $12$5个瓮中无法区分的球，其中瓮1、2、3、4、5的大小分别为2、4、0、3、3:

$* * | * * * * | \， | * * * | * * *$

注意，在分组中，可能会有空瓮。总共有 $n + k - 1$职位,其中 $n$是明星和 $k - 1$是酒吧。因此，放置方式的数量 $n$无法区分球进 $k$骨灰盒的标签是相同的选择方式的数量 $n$之间的位置 $n + k - 1$星星的空格，所有剩下的位置都作为柱。有很多方法可以做到这一点 $\ binom {n + k - 1} {n}。$ $_ \广场$

注意: $\ binom {n + k - 1} {n} = \ binom {n + k - 1} {k - 1}$可以解释为替代选择职位的方法有多少 $k - 1$酒吧和采取所有剩余的位置是星星。

查看以下示例:

有多少非负整数的有序集 $(a, b, c, d)$是否存在这样的情况

$A + b + c + d = 10 ?$

---

的解之间创建一个双射 $A +b+c +d = 10$长度为13的序列由10组成 $1$的和3 $0$换句话说，我们将每个解与唯一的序列相关联，反之亦然。

给定一组4个整数 $(a, b, c, d)$，我们创建的序列开始于 $一个$ $1$的，那么有一个 $0$,然后 $b$ $1$的，那么有一个 $0$,然后 $c$ $1$的，那么有一个 $0$,然后 $d$ $1$例如，if $(a, b, c, d) = (1,4,0,2)$，则关联序列为 $1 0 1 1 1 1 1 0 0 1 1$．现在，如果我们加上限制条件 $A + b + c + d = 10$，关联的序列将由10组成 $1$(从 $A, b, c, d$)和3 $0$'s(来自我们的手动插入)，因此总长度为13。

相反，给定一个长度为13，由10组成的序列 $1$的和3 $0$的,让 $一个$的初始字符串的长度 $1$在第一个之前 $0$),让 $b$是下一个字符串1的长度(在第一个和第二个之间) $0$),让 $c$的第三串的长度 $1$(在第二个和第三个之间 $0$),让 $d$的最后一个字符串的长度 $1$’s(在第三个后面 $0$)．这些值给出了方程的解 $A + b + c + d = 10$．

这种构造将每个解与唯一序列关联起来，反之亦然，因此给出了双射。

现在我们有了一个双射，这个问题就相当于计算长度为13，由10组成的序列的数量 $1$的和3 $0$的，我们用星柱法来计数。有 $13$我们选择的位置 $10$位置为1，其余位置为0。通过星星和酒吧，有 ${13 \choose 10} = {13 \choose 3} = 286$不同的选择。 $_ \广场$

注意:解决这个问题的另一种方法是生成函数．

本节包含示例和要尝试的问题。

求非负整数解的个数 $a + b + c + d + e + f = 23。$

---

我们有 $6$变量,因此 $5$+的迹象。所以根据星星和酒吧，答案是

$23 + 5 \ dbinom {} {5} = \ dbinom{28}{5} = 98280。\ _ \广场$

有多少种方法可以从26个字母的英语字母表中选择一个5个字母的单词替换，其中字谜的单词被认为是相同的?

---

观察一下，因为字谜被认为是一样的，我们感兴趣的特征是每个字母在单词中出现的次数(忽略字母出现的顺序)。为了将其转化为一个星柱问题，我们考虑将5写成26个整数的和 $c_A, c_B, ldots c_Y，$而且 $c_Z,$在哪里 $c_A$次数是字母吗 $一个$是选择, $c_B$次数是字母吗 $B$选择等。

因此, $n$= 5, $k$= 26。

然后用星号和横条表示5个字母的单词的个数

$\binom{26 +5 -1}{5} = \binom{30}{25} = 142506。\ _ \广场$

对于某些问题，星条旗法并不能立即应用。在这些情况下，问题的解决方案必须首先映射到另一个问题的解决方案，然后可以用星形和条形来解决。我们在下面的例子中说明了一个这样的问题:

有多少正整数的有序集 $(a_1, a_2, a_3, a_4, a_5, a_6)$是否存在这样的情况 $ai \组我$为 $I = 1,2， \ldots, 6$而且

$A_1 + a_2 + a_3 + a_4 + a_5 + a_6 \leq 100 ?$

---

由于不平等，这个问题没有直接映射到星形和条形框架。要继续，考虑整数之间的双射 $(a_1, a_2, a_3, a_4, a_5, a_6)$满足条件和整数 $(a_1, a_2, a_3, a_4, a_5, a_6, c)$令人满意的 $A_i \geq i, c \geq 0，$而且

$A_1 + a_2 + a_3 + a_4 + a_5 + a_6 + c = 100。$

现在,通过设置 $b_i = a_i-i$为 $I = 1,2， \ldots, 6$，我们要找到整数的集合 $(b_1, b_2, b_3, b_4, b_5, b_6, c)$这样 $b \geq 0, c \geq 0，$而且

$b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + c = 100 -(1 + 2 + 3 + 4 + 5 + 6) = 79。$

用星星和竖条表示，等于 $\ binom {79 + 7 - 1} {79} = \ binom {85} {79}$． $_ \广场$

尝试以下问题:

• 整数的分区

• 不同的物体放入相同的箱子

• 不同的对象放入不同的箱子