组合

组合是计数和排列的数学。当然，大多数人都知道如何计数，但组合学应用数学运算来计数那些太大而无法用常规方法计数的数量。

组合学特别有用计算机科学．组合学方法可以用来估计计算机算法需要多少运算。组合学对于研究离散概率．在均匀概率实验中，组合学方法可以用来计算可能的结果。

主要文章:规则的产品和总和规则

组合学经常关注事物是如何排列的。在这种情况下，an安排是一种对象可以进行分组。有关安排，最基本的规则是产品的规则和规则。这些规则管理如何使用乘法和加法的操作分别计数安排。

乘积法则决定了如何使用乘法计数排列。

规则的产品

如果有 $米$安排事情的方法，然后 $n$在那之后安排其他东西的方法，然后安排这两个东西的方法的数量是 $米\ n次。$

规则管理如何使用添加计算安排。这些规则的语言似乎相似。主要区别在于，与产品规则计算的安排是连续或同时进行的，而与金额的规则计数的安排不能连续地或同时地发生

总和规则

如果有 $米$安排事情的方法，有 $n$安排其他事情的方式，这些安排不可能同时发生，那么安排其中任何一种方式的数量是 $M + N。$

应用这些简单的规则可以解决组合学中的许多问题。事实上，组合学中更高级的公式只是这些规则的扩展。计算问题的一个潜在陷阱是重复计算的概念。重复计算重复计算同一对象或排列的错误。

1到100之间的整数在7或13之间可被划分？

---

1到100之间能被7整除的整数的个数是 $左\ lfloor \ frac {100} {7} \右\ rfloor = 14。$
1到100之间的整数的数量由13可分开 $\ \ lfloor \离开压裂{100}{13}\ \ rfloor = 7。$

这似乎是在这里适用的金额规则，并且答案将是 $7 + 14 = 21。$然而，这将是一个错误双重计数．必须考虑到一个整数可以同时被7和13整除。

1到100之间的整数的数量可分离为7和13是 $\左\ lfloor \ frac {100} {7 \ times 13} \右\ rfloor = 1。$

为了解释重复计算的原因，将这个数字从原来的答案21中减去。因此,有 $20.$1和100是由7或13整除之间的整数。 $_\正方形$

将重复计算的元素“移除”的过程用包容和排斥的原理．

主要文章:置换和组合

参见:二重传系数

一个排列是根据顺序对物体进行的排列。在组合学中，重点通常是计算元素的个数集排列。

