排列组合归纳总结

1 排列 组合及二项式定理排列 组合及二项式定理 一 计数一 计数 分类加法计数原理和分步乘法计数原理分类加法计数原理和分步乘法计数原理 1 分类加法计数原理定义分类加法计数原理定义 完成一件事 可以有 n 类办法 在第一类办法中有 m1种方法 在第二类办法中有 m2种方法 在第 n 类办法中有 mn种 不同的方法 那么 完成这件事情共有 N m1 m2 mn种不 同的方法 2 分步乘法计数原理定义分步乘法计数原理定义 完成一件事情需要经过 n 个步骤 缺一不可 做第一步有 m1 种方法 做第二步有 m2种方法 做第 n 步有 mn种方法 那 么完成这件事共有 N m1 m2 mn种不同的方法 3 分类加法计数原理与分步乘法计数原理区别与联系 分类加法计数原理与分步乘法计数原理区别与联系 联系 联系 都涉及完成一件事情的不同方法的种数 区别 区别 分类加法计数原理与分类有关 各种方法相互独立 用 其中的任一种方法都可以完成这件事 分步乘法计数原理与分步 有关 各个步骤相互依存 只有各个步骤都完成了 这件事才算 完成 4 分类分步标准分类分步标准 分类就是一步到位 1 类与类之间要互斥 2 总数完整 分步是局部到位 1 按事件发生的连贯过程进行分步 2 步与步之间相互独立 互不干扰 3 保证连续性 排列与组合排列与组合 1 排列 排列 1 排列定义 排列定义 从 n 个不同元素中 任取 m m n 个元素 按 照一定的顺序排成一列 叫做从 n 个不同元素中取出 m 个元素 的一个排列 2 排列数公式 排列数公式 A n n 1 n 2 n m 1 或写 m n AC m m m n 成 A 特殊特殊 An n n n n 1 m n n n m 3 特征 特征 有序且不重复 2 组合组合 1 组合定义 组合定义 从 n 个不同元素中 任取 m m n 个元素组成 一组 叫做从 n 个不同元素中取出 m 个元素的一个组合 2 组合数公式 组合数公式 C 或写成 m n m m m n A A n n 1 n 2 n m 1 m 2 C m n n m n m 3 组合数的性质组合数的性质 C C m nn mn C C C mn 1m nm 1n 4 特征 特征 有序且不重复 3 排列与组合的区别与联系 排列与组合的区别与联系 区别 区别 排列有序 组合无序 联系 联系 排列可视为先组合后全排 4 基本原则 基本原则 1 先特殊后一般 2 先选后排 3 先分类后 分步 排列组合的应用 常用方法 直接法 间接法 排列组合的应用 常用方法 直接法 间接法 1 抽取问题 抽取问题 1 关键 关键 特殊优先 2 题型 题型 把 n 个相同的小球 一次性的放入到 m 个不同的盒 子中 n m 每个盒子至少 1 个 有多少种不同的方法 Cmn 把 n 个相同的小球 依次性的放入到 m 个不同的盒 子中 n m 每个盒子至少 1 个 有多少种不同的方法 Amn 把 n 个相同的小球 放入到 m 个不同的盒子中 n m 每个盒子放球数目不限 有多少种不同的方法 mn 把 n 个不同的小球 放入到 m 个不同的盒子中 n m 每个盒子至少 1 个 有多少种不同的方法 Amn 把 n 个相同的小球 依次性的放入到 m 个不同的盒 子中 n m 每个盒子至多 1 个 有多少种不同的方法 Cn 1m 1 隔 板法 2 2 排序问题 特殊优先排序问题 特殊优先 1 1 排队问题 排队问题 对 n 个元素做不重复排序 Ann 对 n 个元素进行 其中有 m 个元素的位置固定 排列 m m n n A A 如果对 n 个元素进行 其中有 m 个元素的位置固定 k 个元素的位置 3 固定 排列 K K m m n n AA A 相邻问题 捆绑法 注意松绑 不相邻问题 a 一方不相邻 先排没要求的元素 再把不相邻 的元素插入空位 b 互不相邻先排少的在插入多的 2 2 数字问题数字问题 各位相加为奇数的 奇数的个数是奇数 各位相加为偶数的 奇数的个数是偶数 组成 n 为偶数 奇数 的数 特殊优先法 能被 n 整除的数 特殊优先法 比某数大的数 比某数小的数或某数的位置 从大于 小于 开始排 再排等于 3 3 着色问题着色问题 区域优先 颜色就是分类点 颜色优先 区域就是分类点 4 4 几何问题几何问题 点 线 面的关系一般均为组合问题 图中有多少个矩形 C62 C42 从 A 到 B 的最短距离 C83 5 5 分组 分配问题 分组 分配问题 非均分不编号 n 个不同元素分成 m 组 每组 元素数目均不相等 且不考虑各组间的顺序 不考虑是否分尽 3 21 2 1 1 CCC m mmn m mn m n 非均分编号 n 个不同元素分成 m 组 每组组元素数目均不相 等 且考虑各组间的顺序 不考虑是否分尽 A B 4 m m m mmn m mn m n A CCC 3 21 2 1 1 均分不编号 n 个不同元素分成 m 组 其中有 k 组元素数目均相等 且不考虑各组间的顺序 不考虑是否分尽 k k m mmn m mn m n A CCC 3 21 2 1 1 均分编号 n 个不同元素分成 m 组 其中有 k 组元素数目均相 等 且考虑各组间的顺序 不考虑是否分尽 m m k k m mmn m mn m n AA CC C 3 21 2 1 1 二 二项式定理二 二项式定理 1 定理 定理 a b n C anb0 C an 1b C an 2b2 C an rbr C a0bn r 0 1 2 0 n1 n2 nr nn n n 2 二项展开式的通项二项展开式的通项 Tr 1 C an rbr r 0 1 2 n 其中 其中 C叫做二项式系数 叫做二项式系数 r nr n 3 二项式系数的性质二项式系数的性质 对称性 与首末两端对称性 与首末两端 等距离等距离 两项的二项式系数相等 两项的二项式系数相等 即即 C C C C C C 0 nn n1 nn 1nk nn kn 最大值 当最大值 当 n 为偶数时 中间的一项的二项式系数为偶数时 中间的一项的二项式系数 取得最大值 当取得最大值 当 n 为奇数时 中间的两项的二项式系数为奇数时 中间的两项的二项式系数 相等 且同时取得最大值 相等 且同时取得最大值 各二项式系数的和各二项式系数的和 a C C C C C 2n 0 n1 n2 nk nn n b b C C C C C C C C C C C C 2 2n n 2 2n n 1 1 0 0n n2 2n n2 2r r n n1 1n n3 3n n2 2r r 1 1n n 1 1 2 2 二项式定理的应用 二项式定理的应用 1 1 求通项求通项 rrnr nr baCT 1 2 含含 xr的项 的项 项的系数 二项式系数 3 常数项 含常数项 含 xr的项中的项中 r 0 整数项 含 整数项 含 xr的项中的项中 r N N 有理项 有理项 含 含 xr的项中的项中 r Zr Z 无理项 含 无理项 含 xr的项中的项中 r r Z Z 4 4 项的系数和 项的系数和 1 1 已知多项式 已知多项式 f x a bx f x a bx n n a b 0 a a b 0 a0 0 a a1 1x ax a2 2x x2 2 a an nx xn n 1 2 C n n 1 2 C n n 2 C n n 5 a0 f 0 a0 a1 a2 an f 1 a b n a0 a1 a2 an f 1 a b n a0 a2 a4 2 1 1 ff a1 a3 a5 2 1 1 ff a0 a2 a4 2 a1 a3 a5 2 f 1 f 1 2 2 已知多项式已知多项式 f x a bx f x a bx n n a b 0 a a b 0 a0 0 a a1 1x ax a2 2x x2 2 a an nx xn n a0 f 0 a0 a1 a2 an f 1 a b n a0 a1 a2 an f 1 a b n a0 a2 a4 2 1 1 ff a1 a3 a5 2 1 1 ff a0 a2 a4 2 a1 a3 a5 2 f 1 f 1 3 3 已知多项式已知多项式 f x ax b f x ax b n n a b 0 a a b 0 a0 0 a a1 1x ax a2 2x x2 2 a an nx xn n 令令 g x g x 1 1 n n b ax b ax n n a0 f 0 a0 a1 a2 an f 1 a b n a0 a1 a2 an 1 n g 1 a0 a2 a4 2 1 1 ff 6 a1 a3 a5 2 1 1 ff a0 a2 a4 2 a1 a3 a5 2 f 1 f 1 4 4 已知多项式已知多项式 f x ax b f x ax b n n a b 0 a a b 0 a0 0 a a1 1x ax a2 2x x2 2 a an nx xn n 令令 g x g x 1 1 n n ax b ax b n n a0 f 0 a0 a1 a2 an f 1 a b n a0 a1 a2 an 1 n g 1 a0 a2 a4 2 1 1 ff a1 a3 a5 2 1 1 ff a0 a2 a4 2 a1 a3 a5 2 f 1 f 1 5 5 最