《形形色色的计数》

第一章 初等排列组合1

1 问题的基本提法1

2 无重排列与组合3

3 可重排列与组合7

习题一10

第二章 基本计数法则12

1 和则与分组法12

2 积则与分步法17

3 等则与配对法20

4 映射与分配25

习题二28

第三章 二项式系数30

1 二项式定理与二项式系数30

2 杨辉三角33

3 组合恒等式42

习题三52

第四章 多项式系数54

1 多项式定理54

2 多项式系数的组合意义58

3 多项式系数的性质61

习题四66

第五章 费波那契数与递归关系67

1 费波那契数列67

2 递归关系69

3 费波那契数列通项公式72

4 费波那契数列的组合意义77

5 费波那契数列的性质81

6 递归关系的应用84

7 其它的递归关系90

习题五94

第六章 卡塔兰数与母函数96

1 卡塔兰数96

2 母函数100

3 卡塔兰数的通项公式和性质106

4 多重集的排列组合113

5 母函数的应用117

习题六128

第七章 斯特林数、拉赫数与差分表130

1 两类斯特林数130

2 斯特林数的递归关系与数值表131

3 斯特林数的组合意义137

4 斯特林数的其它性质141

5 拉赫数148

6 差分表及其应用154

习题七159

第八章 容斥原理与莫比乌斯反演162

1 容斥原理162

2 容斥原理的应用167

3 限位排列174

4 莫比乌斯函数与欧拉Ψ函数179

5 莫比乌斯反演183

6 多重集的圆排列189

习题八196

第九章 几何计数问题198

1 子图形计数——直接方法198

2 子图形计数——间接方法207

3 图形的切割214

4 折线法及其应用220

5 整点与整边三角形226

习题九233

第十章 鸽笼原理和兰姆赛理论235

1 鸽笼原理的基本形式235

2 整数的和、差、倍240

3 难以置信——不容置疑247

4 奥林匹克试题一瞥250

5 兰姆赛理论254

习题十258

习题答案与提示260