Ryan_<

染色问题：面染色/点染色，通常要求是相邻不同色。

• 立体图形尽量转化为平面图形，简化问题（对我这种空间想象能力奇差的人..）
• 图形的放置默认是有序的，即相当于每个点事先编号。
• 按一定分类顺序计数，用组合数表示。★注意有无"每种颜色必须都用"的要求，如果没有则先按所用颜色数分类

计数问题：

带有限制条件的计数：

• 先特殊(处理限制条件)后一般
• 必须相邻问题：捆绑法，整体+局部
• 不相邻问题：插空法(先考虑不受限制的元素的排列)

至多至少类问题：从反面入手

分组分配类问题：

• Step1：分组(整体均分/部分均分/不等分),其实处理方法是一致的:用C表示分组过程,若均分则与顺序无关,将相应的排列数A除掉。
• Step2：分配。简单的排列过程，x组数的排列数。

n元一次方程整数解个数问题：隔板法

x1+x2+x3+...+xn=S

非负整数解个数：C(S+2,n-1)

正整数解个数：C(S-1,n-1)

二项式定理的相关计算：

《6·7》专题(十二)，十分完整清晰

二项式定理+不等式放缩证明不等式：

• (a+b)^n的形式：考虑二项式定理展开，再利用其它方式放缩
• 伯努利不等式：/( (1+x)^n≥1+n*x  (x>-1,n为正整数) /)——一般形式(见onenote)

组合数的几个性质：

• 对称性、增减性。最大值：偶数项即第n/2项系数，奇数项即第(n-1)/2和第(n+1)/2项的二项式系数。★注意一共有n+1项!
• /( r*C(n,r)=n*C(n-1,r-1) /)。由组合数的定义运算方法可推出。
• 所有(n+1)项的二项式系数相加=2^n，奇数项二项式系数之和=偶数项二项式系数之和
• 组合恒等式:/( C(n,k)=C(n-1,k)+C(n-1,k-1) /)，简单的dp思想，也可借助杨辉三角放在坐标上

组合数计算的常用方法：【Orz韩旭大神】

1. 利用(1+x)^n展开式。令x=特殊值，通常为1，-1，i，ω(自招)
2. 直接计算
3. 求导(取微分)，可多次求导，适时等号两边同乘x改变指数
4. 利用杨辉三角(找规律，猜想)
5. 构造实际意义：题目中有多个kC相乘时考虑

补充的Tips：

调换三个数中每一个数的位置，不同的方式有A(2,2)=2种；

4个数的话：不是A(3,3),而有9种。这种计数还是列树状图分析比较好。