组合数学(26)

组合数学的基本概念与方法
汇报人：XX
目录
01
添加目录项标题
02
组合数学简介
03
组合数学的基本概念
04
组合数学的主要方法
05
组合数学中的问题与求解方法
06
组合数学与其他数学领域的联系
添加章节标题
PART 01
组合数学简介
PART 02
组合数学的定义
组合数学是研究离散对象组合性质和结构的数学分支
THANK YOU
汇报人：XX
特点：具有自相似性、层次性和规律性
定义：一个数学对象或系统通过自身子对象或子系统的递归方式进行描述或构造
组合数学的主要方法
PART 04
归纳法
定义：归纳法是从个别到一般的推理方法，通过对一些具体实例的分析，总结出一般规律。
应用：在组合数学中，归纳法常用于研究排列、组合、概率等问题，通过对具体问题的分析，归纳出一般性的结论。
注意事项：在应用反证法时，需要注意推理和演绎的严密性和准确性，避免出现逻辑错误。
构造法
定义：构造法是一种通过构造具体的实例或模型来解决问题的数学方法。
应用场景：在组合数学中，构造法常用于证明组合恒等式、求解组合问题等。
举例说明：例如，通过构造一个具体的组合模型来证明组合恒等式。
注意事项：使用构造法时需要注意构造的合理性和正确性，以及构造实例或模型的代表性和一般性。
数学归纳法
定义：数学归纳法是一种证明无限数学命题的推理方法，通过有限次验证和归纳推理来证明无限命题的正确性。
步骤：数学归纳法包括两个步骤：基础步骤和归纳步骤。基础步骤是验证命题在某个初始值成立，而归纳步骤则是假设在某个值成立，然后证明该假设对于下一个值也成立。

1.1 题 从{1，2，……50}中找两个数{a，b}，使其满足 （1）|a-b|=5； （2）|a-b| 5； 解： （1） ：由|a-b|=5 a-b=5 或者 a-b=-5， 由列举法得出，当 a-b=5 时，两数的序列为（6，1） （7，2）……（50，45） ，共有 45 对。 当 a-b=-5 时，两数的序列为（1，6） ， （2，7）……（45，50）也有 45 对。 所以这样的序列有 90 对。 （2） ：由题意知，|a-b| 5 |a-b|=1 或|a-b|=2 或|a-b|=3 或|a-b|=4 或|a-b|=5 或|a-b|=0； 由上题知当|a-b|=5 时 有 90 对序列。 当|a-b|=1 时两数的序列有（1，2） ， （3，4） ， （2，1） （1，2）…（49，50） ， （50，49）这样的序列有 49*2=98 对。 当此类推当|a-b|=2，序列有 48*2=96 对，当|a-b|=3 时，序列有 47*2=94 对，当|a-b|=4 时，序列有 46*2=92 对， 当|a-b|=0 时有 50 对 所以总的序列数=90+98+96+94+92+50=520 1.2 题 5 个女生，7 个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排 列？(c) 两男生 A 和 B 之间正好有 3 个女生的排列是多少？ 解： （a）可将 5 个女生看作一个单位，共八个单位进行全排列得到排列数为：8！× 5！ ， （b）用 x 表示男生，y 表示空缺，先将男生放置好，共有 8 个空缺， Y X Y X Y X Y X Y X Y X Y X Y 在其中任取 5 个得到女生两两不相邻的排列数： C（8，5）× 7！× 5！ （c）先取两个男生和 3 个女生做排列，情况如下： 6. 若 A，B 之间存在 0 个男生， A，B 之间共有 3 个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1．若 A，B 之间存在 1 个男生， A，B 之间共有 4 个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2．若 A，B 之间存在 2 个男生，A，B 之间共有 5 个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3．若 A，B 之间存在 3 个男生，A，B 之间共有 6 个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4．若 A，B 之间存在 4 个男生，A，B 之间共有 7 个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2 5．若 A，B 之间存在 5 个男生，A，B 之间共有 8 个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2 所以总的排列数为上述 6 种情况之和。 1.3 题 m 个男生，n 个女生，排成一行，其中 m,n 都是正整数，若 (a)男生不相邻 (m n 1) ; (b)n 个女生形成一个整体； (c)男生 A 和女生 B 排在一起； 分别讨论有多少种方案。 解：(a) 可以考虑插空的方法。 n 个女生先排成一排，形成 n+1 个空。因为 m n 1 正好 m 个男生可以插在 n+1 个空中，形成不相邻的关系。 则男生不相邻的排列个数为

