这是Buraldi的《组合数学》的简要笔记. 这书废话挺多的,内容也比较像科普而不像专业数学书.
笔记里只会记录个人觉得有价值的内容,像图论的那几章就不记了(与其看这个不如看专门的图论书),有些看不进去的内容当然也不会记.
第1章
Nim游戏:有\(2\)个人和\(k\)堆金币,每一堆中有\(n_i\)个金币.两个人轮流取金币,每次只能取某一堆最上面的若干金币(不能不取),先取完的人胜出.
设\(n_i\)的二进制表示为\(n_i=a_{is}\cdots a_{i1} a_{i0}\),如果对于所有\(1\le j\le s\),\(a_{1j}+a_{2j}+\cdots+a_{kj}\)为偶数,则称此局面是平衡的,否则为不平衡的.
对于平衡的开始局面,后手必胜,因为先手不管怎么取都会把局面从平衡变为不平衡,然后后手每次将不平衡的局面变为平衡,最后一定是后手取完. 对于不平衡的开始局面,先手必胜,因为先手总可以取一些金币使得局面从不平衡变为平衡,然后重复刚才的过程.
第2章
对于有\(k\)种元素,每种元素有\(n_k\)个的多重集合,将其中\(n=n_1+\cdots+n_k\)个元素全部取出进行排列的种数为\(\frac{n!}{n_1!\cdots n_k!}\). 其组合意义是,先给多重集中的元素标号,排列数为\(n!\),再忽略同种元素的编号.
对于有\(k\)种元素,每种元素无穷多的多重集合,从中取出\(r\)个元素进行组合的种数为\({r+k-1}\choose r\). 其组合意义是,组合的个数可以转化为\(x_1+\cdots+x_k=r\)的正整数解个数,而这可以利用插隔板的思想求种数.
第5章
组合恒等式:
\[\sum_{k=0}^n{k n \choose k}=n2^{n-1},\sum_{k=0}^n{k^2 n \choose k}=n(n+1)2^{n-2}.\]
它们可以用二项式定理求导证明,第一个等式也可以用恒等式\(k{n\choose k}=n{ {n-1}\choose{k-1} }\)来证明. 对于一般情形,可以参考CF上的一道题.
\[\sum_{k=0}^n{ {m_1\choose k} {m_2\choose{n-k} } }={ {m_1+m_2}\choose n} , \sum_{k=0}^n{(-1)^k {n \choose k}^2}=(-1)^m { {2m}\choose m} (n=2m);0 (n为奇数).\]
它们可以用多项式Cauchy乘积比较系数的方法证明,第一个不等式也可以用组合意义:\(m_1\)个元素和\(m_2\)个元素共同组成的集合中选出\(n\)个元素所可能的种数. 第一个不等式取\(m_1=m_2=n\)是一个特殊情形.
多项式定理:
\[(x_1+\cdots+x_t)^n=\sum_{n_1+\cdots+n_t=n}{ {n\choose{n_1 \cdots n_t} } x_1^{n_1} \cdots x_t^{n_t}}.\]
第6章
一般Mobius反演: 设\((X,\le)\)为一有最小元且局部有限的偏序集,其上的函数\(f,g:X\times X\rightarrow R\)具有卷积\((f*g)(x)=\sum_{z\le y}{f(x,z)g(z,y)}\).
定义\(\delta\)函数和\(\zeta\)函数:\(\delta(x,y)=1(x=y);0(x\neq y),\zeta(x,y)=1(x\le y);0(其他)\),则\(\zeta\)函数有逆函数\(\mu*\zeta=\zeta*\mu=\delta\),\(\mu\)函数称作Mobius函数.
对于\(f:X\rightarrow \mathbb{R}\),有Mobius变换\(g(x)=\sum_{y\le x}{f(y)}\),从而有Mobius反演\(f(x)=\sum_{y\le x}{g(y)\mu(y,x)}\).
在容斥原理中,设\(X=P(U),\le=\subset\),此时Mobius函数为\(\mu(A,B)=(-1)^{|B|-|A|}(A \subset B)\); 在数论中,设\(X=\mathbb{N},\le=\mid\),此时Mobius函数化为数论中的Mobius函数:\(\mu(x,y)=\mu(\frac{y}{x})(x\mid y)\).
第7章
设多重集合\(S\)中有\(k\)种元素,每种元素有\(n_i\)个,取出其中\(n\)个元素的组合有\(g_n\)种,排列有\(h_n\)种. 则有生成函数
\[g(x)=\sum_{n=0}^{\infty} {g_n x^n} = \prod_{i=1}^k (\sum_{j=0}^{n_i} {x^j})\], \[h(x)=\sum_{n=0}^{\infty} \frac{h_n}{n!} x^n = \prod_{i=1}^k ( \sum_{j=0}^{n_i} \frac{x^j}{j!} ).\]
第8章
Catalan数可以用于出栈序列,上三角形限制下行走,乘法计算顺序,多边形三角剖分等情况.
设\(n\)的分拆种数为\(p_n\),则有生成函数
\[\sum_{n=0}^{\infty}{p_nx^n}=\prod_{k=1}^{\infty}{\frac{1}{1-x^k}}\].
第14章
设群\(G\)作用在集合\(S\)上,用\(q\)种颜色\(C\)给\(S\)中的每个元素染色,就能诱导出\(G\)在\(C\)上的作用.
若存在\(g\in G\)使得\(g*c=c'\),则染色\(c\)和\(c'\)等价,\(C\)中等价类的个数记为\(N\).
记稳定子\(C(g)={c\in C \| g*c=c}\),则有Burnside引理:
\[N=\frac{1}{ \| G \| } \sum_{g\in G}{ \| C(g) \| }\].
特别地,取\(S=\\{1,\cdots,n\\}\),\(G\le S_n\),记置换\(g\in G\)的循环节个数为\(\tau(g)\),那么有 \(\| C(g) \| =q^{\tau(g)}\) ,进而有Polya计数定理:\[N=\frac{1}{ \| G \| } \sum_{g\in G}{q^{\tau(g)}}\].