计数工具二项式分解原理
鸽巢原理证明具有某种性质的事物的存在

本章内容

1.基本原理
2．排列组合
3.产生排列组合的算法
4.广义排列组合
5.二项式系数和组合恒等式
6．鸽巢原理

4.1 基本原理

有2种开胃食品，3道主菜，4种饮料
由一道主菜和一种饮料可以组成多少种不同的正餐?
由一开胃食品、一道主菜和一种饮料可以组成多少种不同的正餐?

乘法原理

如果一种活动由连续t步组成，第一步有n₁种方法，
第二步有n₂种方法,
……
第t步有n_t种方法，
那么不同的活动数目有n₁ * n₂ …n_t
当一活动由连续几步组成时,把每一步的方法数乘起来
例：

• 如果不允许重复，用ABCDE可以组成多少种长度为4的字符串?
• 如果不允许重复，用ABCDE可以组成多少长度为4的字符串?其中有多少是以B开头的?
• 如果不允许重复，用ABCDE可以组成多少长度为4的字符串?其中有多少不是以B开头的?

{x₁,x₂,. . .，x_n}的子集的数目一个子集可以由n步构成:选或不选x₁,选或不选x₂，...,选或不选x,共有n个（2 * 2 * ...* 2）种可能性=子集数2ⁿ个

①在A中(且在B中)
②在B中(但不在A中，在B-A中)
③不在B中(不在A中，在X-B中)
n个(3 * 3 ...*3)种可能性,3ⁿ种
例：用101或111打头的8位串有多少?
101打头的8位串有2⁵ = 32
111打头的8位串有2⁵ = 32
用101或111打头的8位串有32+32=64个

加法原理

假设x₁,...X_t是集合且第i个集合有n个元素，如果X₁,. ..X_t两两不相交，则可以从X₁或X₂或...X_t选择元素的可能性有 n₁+ . . . +n_t种
当被计数的元素可以被分解到不相交的子集时，可将每个子集的元素数相加得到总的元素数。
问题：分不清到底什么时候用加法原理还是乘法原理，多练习+对每个问题的认真思考。
例：
5本不同的计算机书
3本不同的数学书
2本不同的美术书
选择2本不同类的书有多少方法?
C₅¹*C₃¹+C₅¹*C₂¹+C₃¹*C₂¹

---

由A、B、C、D、E、F6人委员会要选一个主席，一个秘书，一个书记。有多少种选法?
如果A或B必须是主席，有多少种?
如果E必须任3职之一，有多少种?
如果D和F必须任职，有多少种?
习题：P170 4，10，16，27

---

4.2 排列和组合

A、B、C、D竞选主席，为了使选票上人名顺序不影响选举，故设计不同的选票，问应有多少种?
n个元素有n！个排列。
字母ABCDEF中有多少个包含DEF的排列?
6个人围坐在圆桌有多少种坐法?

排列 事物的有序叫做排列

n个不同元素x₁... x_n的一个r排列就是{ x₁,... ，x_n}的一个r元子集的排序，记为 P(n, r)
从10个人中选择主席、副主席、书记、副书记，有多少种?
10*9*8*7 =5040
7个男，5个女的排队，如果不能有2个女的排在一起，有多少种方法?
男的有7!
女的有P（8,5）
共有7!*P（8,5）

组合 不考虑顺序的对象的选取叫做组合

给定X={x₁, ...x_n}
X的一个r-组合就是X的包含r个元素的一个无序选择
一个包含n个不同元素的r-组合记为C(n,r)或 [ ⁿ_r]
例子：
5个学生想和校长谈奖学金的事，校长办公室安排3个人去谈，问有多少种方法从5选3?

定理

例：由10个人选出一个3人委员会有多少中方法?
10! C(10，3)= 10! /7!*3!=120
例：从5个女的,6个男的,选出2个女生3个男生有多少种方法?
C(5,2) * C(6,3)
例：52牌 ♣ ♠ ♡ ♢

• 选5张牌(无序)有多少种选法?
• 5张为同一种花色有多少种?

• 5张中3张为一个面额，2张为另一个面额有多少种?
  C(52，5)
  4*C(13，5)
  13 * 12 * c(4，3) * C(4，2)

  
  C(2n,n)
  

  习题：P183 7，10，37，41

4.3 产生排列组合的算法

乐队录取n个节目，时间为t₁,.. . ,t_n带子可以录取C秒，希望包含尽可能多的节目，即从{1,. ..n}中选择一个子集{i₁,. . ., i_k}，使得
^k_j=1 ∑ t_ij~ 尽可能大，但又不大于C。

字典序

dog < doghouse / gladiator < gladiolus
O=s₁,s₂,... , s_p;
β=t₁,t₂,. . . ,t_q
定义在{1, .. .,n}上的字符串，若α<β iff
(a) p <q and s_i=t_i, i=1, . . .,p
(b)对于某些i, s_i ≠ t_i,并且对于最小的i, s_i < t_i

{1,...,n}的r组合

列出{1,2,. . . ,n}的所有r组合
r组合{x₁,. . . ,x_r}列成s₁, ... ,s_r的形式，
其中s₁< s₂< ...< s_r{x₁, . . . ,x_r} = {s₁,. . . , s_r}

4.4 广义的排列组合

