中科⼤-组合数学复习知识点⼀、鸽巢原理定理：n+1个物品放⼊n个盒⼦中，那⾄少有 1 个盒⼦中⾄少有 2 个物品。
解题思路：构造部分和序列正整数a i=2s i×r i,s i为⾮负整数,r i为奇数加强形式：m个物品放⼊n个盒⼦中，⾄少有 1 个盒⼦中⾄少有mn个物品。
若物品数与盒⼦数相等，则⾄少 1 个盒⼦中⾄少有 1 个物品。
若m=n+1，则⾄少 1 ⼀个盒⼦中⾄少有 2 个物品。
解题思路：递增⼦序列问题：构造{m k},m k表⽰从a k开始的最长递增⼦序列长度将集合分成 n 部分，使⽤加强形式取余⼆、排列与组合2.1 集合的排列组合r排列=P(n,r)=A rn =n! (n−r)!r圆排列=1r P(n,r)=1r A rn=n!r(n−r)!r组合数=nr=C rn=n!r!(n−r)!定理：(n0)+(n1)+⋯+(nn)=2n解题思路：能被 3 整除的数，各位数字之和也要能被 3 整除2.2 多重集合定理：多重集合M={∞⋅a1,∞⋅a2,⋯,∞⋅a k}的r排列数为k r.定理：多重集合M={k1⋅a1,k2⋅a2,⋯,k n⋅a n}的全排列数为(k1+k2+⋯+k n)!k1!k2!⋯k n!.只适⽤全排列，如果 k 排列，则⽤指数型⽣成函数。
定理：多重集合M={∞⋅a1,∞⋅a2,⋯,∞⋅a k}的r组合数为(k+r−1r)=C rk+r−1.证明⽅法：对应求⾮负整数解⽅案数x1+x2+⋯+x k=r =>r 个相同的球放⼊ k 个不同的盒⼦中定理：多重集合M={∞⋅a1,∞⋅a2,⋯,∞⋅a k}，要求各元素⾄少出现⼀次的r组合数为(r−1k−1)=C k−1r−1.证明⽅法：对应求满⾜⼀定条件的整数解⽅案数x1+x2+⋯+x k=r,x i≥1例题：求⽅程x1+x2+x3+x4=18满⾜条件x1≥3,x2≥1,x3≥4,x4≥2的整数解数⽬。
解：令y1=x1−3,y2=x2−1,y3=x3−4.y4=x4−2，则原⽅程变为y1+y2+y3+y4=8的⾮负整数解数⽬，(8+4−1 8)⌈⌉()课后习题 13，不穿过直线y=x课后习题 13，不穿过直线y=x的⾮降路径数？三、⼆项式系数⼆项式定理：(x+y)n=x n+(n1)x n−1y+(n2)x n−1y2+⋯+y n=∑ni=0(ni)x n−i y i⽜顿⼆项式定理：(1+x)α=∑∞r=0(αr)x r,(αr)=α(α−1)⋯(α−r+1)r!,α为⼀切实数,|x|<1α=−n 时，有(αr)=(−1)r(n+r−1r)(1+x)−n=∑∞r=0(−1)r(n+r−1 r)x r(1−x)−n=∑∞r=0(n+r−1 r)x r(1+x)−1=1−x+x2−x3+⋯(1−x)−1=1+x+x2+x3+⋯α=12时，有(αr)=(−1)r−11r22r−1(2r−2r−1)(1+x)12=∑∞r=1(−1)r−11r22r−1(2r−2r−1)x r,Catalan数基本性质：对称关系：(nr)=(nn−r)递推关系：(nr)=(n−1r)+(n−1r−1)=C rn−1+C r−1n−1组合恒等式：C1 n +2C2n+3C3n+⋯+nC nn=n2n−1C k 0+C k1+C k2+⋯+C kn=C k+1n+1∑n i=0(C in)2=C n2n∑r i=0C imC r−in=C rm+n,Vandermonde恒等式∑m i=0C imC r+in=C m+rm+n多项式定理：(x1+x2+⋯+x t)n=∑(nn1n2⋯n t)x n11x n22⋯x n tt,(nn1n2⋯n t)=n!n1!n2!⋯n t!例题：展开 (2x1−3x2+5x3)6，则 x31x2x23系数为解：6!3!1!2!23(−3)52多项式定理性质：展开式项数为n1+n2+⋯+n t=n的⾮负整数解个数，为(n+t−1 n)∑(nn1n2⋯n t)=t n,令所有xi都为1四、容斥原理定理：|¯A1∩¯A2∩⋯∩¯A m|=|S|−∑|Ai|+∑|A i∩A j|+⋯+(−1)m|A1∩A2∩⋯∩A m|推论：|A1∪A2∪⋯∪A m|=|S|−|¯A1∩¯A2∩⋯∩¯A m|欧拉函数的证明欧拉函数表⽰⼩于 n 且与 n 互素的整数的个数n =p i 11p i 12⋯p iq q 记 A i ={x |x ≤n 且p i |x} ，表⽰与 p i 成倍数的那些数那么 φ(n)=|¯A 1∩¯A 2∩⋯∩¯A q |=n ∏q i=1(1−1p i )定义：N (P i 1,P i 2,⋯,P i k ) 表⽰ S 中具有性质 P i 1,P i 2,⋯,P i k的元素个数ω(k )=∑N (P i 1,P i 2,⋯,P i k) 表⽰具备 k 个性质的元素计数，其中⼀个元素会被多次计数。
