不同个数和不同重量的砝码是否能称出所有的重量？
十八级台阶
• 问题：欲登上第十八级台阶，如果规定 每步只能跨上一级或两级，共有多少种 不同的走法？ 递推公式： an an1 an2 , a1 1, a2 2 问题：你能写出这个公式的通项吗？ 本书将给出回答.
The Game of Nim
推论 n元集的全排列的个数为n !.
例 求由n个相异元a1 , a2 , 不相邻的全排列的个数.
第一章 排列与组合
§1 计数的基本原则
三条原则
• 相等原则 equivalence principle • 加法原则 addition principle • 乘法原则 multiplication principle
相等原则
设A，B是两个有限集，如果存在由A到B上 的一个一一对应（双射），则|A|=|B|，即， 若存在双射，
• Game rules:
There are k≥1 heaps of coins that contain, respectively, n1,n2,…nk coins The players alternate turns Each player, selects one of the heaps and removes at least one of the coins from the selected heap. The player who takes the last coin(s)-is the winner
定义 （全排列- total perm utati on） n元集A {a1 , a2 , , an }的n 排列称为n元集A的一个 , an 作成的一个全排列 全排列，亦称为由a1 , a2 ,
定理 设n, r ( n r )是正整数，以P ( n, r )表示n元集的 r 排列的个数，则 P ( n, r ) n( n 1)( n 2) n! ( n r 1) ( n r )!
组合数学 Combinatorial mathematics or combinatorics
参考书
• 组合数学习题解答，曹汝成，华南理工大学出版社； • 组合数学，Richard，机械工业出版社； • 应用组合数学(applied combinatorics), Fred S. Roberts, 冯速 译，机械工业出版社； • 组合数学，卢开澄，清华大学出版社。 • 组合数学，南基洙，高等教育出版社 • Introductory Combinatorics (fifth edition), Richard A. Brualdi
f : A B x
则
f ( x)
|A|=|B|.
例 n名选手参加乒乓球单打淘汰赛，需要打 多少场比赛才能产生冠军？
例 已知序列a1 , a2 , 需要做多少次比较？
, a100 , 从中找出最大者，试问
加法原则
设A是有限集，Ai A ( i 1, 2, A
k n
, k ),Aj (1 i j k ),
则 | A | | Ai |
i 1
例 设n为大于1的正整数，求满足条件 x y n 的所有的有序正整数对 ( x , y )的个数.
当
xk
时
| Ak | n k
n 1
1 k n1
于是
n( n 1) N (n k ) 2 k 1
问题
• • • • 存在性？ 如何构造？ 多少个？！！！ 最优？
内容简介
• 排列组合: permutation and combination • 容斥原理: inclusion and exclusion principle • 递推关系: recurrence relation • 生成函数: generation function • 整数分拆: partition of integer • 鸽笼定理: pigeonhole principle
例 把4个人分成两组，每组至少一人，求不同 的分组方法数。
1 2
3 2
4 3
乘法原则
已知做一件事要依次经过k 个步骤，且在已完 成前面i 1,(1 i k )个步骤的情况下，完成 第i 个步骤有ni中方法，则做这件事的方法共有
n .
i 1 i
n
例 求n元集A {a1 , a2 ,
, an }的子集的个数.
Step1 确定a1
Y/N
Step2 确定a2
Y/N
…
Y/N
Stepn 确定an
例 设自然数n ( n 2)的质因数分解式为
1 2 n p1 p2 k pk
求n的不同正约数的个数 .
解：n的每个约数可以表示为 其中 0 i i 答案
2 p11 p2 k pk
幻 方
17 8 3 4 1 5 9 6 23 7 4 2 10 11 是否存在3维幻方体？ 6 12 18 13 19 25 20 21 2 22 3 9 5 7 14 16 24 1 8 15
称重问题
• 实验室有1g砝码2枚，2g的3枚，4g的2枚， 问能称出哪些重量？各有几种方案？
G ( x ) (1 x x 2 )(1 x 2 x 4 x 6 )(1 x 4 x 8 ) 1 x 2 x2 x3 3 x4 2 x5 4 x6 2 x7 4 x8 x 9 4 x10 2 x11 3 x12 x13 2 x14 x 15 x 16
(
i 1
n
i
1)
§2 排列 permutation
• n元集合r-排列 • n元集的r-可重复排列 • 多重集的排列
n元集合r-排列
定义 ( r 排列) 设A是n元集，如果序列a1a2 ar中的r 个元都 ar 是n元集A的 属于A且彼此互异，则称序列a1a2
一个r 排列，并称ak (1 k r )是该r 排列的第 k 个元，或称ak 在该r 排列中排在第k 位.