有重复元素、 允许重复元素、 多重集的排列组合问题
例：用下列字母可以组成多少个字符串? M I S S I S S I P P I
解：一共11个字符串，很显然全排列是11！
对于P：C（11,2）
S：C（11-2,4）=C(9,4)
I:C(9-4,4)=C(5,4)
M:C(1,1)
共有C（11,2）C（9,4）C（5,4）C（1，1）种
C₁₁² C₉⁴ C₅⁴ C₁¹=11!/2!/4!/4!/1!

定理

假定一个n项序列S包含1类的n₁个相同的对象，2类的n₂个相同的对象,..., t类的n_t个相同的对象,则排列数为

例题：

1、在3个学生中分8本书，如果包(B)得到4本书,邵(S)和马(M各得到2本书,有多少种可能? 8!/4!/2!/2!
C(8,4) C(4,2) (C2,2)=C₈⁴ C₄² C₂²
2、考虑3本书(计算机,数学、历史),每本书图书馆有6本拷贝,选择6本书有多少种可能?
排列用 | 和* 来表示所有可能的书籍选择情况。
解：有6本书用6个*号，3个类用2个| 分开，故做一个6个" * "和2个" | "的一个排列组合。
因此一共有8个符号，C₈² 代表分好了3个类， C₆⁶代表剩余6个位置6本书的全排列。

---

如果X是一个t元集合,则从X中允许重复地选择k个无序元素的方法数为 C(k+t-1, t-1)=C(k+t-1,k)。
3、有红、绿、蓝三个颜色的球若干，随便选8个球，有多少种方法。如果每种球至少选一种，有多少种选法？
解： 第一问：C（8+3-1,3-1）=C（10,2）=45
第二问：C（8-3+3-1,3-1）=C(5+3-1,3-1)= C(7,2)=21
4、12本相同的数学书分给4个学生有多少不同的方法?
解：C（12+4-1,4-1）
5、满足x₁+x₂+x₃+x₄=29的非负整数解有多少种?
解：C（29+4-1，3-1）
6、满足x₁+x₂+x₃+x₄=29且x₁>0, x₂>1,x₃>2, x₄ >=0的整数解有多少?
解：先给x₁分配1，给x₂分配2，给x₃分配3，再重排
C（29+4-1-6，4-1）
习题：P199 1,5,12,33

4.5 二项式系数

(a+b)ⁿ=(a+b)(a+b)…(a+b)
从n个因式的每一个中选择a或b,连乘并加起来，就得到展开式。
(a+b)³=(a+b)(a+b)*(a+b)
==aaa+aab+aba+abb+baa+bba+bbb
a^n-kb^k k个因子中选b,n-k个因子中选a,可能性为C(n,k),即该项在展开式中出现C(n,k)次。
(a+b)ⁿ=C(n,0) aⁿ b⁰+C(n,1) a^n-1 b¹+C(n,2) a^n-2 b²+...+C(n,n-1) a¹ b^n-1+C(n,n) a⁰bⁿ

4.6 组合恒等式

组合方法 杨辉三角

行数即系数

定理 C(n+1,k)=C(n,k-1)+ C(n,k)

习题P204 1,3,10

4.7 鸽巢原理

第一种形式：
如果n只鸽子飞入k个巢且k<n,则某些巢至少有两只鸽子。
例：10个人拥有姓张、王、李and名 三、四、五，
则至少有两个人的名字是一样的?
解：10个人就是鸽子，姓是鸽子，名是巢。
第二种形式
如果f是一个从有限集合X到有限集合Y的函数且|X|>|Y|，那么对某些X中的(不相等)元素x₁, x₂，有f(x₁)=f(x₂)
例：如果选择151门不同的课程并用1-300之间的数编号，则必有两门课程的编号是连续的，如121、122。
解：令课程编号为c1,c2,. . . ,c151
考虑上述编号和c1+1,. .. ,c151+1共302个数
值1-300+1共301个必有ci=cj +1
例：一份由80项(标记为有用、无用)物件构成的目录表,其中45项有用,证明表中至少有两个有用的项相隔9?
13 22 69 78
解：
ai表示第i个有用项的位置a1, a2,. . . ,a45
a1 + 9,. . . ,a45+9共90项
值范围1-80+9共89个 至少两个一样
ai = aj +9即 ai-aj=9
第三种形式
如果f是一个从有限集合X到有限集合Y的函数且|X|=n,|Y|=m，令K=[n/m],那么X中至少有k个(不相等)元素x1,2 ,.. . ,xk满足
f(x1)=f(x2)=...=f(xk)。
例：证明在6个人中,必有3个人互相相识或有3个人互相不相识。
解：P1, P2,....P6
(P1, P2),(P1,P3),... ,(P1,P6)
具有值相识或不相识,至少有5/23有同一值,设为
(P1,Pi) (P1,Pj)(P1,Pk)
若相识，考虑(Pi,Pj)(Pi,Pk)(Pj,Pk)若有一相识，则与P1一起,有三人互相相识，否则得到3人互不相识
若不相识,考虑(Pi,Pi)(Pi,Pk)(Pi,Pk),若都是相识，得到3个互相相识的人，否则有一不同，加上P1，得到3互不相同的人
习题：P208,1,5,24