排列和组合排列和组合|离散数学

本文概述

排列
有限制的排列
重复对象的排列
循环排列
组合

排列将一组n个对象按给定顺序进行的任何排列称为“对象排列”。这些对象中任何r≤n的给定顺序的任何排列称为r置换或一次取r的n个对象的置换。
用P（n, r）表示P（n, r）=
【排列和组合】定理：证明一次取n个事物的排列数为n！
证明：我们知道

例如：4 x np3 = n + 1P3
解决方案：4 x
4（n-2）=（n + 1）4n-8 = n + 1 3n = 9 n = 3。
有限制的排列在不出现p个特定对象的情况下, 在n个不同对象中进行的排列次数r

在存在p个特定对象的情况下, 在r时获取的n个不同对象的排列数量为

示例：如果每个数字都以“ 30”开头而不重复数字, 那么使用数字0、1、2、3、4、5、6、7、8可以形成多少个6位数字？
解决方案：所有数字均以“ 30”开头。因此, 我们必须从剩余的7位数字中选择4位数字。
with以’ 30’ 开头的数字总数是7P4 = = 840。
重复对象的排列定理：证明nr给出了每次允许每个对象重复任意次数时, n个不同对象的不同排列数。
证明：假设允许重复对象, 我们必须用n个对象填充r个位置。
因此, 填充第一位的方式数为= n填充第二位的方式数= n … … … … … … … … … … … . … . … … … … … … … … … … … … ..填充第r位的方式数= n因此, 用n个元素填充r个地方的方式是= n。。 n … … … … .. r times = nr。
循环排列围绕一个圆进行的排列称为循环排列。

示例：以哪种方式可以将这些字母a, b, c, d, e, f, g, h, i, j排列成一个圆圈？
解决方案：（10-1）= 9！ = 362880
定理：证明n个不同对象的圆形排列数为（n-1）！
证明：让我们考虑K是所需的排列数。
对于K的每个这样的圆置换, 存在n个对应的线性置换。如前所述, 我们从循环排列中n个对象的每个对象开始。因此, 对于K个圆置换, 我们有K … n个线性置换。

组合组合是从一组给定对象中选择部分或全部对象的对象, 对象的顺序无关紧要。一次以nCr或C（n, r）表示的n个对象的组合数量。

证明：n个不同事物的排列数, 一次取r由下式给出

由于对象的排列顺序无关紧要, 因此, 对于r个事物的每个组合, 都存在r！安排, 即

示例：一位农民从一个有6头牛, 5头猪和8头母鸡的男人那里购买了3头牛, 2头猪和4头母鸡。找到农民拥有的选择数m。
农民可以选择C（6, 3）方式的母牛, C（5, 2）方式的猪和C（8, 4）方式的母鸡。因此, 选择数m为：