计数组合学导引 英文PDF电子书下载

第1章　基本方法 3

1.1　何时用加法、何时用减法 3

1.1.1　何时用加法 3

1.1.2　何时用减法 4

1.2　何时用乘法 6

1.2.1　乘法原理 6

1.2.2　联合使用几个计数原理 9

1.2.3　何时不允许有重复 10

1.3　何时用除法 14

1.3.1 除法原理 14

1.3.2　子集 17

1.4　基本计数原理的应用 20

1.4.1　双射的证明 20

1.4.2　二项式系数的性质 27

1.4.3　有重排列 31

1.5　鸽巢原理 35

评注 39

小结 40

练习题 41

习题解答 46

补充习题 54

第2章　基本方法的直接应用 59

2.1　多重集与合成 59

2.1.1 弱合成 59

2.1.2　合成 62

2.2　集合的划分 63

2.2.1　第二类斯特林数 63

2.2.2　第二类斯特林数的递推关系 65

2.2.3　何时块的数量是不固定的 69

2.3　整数的分拆 70

2.3.1　整数的非增有限序列 70

2.3.2　法勒斯图样及其应用 72

2.3.3　尝试一下：欧拉五角形数定理 75

2.4　容斥原理 83

2.4.1 两个相交的集合 83

2.4.2　三个相交的集合 86

2.4.3　任意多个相交的集合 90

2.5　放球入箱的12类方式 99

评注 102

小结 103

练习题 104

习题解答 108

补充习题 120

第3章　母函数 125

3.1 幂级数 125

3.1.1　广义二项式系数 125

3.1.2　形式幂级数 127

3.2　轻松一刻：解递推关系式 130

3.2.1　通常母函数 130

3.2.2　指数型母函数 138

3.3　母函数的积 141

3.3.1　通常母函数 142

3.3.2　指数型母函数 154

3.4　尝试一下：两个母函数的复合 160

3.4.1　通常母函数 160

3.4.2　指数型母函数 165

3.5　尝试一下：母函数的不同形式 173

评注 174

小结 175

练习题 176

习题解答 179

补充习题 190

第4章　排列的计数 195

4.1 欧拉数 195

4.2　排列的循环结构 204

4.2.1　第一类斯特林数 204

4.2.2　给定类型的排列 212

4.3　循环结构和指数型母函数 217

4.4　逆序 222

4.4.1　关于逆序排列的计数 227

评注 232

小结 233

练习题 234

习题解答 239

补充习题 251

第5章　图的计数 255

5.1　树和森林的计数 258

5.1.1　树的计数 258

5.2　图同构 260

5.3　标号顶点树的计数 265

5.3.1　森林的计数 274

5.4　图和函数 278

5.4.1　非循环函数 278

5.4.2　停车函数 279

5.5　何时顶点不能自由标号 283

5.5.1　有根平面树 283

5.5.2　二叉平面树 288

5.6　尝试一下：着色顶点图 292

5.6.1　色多项式 294

5.6.2 k色图的计数 301

5.7　图和母函数 305

5.7.1　树的母函数 305

5.7.2　连通图的计数 306

5.7.3　欧拉图的计数 307

评注 311

小结 313

练习题 314

习题解答 319

补充习题 330

第6章　极值组合学 335

6.1 极图理论 335

6.1.1 二部图 335

6.1.2　图兰定理 340

6.1.3 无圈图 344

6.1.4　无完全二部图的图 354

6.2　超图 356

6.2.1 具有分段相交边的超图 357

6.2.2　具有分段不可比边的超图 364

6.3　没有的反面：存在性证明 366

6.3.1 性质B 367

6.3.2　排除单色等差数列 368

6.3.3　有限字母表组成的代码 369

评注 373

小结 374

练习题 375

习题解答 381

补充习题 393

第7章　对称结构 399

7.1 具有对称性的超图 399

7.2　有限投影平面 406

7.2.1　尝试一下：质数幂阶的有限投影平面 409

7.7　纠错码 411

7.3.1 字的区分 411

7.3.2 由超图得到的码 414

7.3.3 完满码 415

7.4　对称结构的计数 418

评注 427

小结 428

练习题 429

习题解答 430

补充习题 435

第8章　组合学中的序列 439

8.1 单峰性 439

8.2　对数凹性 442

8.2.1　对数凹性蕴含着单峰性 442

8.2.2　积性质 445

8.2.3 内射的证明 447

8.3　实零点性质 453

评注 457

小结 458

练习题 458

习题解答 460

补充习题 466

第9章　幻方和幻立方的计数 469

9.1　一个有趣的分布问题 469

9.2　固定规模的幻方 470

9.2.1 n=3的情形 471

9.2.2　对固定n的Hn（r）函数 474

9.3　固定线和的幻方 485

9.4　为什么幻立方就不同了 490

评注 493

小结 495

练习题 496

习题解答 499

补充习题 509

附录A　数学归纳法 511

A.1 弱归纳 511

A.2　强归纳 513

参考文献 515

索引 521

常用记号 525