组合数的性质
计数问题知识网络
复杂的计数问题 简单的计数问题
组合数的性质
对称性 拆并性 增减性 可和性
计数原理型 排列组合型 十大题型
计数问题总述: 两理两数四原则 十大题型递推法
①
②
③
④
⑤
注①:分类加法及分步乘法计数原理:
化大为小是共性 顾名思义是区分
注②:排列数与组合数: 注③:①○先理后数②○先组后排③○特殊优先④○正难则反
类似于物理中的串联电路
说明
最终结果“分类” 用“加 法 最”终结果“ 分步”用“乘 “法分”类”要不重不漏;各类间要互斥独立
“分步”要连续完整;各步间要关联独立
两理两数四原则 十大题型递推法
1.阶乘: n!1 23 n
A 2.排列数: m n! n • (n 1) • (n 2) (n m 1) n (n m)!
C
3 4
C
4 4
C
3 5
C
4 5
C
5 5
C10 C11
C
0 2
C12
C
2 2
C
0 3
C13
C
2 3
C
3 3
C
0 4
C14
C
2 4
C
3 4
C
4 4
C
0 5
C15
C
2 5
C
3 5
C
4 5
C
5 5
左右对称抛物线
C10 C11
C
0 2
C12
C
2 2
C13
C
2 3
C
0 3
C14
C
2 4
C
3 3
C
3 4
C
0 4
注2:上下前后及某项 知四有一两头同(中间差)
§249 组合数的性质
一、对称性:
Cnr
C nr n
二、增减性:
左右对称抛物线 左增右减中间大
三、拆并性: 拆并要连同 上大下+1
1.
Cnr
Cnr1
C r1 n1
2. Crr
Cr r 1
Cr r2
Cr n-1
Cr1 n
四、可和性: 系数求和赋值法 方法要熟正负1
C
2 5
C
3 5
C
4 5
C
5 5
幂的运算性质
③ amn am an
④ amn am an
⑤ amn (am )n (an )m
特殊幂
① a0
1②
an
1 an
⑦ an bn (当n 2,3时,背诵之)
⑧
(a b)n
当 当nn
42时,3时, 二,项背式诵定之理
⑨ (a b)n an bn
3.在与不在 4.含与不含 5.至多与至少
——
特殊优先直接法 正难则反间接法
6.错排:①背诵法:a2=1;a3=2;a4=9;a5=44……
②递推法: ①〇 an (n 1)(an1 an2 )
②〇 Ann Cn0a1 Cn1a1 Cn2a2 Cnnan
7.定序:
①倍缩法(等概率法):N n! m!
m
⑥ a n n am
同底幂
⑩
( a )n b
an bn
异底幂
二项式定理——通项公式
Tr1 Cnr anrbr
T上1 C下上前下上后上
(a b)n Cn0an Cn1an1b Cnra b nr r Cnnbn
注1:相关概念: ①项与项数: 类似于学号与同学的关系
②系数与二项式系数:Cnr 称为二项式系数 ;容斥关系
C r1 n1
其中含A元素的组合数是 Cnr 不含A元素的组合数是 Cnr 1
所以
Cnr
C r1 n
C r1 n1
三、拆并性: 拆并要连同 上大下+1
1. Cnr
C r1 n
C r1 n1
2. Crr
Cr r 1
Cr r2
Cr n-1
Cr1 n
(6)
C10 2014
C11 2014
CC1?1 2?015
C
2 5
C
3 5
C
4 5
C
5 5
C10 C11
C
0 2
C12
C
2 2
C
0 3
C
1 3
C
2 3
C
3 3
C
0 4
C14
C
2 4
C
3 4
C
4 4
C
0 5
C15
C
2 5
C
3 5
C
4 5
C
5 5
C
0 1
C11
C
0 2
C12
C
2 2
C
0 3
C
1 3
C
2 3
C
0 4
C14
C
2 4
C
0 5
C
1 5
C
2 5
C
3 3
法2:由题意得x2的系数是
C32
C42
C52
C2 n2
1 (C33 C32 ) C42 C52 Cn22
1 C43
C42
C52
C2 n2
1
C3 n3
n(n2 6n 11)
6
实际上,由
Crr
Crr1
Cr r2
Cr n-1
Cr1 n
得
x2的系数是
Cn33
1
n(n2
6n 6
11)
9.分配:
(1)不同元素的分配: 先分组后分配
(2)相同元素的分配(分组):0—1法
10.染色问题:
(1)条型域:
如图,1 2 3 … n ,用k种颜色染n块区域,相邻
区域不能同色, 则共有 tn k(k 1)n1 种染法
注1:染色基础是条型 方法多多随爱好 从头到尾逐个染 乘法原理显神功
注2:隐含了颜色有剩余
§249 组合数的性质
一、对称性:
Cnr
C nr n
二、增减性:
左右对称抛物线 左增右减中间大
三、拆并性: 拆并要连同 上大下+1
1.
Cnr
Cnr1
C r1 n1
2. Crr
Cr r 1
Cr r2
Cr n-1
Cr1 n
四、可和性: 系数求和赋值法 方法要熟正负1
1. C0n C1n C2n C3n Cnn 2n 2. C0n C2n C4n C1n C3n C5n 2n-1
⑦分配
均匀分配 非均匀分配
先分组后分配
⑧错排:二元1种;三元2种;四元9种……
⑨定序——倍缩法(等概率法);插空法
⑩染色——递推法
1.相邻问题捆绑法:
先捆可邻成大元 次变个数全排列
2.不邻(相离)问题插空法:
先排可邻后插空 多元切忌间接法
二元可用间接法 亮灯空位是变式
引:相间问题位置法
相邻相离综合体 一般解法位置法
四、可和性: 系数求和赋值法 方法要熟正负1
1. C0n C1n C2n C3n Cnn 2n 2. C0n C2n C4n C1n C3n C5n 2n-1
练习4.可和性:
(8)赋值法证:C0n C1n C2n C3n Cnn 2n
证明①:令a=b=1,代入
② 先组后排:排列可以看作是先取组合,再做全排列
Anm Cnm m!
两理两数四原则 十大题型递推法
①先理后数 ②先组后排 ③特殊优先 ④正难则反
两理两数四原则 十大题型递推法
①相邻——捆绑法
②不邻(相离) ——插空法
③在与不在
④含与不含 ⑤至多与至少
——
特殊优先直接法 正难则反间接法
⑥分组
相同元素——0-1法 不同元素——公式法
1. C0n C1n C2n C3n Cnn 2n 2. C0n C2n C4n C1n C3n C5n 2n-1
一、对称性:
Cnr
C nr n
与首末两端“等距离”的两个二项式系数相等
二、增减性:
n
1.当n为偶数时,展开式中间的一项
C2 n
取得最大
n 1
n 1
2.当n为奇数时,展开式中间的两项
hn (k 2)hn1 (k 1)hn2 (n 4)
注:二三环型点算法 四块以上递推法
异色插入第一类 同色剪开第二类
二项式的展开式
(a b)n Cn0an Cn1an1b Cnranrbr Cnnbn
注1:(前项)后n 项C“n0+n”相Cn1连n1 展开共 C有nrn n+rr Cnnn
C2 n
,Cn 2
相等
且同时取得最大
一、对称性: 二、增减性:
左右对称抛物线 左增右减中间大
杨辉三角形——二项式系数表
11 121 1331 14641 1 5 10 10 5 1
C10 C11
C
0 2
C12
C
2 2
C
0 3
C
1 3
C
2 3
C
3 3
C
0 4
C14
C
2 4
C
3 4
C
4 4
C
0 5
C15
C
2 5
C15
C
3 5
C
4 4
C
4 5
C
0 5
C
5 5
左增右减中间大
练习1.对称性:
(1)对称性
Cnr