多少排列是有字母 $ABC}{\文本吗?$

---

排列是

$\ begin {array} {lll} {lll} \ text {abc} \ text {acb}＆\ text {bac} \\ \ text {bca} \\ \ text {bca}＆\ text {cab}＆\ text {cba。} \ neg {arrow}$

有 $\盒装{6}$排列。 $_\正方形$

给定一组 $n$不同的对象，让这些对象的排列集合是 $P。$然后,

$| | = P n !，$

在哪里 $！$是阶乘操作员。

有 $n$方式可以选择顺序的第一个对象。然后，有 $N-1$按顺序选择第二个物体的方法。这种情况会一直持续下去，直到只有 $1$方法选择最后一个对象的顺序。根据乘积法则，排列的次数 $n$对象是

$N * (N -1) * (N -2) * (cdots) * 2 * 1= N !\ _ \广场$

还可以考虑对象子集的置换。

有多少排列来自2个字母 $文本\ {ABCD} ?$

---

排列是

$文本\开始{数组}{微光}\ {AB} & \文本{广告}& \文本文本{英航}{BD} \ \ \ & \文本{DA} & \文本文本{AC} {DB} \ \ \ & \{公元前}& \文本文本{CA} {CD} \ \ \ & \文本{CB} {DC & \文本。} \结束{数组}$

有 $\盒装{12}$排列。 $_\正方形$

给定一组 $n$对象，让集合的排列 $k$这些物体是 $S.$然后,

$S | | = \压裂{n !} {(n - k) !}。$

一个组合是不考虑顺序的对象的排列。

给定一组 $n$不同的对象,让 $C$的组合的集合 $k$这些物体。然后,

$C | | = \ binom {n} {k} = \压裂{n !} {k (n - k) !}，$

在哪里 $\ binom {\ CDOT} {\} CDOT$是二项式系数操作员。

排列的数目 $k$对象集合中的对象 $n$对象是 $\ frac {n！} {（n-k）！}。$对于每个子集 $k$从一组对象 $n$物体，有 $k !$该子集的排列。因此，组合的数量 $k$对象集合中的对象 $n$对象是

$\ frac {n！} {（n-k）！} \ div k！= \ frac {n！} {k！（n-k）！} = \ binom {n} {k}。\ _ \ square$

二项式系数操作者接收，因为其应用到下面的二项式定理的它的名字。然而，这种操作对计算的组合数的广泛使用。

组合可用于在一个概率实验来算结果。这是当概率试验是均匀特别有用。在这种情况下，概率仅仅是一个组合数的比率。

主要文章:二项式定理

的二项式定理给出升高到正整数功率的二项式的多项式膨胀。

$\{对齐}开始(a + b) ^ n & = \ \ limits_总和{k = 0} ^ {n} \ binom {n} {k} ^ {n - k} ^ k \\ \\ &= \ binom {n} {0} ^ n + \ binom一^ {n} {1} {n} b + \ cdots + \ binom {n} {n} ab ^ {n} + \ binom {n} {n} b ^ n \{对齐}结束$

我们可以建立一个双射二项式的乘积之间 $n$以及组合 $n$对象。每个产品的结果 $一个^ {n-k个} b ^ķ$对应于组合 $k$对象的 $n$对象。因此,每个 $一个^ {n-k个} b ^ķ$多项式展开中的项由的和导出 $k \ binom {n} {}$产品。 $_\正方形$

这些都对扩张 $（X + Y）^ n的$对于小值 $护士:$

$\ begin {对齐}（x + y）^ 0＆=＆1 \\（x + y）^ 1＆=＆x + y \\（x + y）^ 2＆=＆x ^ 2 + 2xy + y^ 2 \\（x + y）^ 3＆=＆x ^ 3 + 3x ^ 2y + 3xy ^ 2 + y ^ 3 \\（x + y）^ 4＆=＆x ^ 4 + 4x ^ 3y + 6x^ 2y ^ 2 + 4xy ^ 3 + y ^ 4 \\＆\ vdots＆\ neg {aligned}$

当我们看上面表达式中的系数时，我们会发现以下模式:

$1 \\ 1 \四1 \\ 1 \四2 \四1 \\ 1 \四3 \四3 \四1 \\ 1 \四4 \四6 \四4 \四1 \\ 1 \四5 \四10 \四10 \四5 \四1 \\ \ cdots$

这叫做帕斯卡三角形．

尽管上面的公式仅适用于向整数功率提升的二项式，但是可以应用类似的策略来查找升高到整数功率的线性多项式的系数。

主要文章:入选和排除原理

的包容和排斥的原理介绍如何计算字符串中的元素数量和集合的工会。

1到1000(包括1000)之间有多少整数能被3、5或7整除?

---

能被3整除的整数数是 ${1000}{3} \right\rfloor = 333。$
能被5整除的整数数是 $\left\lfloor \frac{1000}{5} \right\rfloor = 200。$
可分解的整数数由7是 $\左\ lfloor \压裂{1000} {7} \右\ rfloor = 142。$

整数是被3整除和5是整除15的整数的数目整除15个是 $\左\ lfloor \压裂{1000} {15} \右\ rfloor = 66。$
能被3和7整除的整数能被21整除。能被21整除的整数数是 $\左\ lfloor \压裂{1000} {21} \右\ rfloor = 47。$
可分解的整数5和7可被35可分开。可分离的整数数由35可分开 $\左\ lfloor \ frac {1000} {35} \ \ \ rfloor = 28。$

能被3、5和7整除的整数能被105整除。能被105整除的整数数是 $\左\ lfloor \ frac {1000} {105} \右\ rfloor = 9。$

包含和排除原则给出了能被3,5或7整除的集合的大小:

$333 + 200 + 142-66-47-28 + 9 = 543。$

有 $\盒装{543}$可被3、5或7整除的1到1000(含)之间的整数。 $_\正方形$

主要文章:着色(奇偶校验参数)

参见:霍尔婚姻定理

染色是一种策略，用于确定是否有可能进行瓦片排列。与其详尽地搜索满足问题需求的排列，有时测试所有排列的颜色奇偶性更有效。颜色平价是指所有可能排列的着色方案必须与所期望排列的着色方案相匹配。

下面的图形可以平铺吗 $1 \ * 2$多米诺骨牌?

---

如果一个人试图找到完全平铺多米诺骨牌图的安排，似乎好像它是不可能的。然而，测试每一种可能的安排是困难的。相反，考虑棋盘配色方案。

一个 $1 \ * 2$多米诺骨牌将具有类似着色1黑色瓷砖和1个白色瓷砖。用多米诺骨牌铺设图形，必须有相同的黑白空间。然而，右图中的数字包含11个黑色瓷砖和13个白色瓷砖。因此，不可能平铺。 $_\正方形$

主要文章:图论理论

图论是研究图形，这是连接节点的集合。

的基本图3循环

在组合中，一个可以研究的曲线图的遍历和图形的排列。

证明不可能沿着每条路径精确地移动一次来遍历下面的图。任何顶点都可以被选为起始顶点或结束顶点，顶点可以被传递不止一次。

---

假设在图上每条路径只走一次是可能的。考虑每个顶点经过多少次。每当一个顶点被输入时，它也会被退出。因此，如果每条路径只经过一次，那么每个顶点的路径数量应该是偶数。如果我们的图有不同的起始顶点和结束顶点，则有一个例外。这些顶点的路径数量应该是奇数。只有一个起始顶点和一个结束顶点。然而，上面的图有4个顶点，它们的路径数量是奇数。

因此，不可能通过沿每条路径行进恰好一次遍历上述曲线图。 $_\正方形$

主要文章:递归

参见:线性递归关系

递归将认识到如何一层一层地建立解决小问题的方案来解决任何问题的过程形式化，无论问题有多大。递归对于组合学中推导公式特别重要。

给出一个表达式 $S_n， (n=1, 2, 3, ldots)，$其表示的串的数目 $n$字符，单独组成 $文本\{一},{B} \文本,$和/或 $\ text {c}，$不包含连续的字符是相同的。

---

首先考虑长度为1的字符串：

$\开始{阵列} {CCC} \文本{A}＆\文本{B}＆\文本{C}。\ {端阵列}$

所以, $S_1 = 3。$现在考虑长度为2的字符串:

$\开始{阵列} {LL} \ {文本AB}＆\文本{AC} \\ \文本{BA}＆\文本{BC} \\ \文本{CA}＆\文本{CB} \ {端阵列}$

所以, $S_2 = 6。$现在考虑长度为3的字符串:

$\ begin {array} {llll} {llll} \ text {abc}＆\ text {aba}＆\ text {aca}＆\ text {acb} \\ \ text {bab}＆\ text {bac}＆\ text {bac}＆\ text {bca}＆\ text {bcb} \\ \ text {cab}＆\ text {cac}＆\ text {cba}＆\ text {cbc。} \ neg {array}$

所以, $s_3 = 12。$很明显，串数与每个连续角色加倍。这是因为下一个字符有2个选项，与最后一个字符不同。这可以通过以下方式表示：

$S_n = 3 \ cdot 2 ^ {n}。\ _ \广场$

文章:

• 不同的对象为不同的垃圾箱

• 不同的对象进入相同的容器

• 相同的物体为不同箱柜

• 相同的对象进入相同的容器

一个分配将对象分组到一个容器中是一种将集合中的每个对象分组到一个容器中的安排。

分布独特的物体注意在每个容器中哪些对象被组合在一起。相反，分布相同的对象不考虑哪个对象将其分组在一起，仅适用于每个箱中的对象有多少。

分布在不同的垃圾箱注意垃圾箱的顺序。相反，分布为相同的箱子不考虑容器的顺序，只考虑对象如何分组。

这些区别创建四种类型的分布到箱中的问题。正如在组合等问题，值得关注的通常是计数可能分布的数量。

在水族馆中，有一个慈鲷，四，金鱼和达尼奥。14种食物颗粒落入水族馆。如果所有颗粒都被吃掉，那么有多少可能的颗粒分布？

---

在这个例子中，“箱”是鱼，和“对象”被分布是粒料。每个箱子是不同的，因为它很重要，其鱼得到颗粒。每个对象是相同的，因为它并不重要的小球被消耗，只有多少消耗。请注意，这是可能的鱼接受0颗粒。解决的有效途径相同的对象放入不同的容器中问题是申请a星星和酒吧策略。

${\ color {＃d61f06} \ star \ star} \ mid {\ color {＃3d99f6} \ star \ star \ star \ star} \ mid {\ color {＃oc7300} \ star \ star \ star \ star} \ min{\ color {＃20a900} \ star \ star \ star \ star}$

上面的排列表示慈鲷有2粒(红色)，四环鱼有4粒(蓝色)，金鱼有4粒(橙色)，达尼奥有4粒(绿色)。图中有14颗星星和3根横杆，总共有17个物体。我们可以得到任何通过在17个可能的位置中为棒选择3个位置来分配小球。因此，小球的分布数为

$\ binom{17}{3} = 680。\ _ \广场$

主要文章:整数分区

一个整数分割，有时简称为a划分，是等于给定整数正整数的总和。在组合中，值得关注的是在计数的整数的多个分区是如何存在的。

有多少分区？

---

8的分区如下:

$\ begin {array} {CCCC} 8和7 + 1和6 + 2＆5 + 3 \\ 4 + 4 + 4和6 + 1 + 1 + 2 + 1和4 + 3 + 1 \\ 4 + 2 +2＆3 + 3 + 2＆5 + 1 + 1 + 1 + 1 + 2 + 1 + 1 \\ 3 + 3 + 1 + 1＆3 + 2 + 2 + 1＆2 + 2 + 2 + 2 + 2 + 2和4+1+1+1+1\\ 3+2+1+1+1 & 2+2+2+1+1 & \hspace{5mm} 3+1+1+1+1+1\hspace{5mm} &\hspace{5mm} 2+2+1+1+1+1\hspace{5mm} \\ \hspace{5mm} 2+1+1+1+1+1+1 \hspace{5mm} & \hspace{5mm} 1+1+1+1+1+1+1+1\hspace{5mm} \end{array}$

有 $\盒装{22}$8的分区。 $_\正方形$

列出所有可能的分区可能是一个挑战。没有人知道闭合形式表达为整数的分区数 $n。$幸运的是，有一个双射的分区和分布之间相同的对象放入相同的容器中．同样的解决问题的方式可以采取。

主要文章:鸽子洞原理

的鸽子洞原理描述至少一个二进制位必须如何，给定块的一个特定数目和放置到这些块的对象的更多数量的，具有多于一个的对象。

5个点被放置在一个单位等边三角形内。证明其中两个点的最大距离 $\ frac {1} {2}$从对方。

---

假设5中任意一对点，点之间的距离大于 $\ frac {1} {2}$．现在考虑的三角形分割成4个更小等边三角形。

注意，这些小三角形中两点之间的最大距离是 $\压裂{1} {2}。$的点可以被放置在每一个三角形（4个蓝点），使得每个点比 $\ frac {1} {2}$从其他方面来看。然而, $5 ^ \ text {th}$点(红色的点)必须与另一个点放在同一个三角形内。

因此，如果在一个单位等边三角形中放置5个点，那么其中两个点必须最多 $\ frac {1} {2}$彼此远离。 $_\正方形$

主要文章:矩形网走

一个步行格是沿着图从开始节点到结束节点的路径。在网格行走问题中，目标是找出可能路径的数量。

只向上或向右移动，从开始节点到结束节点有多少可能路径?

---

从起始节点到完成节点的任何路径都需要3个向上移动和5个右移动。考虑8个移动是一组不同的物体。然后，这些移动的任何组合，其中3个都是向上移动的移动将是有效的路径。因此，从启动节点到完成节点的可能路径的数量是

$\ binom{8}{3} = 56。\ _ \广场$

• 置换

• 组合

• 二项式系数

• 多项式定理

• 纽结理论

• 守着一个博物馆