第16章 计数原理

数学学习 · 爱知数学讲义

18
本章目录 · 14 节

学习目标

掌握分类加法、分步乘法;会用排列组合公式;会写二项式定理的通项。

16.1 两个基本原理

做一件事,有 类办法,第 类有 种,各类两两互斥(用了这一类就不会同时算成那一类),那么总方法数是 。这是分类加法原理。

做一件事要分成 个步骤,第 步有 种方法,那么总方法数是 。这是分步乘法原理。

【例1】从甲地到乙地,坐火车有 班、汽车有 班;若必须先到丙地(去丙地有 种走法,再从丙地到乙地有 种),分别有多少种走法?

解:

直接走是分类:火车或汽车, 种。

经丙地是分步: 种。

16.1.1 小结

先问自己:是分类还是分步。分类加,分步乘。可以先分类再在每一类里分步,变成先加后乘。

16.2 排列与组合

排列:从 5 人里排 3 个座位,座位有顺序 5 种 4 种 3 种 相乘:5×4×3。若不问顺序,再除以 3×2×1,变成组合
从 人里排 个位置:第一格 种,第二格 种,第三格 种,相乘就是 。若不问顺序,再除以 把同组的不同排法抹掉。

个不同元素中取出 个(),按顺序排成一列,叫做排列。第一种有 种选法,第二种 种,……,第 种 种,故 特别地 。规定 。

如果不看顺序,只问取出的是哪 个,叫做组合。每 个元素对应 个不同排列,所以 有对称性 ,以及 。

相邻问题常用捆绑法:把相邻的先绑成一个再排。不相邻常用插空法:先排其余的,再在空位里插。有限制时先安排特殊元素或特殊位置。

【例2】从 人里选 人站成一排有多少种站法?若只选 人组成小组、不问顺序呢?

解:

站成一排要看顺序:。

组成小组不问顺序:。也可以 。

【例3】 人站一排,甲乙必须相邻有多少种站法?甲乙不能相邻呢?

解:

捆绑:甲乙绑成一块,这一块内部 种顺序,与另外 人共 个单元排列:。

不相邻:先排另外 人有 种,形成 个空(含两端),从中选 个空插甲乙:。也可用总排法减相邻:。

说明:相邻先绑,不相邻先排其余再插空。两种算法对得上,才比较放心。

16.2.1 小结

本节抓住「排列与组合」。 个不同元素中取出 个(),按顺序排成一列,叫做排列。对照例题把公式用一遍。

16.3 二项式定理

把 展开,每一项都是从 个括号里各取 或 相乘。取 个 (因而取 个 )的方式有 种,所以 第 项(从 数起)是 注意下标是 ,不是 。

1 11 121 1331 14641 杨辉三角:每个数等于肩上两数之和,也是组合数 C(n,k)
杨辉三角(帕斯卡三角):每数等于肩上两数之和,第 行就是 。

令 ,系数和 。

【例4】写出 的展开式,并求所有二项式系数的和。

解:

到 :。

系数和 。

【例5】 的通项为什么写成 而不是 ? 与 各是多少?

解:

从 取到 ,对应第 项到第 项,所以第 项含 。

,。

【例6】求 中 的系数。

解:

通项 。

时系数 。

说明:先对上 里的 ,再把常数 乘进系数。不要只写 。

16.3.1 小结

本节抓住「二项式定理」。把 展开,每一项都是从 个括号里各取 或 相乘。对照例题把公式用一遍。

16.4 隔板法(扩展)

相同的物品分到不同的盒子里,用隔板法最好懂:先把物品排成一排,再用隔板把位置切开。允许空盒和不许空盒,隔板的块数一样,物品那边是否先“每个盒子放一个”不同。

隔板法:8 个相同苹果放进 3 个盘子,允许空盘 ○ ○ ○ ○ | ○ ○ | ○ ○ 8 个苹果排成一排,再插入 2 块隔板,把位置分成 3 段 一共 8+2=10 个位置,选 2 个放隔板:C(10,2) 一般:n 个相同物品进 k 个盒子,方法数 C(n+k−1, k−1)
圆点是苹果,竖线是隔板。隔板插在不同空档,就分成不同的盘。

16.4.1 隔板法

定理(隔板法)把 个相同物品分成 组(组与组有区别)。允许空组时,方法数是 ;每组至少一个时,先各放 个,剩下 个按允许空组来分,方法数是 (需 )。

为什么允许空组是 :把 个物品和 块隔板排成一排,一共 个位置,从中选 个放隔板。

【例7】 个相同苹果放进 个不同盘子,允许空盘有多少种放法?不允许空盘呢?方程 ( 是非负整数)的解数是多少?

解:

允许空盘:。

不允许空盘:先各放 个,剩 个允许空:。或直接 。

非负整数解的个数就是允许空盘的放法,也是 。正整数解是 。

说明:先问盘子是否有区别、能不能空。相同物品、不同盒子,才用隔板。物品不同就该改用排列。

16.4.2 小结

相同物品进不同盒子用隔板。允许空:;不许空:先各放一个。

16.5 本章总结

这一章一共 4 节。合上书应能用自己的话答出下面各节的要点,再去做练习。

16.1 两个基本原理:先问自己:是分类还是分步。分类加,分步乘。可以先分类再在每一类里分步,变成先加后乘。

16.2 排列与组合:本节抓住「排列与组合」。 个不同元素中取出 个(),按顺序排成一列,叫做排列。对照例题把公式用一遍。

16.3 二项式定理:本节抓住「二项式定理」。把 展开,每一项都是从 个括号里各取 或 相乘。对照例题把公式用一遍。

16.4 隔板法(扩展):相同物品进不同盒子用隔板。允许空:;不许空:先各放一个。

贯通全章:先问分类还是分步,再问看不看顺序。二项式通项注意是第 项。相同物品进不同盒子用隔板。

把各节小结连起来复述一遍,对照学习目标查缺,再进入易错与练习。

16.6 易错

误:组合题用了排列。正:不问顺序用组合,问顺序用排列。

误:分类与分步搞反。正:分类加,分步乘。

误:二项式通项写成 。正:第 项是 。

误:。正:。

误:隔板法用于不同物品。正:物品必须相同,盒子(变量)才互相区别。

误:允许空盘仍用 。正:允许空是 ,不许空才是 。

16.7 练习

先独立完成,再对照答案。看错在概念、运算、图形还是推理。

1. 分类用什么运算?

2. 分步用什么运算?

3. 排列与组合的差别?

4. 对吗?

5. 等于什么?

6. 二项式系数之和是什么?

7. 通项 的公式?

8. 等于什么?

9. 由排列如何得到组合?

10. 捆绑法用于哪类问题?

11. 插空法用于哪类问题?

12. 有限制条件时通常先安排什么?

13. 隔板法用于哪类问题?

14. 个相同苹果进 盘、允许空盘?

15. 方程 非负整数解的个数?

16.8 答案与解析

显示答案

1. 加法。

2. 乘法。

3. 排列计顺序,组合不计顺序。

4. 对。选 个留下与选 个去掉是同一件事。

5. 。

6. ,即 。

7. 。

8. 。

9. 再除以 ,把顺序抹掉。

10. 某些元素必须相邻。

11. 某些元素不能相邻。

12. 特殊元素或特殊位置。

13. 相同物品分到不同盒子。

14. 。

15. ,即 。