根据清华远程教育课堂答案编辑整理,有改动，如果有错误，请指正。

――编者注 第一章习题1.证任一正整数n 可唯一地表成如下形式:,0≤a i ≤i,i ＝1,2,…。

证：对n 用归纳法。

先证可表示性：当n=0,1时，命题成立。

假设对小于n 的非负整数，命题成立。

对于n,设k!≤n ＜(k+1)!,即0≤n-k!＜k ·k!由假设对n-k!,命题成立，设，其中a k ≤k-1,，命题成立。

再证表示的唯一性：设, 不妨设a j ＞b j ,令j=max{i|a i ≠b i }a j ·j!+a j-1·(j-1)!+…+a 1·1! =b j ·j!+b j-1·(j-1)!+…+b 1·1!, ∑∑∑∑⋅-≥⋅-≥⋅>≥⋅-=⋅-!)(!!!!)(!)(i a bi a bi i j i a bj b a i ii ii ij j矛盾，命题成立。

另一种证法：令j=max{i|a i ≠b i}, 两边被(j+1)!除,得余数a j ·j!=b j ·j!,矛盾.2.证 nC(n-1,r)=(r+1)C(n,r+1).并给出组合意义。

证：)1,()1()!1()!1(!)1()!1(!)1(!)1()!1(!1),1(++=--⋅+⋅+=--⋅⋅+⋅+=--⋅-=-r n C r r n r n r r n r r n r r n r n n r n nC组合意义：等式左边：n 个不同的球，先任取出1个，再从余下的n-1个中取r 个； 等式右边：n 个不同球中任意取出r+1个，并指定其中任意一个为第一个。

显然两种方案数相同。

3.证。

证：由等式∑==⋅++⋅+⋅+=+nk knn xk n C xn n C x n C x n C n C x 02),(),()2,()1,()0,()1(两边求导并令x=1,即命题得证。

4.解：f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=8.
当n为偶数时：
f(n)=
当n为奇数时：
f(n)=
证明：因为f(n)为2行n列的多米诺牌覆盖的棋盘。
所以当n为偶数时：
当所有多米诺牌都竖放时，有 种方法。
当只有1个（并列2个）多米诺牌横放，其余都竖放时，则有 种方法。
(1)当切除的方格位于奇数与奇数的位置时，因为m为奇数则m-1为偶数，因此除去方格所在的行，分成的剩余棋盘的行必然为偶数。所以该部分一定能完美覆盖；而方格所在的行数为1，列数为n-1为偶数，所以该部分也能被完美覆盖。因此，当切除的方格位于奇数行奇数列交叉处时剩下的棋盘可被完美覆盖。
（2）当切除的方格位于偶数行与偶数列交叉处时，以被切除的方格为中心分割出其周围紧邻的方格作为一部分，则该部分一定能被完美覆盖，而剩余部分经过分割必然会分成行与列至少有一个偶数的各部分棋盘。因此该各部分也能被完美覆盖。因此，当切除的白色方格位于偶数行与偶数交叉处时，剩下的棋盘可被多米诺牌完美覆盖。
综合（1）（2），则如果切除棋盘上的任意一个白色方格，那么剩下的棋盘可被多米诺牌完美覆盖。
3.解：犯人不能得到自由。
假设囚室为一张8行8列且由黑白方格构成的棋盘，设左上角方格为白色，则对角位置方格也为白色。如果从左上角白色方格能够依次通过每个方格到达右下角的白色方格，则需要跨越63次，然而左上角白格到白格需要跨越偶数次。因此假设于事实矛盾。所以，犯人不能得到自由。
当只有2个（并列4个）多米诺牌横放，其余都竖放时，则有 种方法。
当只有3个（并列6个）多米诺牌横放，其余都竖放时，则有 种方法。
……
当最多只有n/2个（并列即：f(n)=
同理:当n为奇数时：