书籍分享之 "Combinatorics - The Art of Counting" by Bruce Sagan
这本书是作者Bruce Sagan在密歇根州立大学开设的组合数学课程的讲义, 笔者在博士学姐Yulia Alexandr的带领下研读过其中第1-4、7章的部分内容并完成了部分习题. 一言蔽之,这是一本趣味横生、流畅自然的组合数学入门教材.
首章开篇, 作者从集合分拆(partition)、格点路径(lattice paths)、图(graph)与有向图(digraph)的计数等组合学中的经典专题娓娓道来, 引入了诸如Young diagram、Catalan数等重要概念或研究对象.
在(第2章)介绍容斥原理、Garsia–-Milne对合原理、Lindström–Gessel–Viennot引理之后, 作者花费了整整两章的篇幅(第3、4章)细致讨论了计数组合学家最强有力的工具之一————生成函数(generating functions). 特别地, 作者通过三种求解Bell数的生成函数的方法诠释了指数型生成函数的威力, 令笔者至今回味无穷.
由于第5、6两章相对独立(主要是时间紧张的原因…), 在Yulia学姐的建议下笔者跳过了这些内容, 并转而探索了第7章对称函数与计数的第1、2、3、5小节. 这4小节内容涵盖对称函数代数与Schur基、关于Young tableau的神奇公式————Hook Formula与行列式公式(不是矩阵行列式的定义哈). 相较前几章而言, 本章内容难度大, 更富有技术性, 但当读者一番思索顿悟之后, 定会神清气爽.
每章末的习题中, 既有补全细节推广证明等”理解性”问题, 又有殊途同归一题多证的”发散性”问题, 更有需要细细揣摩苦苦钻研的“挑战性”问题, 相信会使读者受益匪浅.
借用Yulia学姐的话, “这本书将带你领略组合数学的风景, 也将为你打开现代组合学的大门”.
注: https://users.math.msu.edu/users/bsagan/ 作者主页, 附有勘误表.
Enjoy Reading This Article?
Here are some more articles you might like to read next: