排列与组合
(
P_m^n=frac{n!}{(n-m)!}(Rightarrow A_m^n)(有顺序)
\
(_m^n)=frac{n!}{m! imes(n-k)!}(Rightarrow C^n_m)(无顺序)
)
Catalan数
(
本质(最通俗易懂):在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f(n)。
\
或(经常用的):一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
\
h_n的递推关系和通项公式：
)
( 通项公式： )
求数的性质(个人认为&重要)：
(
画图求.
)
(
(此图为Catalan数的画图求法)
其它（非三角形（有多种Catalan数））以此类推。
)
证明：
(
如果n个+1和n个-1的序列满足部分和都不小于0，则称其为可接受的，否则为不可接受的，令A_n为n个+1和n个-1形成的可接受序列的个数，令U_n为不可接受序列个数。我们尝试计算出A_n+U_n的值和U_n的值以得到A_n的值。
\
任意一个有n个+1和-1的构成的2n项必然属于且仅属于可接受序列和不可接受序列之一，于是有：
)
( 下面我们试图计算出U_n的值。 \ 对于任意一个不可接受的数列中一定存在一个最小的k，使得a_1+a_2+a_3+cdots+a_k<0，于是我们可以得到一些显然的结论：k是一个奇数，前k-1个数中+1和-1恰好各占一半且a_k=-1.我们将这k个数取相反数，后面的数不变，由此得到了一个有n+1个+1和n-1个-1的数列。注意这个操作是可逆的：对于一个有n+1个+1和n-1个-1的数列，我们只需要找到最小的k，满足a_1+a_2+a_3+cdots+a_k>0,然后将前k个数取反即可得到原数列。所以不可接受序列和有n+1个+1和n-1个-1的数列是一一对应的，故： )
( 再结合： )
Stirling数
性质:
(
第二类Stirling数实际上是集合的一个拆分，表示将n个不同的元素拆分成m个集合的方案数，记为S(n,m)或者{_m^n}。
\
和第一类Stirling数不同的是，集合内是不考虑次序的，而圆排列是有序的。常常用于解决组合数学中几类放球模型。描述为：将n个不同的球放入m个无差别的盒子中，要求盒子非空，有几种方案？
\
第二类Stirling数要求盒子是无区别的，所以可以得到其方案数公式：
)
(
(也为通项公式)
)
容斥原理与错位排列问题
容斥原理:
(
定义:如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。（A∪B∪C=A+B+C-A∩B-B∩C-C∩A+A∩B∩C）
)
错排:
(
性质:对于一个1cdotscdots n的任意排列，有一种情况是第i个位置上的数不是i对任意i都成立，这样的排列被称为错位排列。
公式：
)
鸽巢原理
又名狄利克雷抽屉原理、鸽笼原理
性质:
(
桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。
)
第一抽屉原理
(
原理1:把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
\
证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n×1，而不是题设的n+k(k≥1)，故不可能。
\
原理2：把多于mn(m乘n)+1（n不为0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。
\
证明（反证法）：若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能。
\
原理3：把无数还多件物体放入n个抽屉，则至少有一个抽屉里有无数个物体。
\
原理1 、2 、3都是第一抽屉原理的表述。
)
第二抽屉原理
(
把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体。
)
常见运用
(
构造抽屉的方法
\
运用抽屉原理的核心是分析清楚问题中，哪个是物件，哪个是抽屉。
\
在问题中，较多的一方就是物件，较少的一方就是抽屉。
\
最差原则
最差原则，即考虑所有可能情况中，最不利于某件事情发生的情况。
\
（反证法）：若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能。
)
表现形式
(
把它推广到一般情形有以下几种表现形式。
\
形式一：设把n+1个元素划分至n个集合中(A_1，A_2，…，A_n)，用a_1，a_2，…，a_n分别表示这n个集合对应包含的元素个数，则：至少存在某个集合A_i，其包含元素个数值a_i大于或等于2。
\
证明：（反证法）假设结论不成立，即对每一个a_i都有a_i<2，则因为a_i是整数，应有a_i≤1，于是有：a_1+a_2+…+a_n≤1+1+…+1=n<n+1，这与题设矛盾。所以，至少有一个ai≥2，即必有一个集合中含有两个或两个以上的元素。
\
形式二：设把nm+1个元素划分至n个集合中(A_1，A_2，…，A_n)，用a_1，a_2，…，a_n表示这n个集合对应包含的元素个数，则：至少存在某个集合A_i，其包含元素个数值a_i大于或等于m+1。
\
证明：（反证法）假设结论不成立，即对每一个a_i都有a_i<m+1，则因为a_i是整数，应有a_i≤m，于是有：a_1+a_2+…+a_n≤m+m+…+m=nm<nm+1，这与题设相矛盾。所以，至少有存在一个a_i≥m+1
\
知识扩展——高斯函数[x]定义：对任意的实数x，[x]表示“不大于x的最大整数”。例如：[3.5]=3，[2.9]=2，[－2.5]=－3，[7]=7，……一般地，我们有：[x]≤x<[x]+1
\
形式三：设把n个元素分为k个集合A_1，A_2，…，A_k，用a_1，a_2，…，a_k表示这k个集合里相应的元素个数，需要证明至少存在某个a_i大于或等于[n/k]。
\
证明：（用反证法）假设结论不成立，即对每一个a_i都有a_i<[n/k]，于是有：
a_1+a_2+…+a_k<[n/k]+[n/k]+…+[n/k] =k*[n/k]≤k*(n/k)=n
\
k个[n/k] ∴ a1+a2+…+ak<n 这与题设相矛盾。所以，必有一个集合中元素个数大于或等于[n/k]
\
形式四：设把q1+q2+…+qn－n+1个元素分为n个集合A_1，A_2，…，A_n，用a_1，a_2，…，a_n表示这n个集合里相应的元素个数，需要证明至少存在某个i，使得a_i大于或等于q_i。
证明：（用反证法）假设结论不成立，即对每一个a_i都有a_i<q_i，因为a_i为整数，应有a_i≤q_i－1。
\
于是有：a_1+a_2+…+a_n≤q_1+q_2+…+q_n－n <q_1+q_2+…+q_n－n+1这与题设矛盾。
\
所以，假设不成立，故必有一个i,在第i个集合中元素个数a_i≥q_i。
\
形式五：证明：（用反证法）将无穷多个元素分为有限个集合，假设这有限个集合中的元素的个数都是有限个，则有限个有限数相加，所得的数必是有限数，这就与题设产生矛盾，所以，假设不成立，故必有一个集合含有无穷多个元素。（借由康托的无穷基数可将鸽巢原理推广到无穷集中。）
)
一般表述
(
在上面的第一个结论中，由于一年最多有366天，因此在367人中至少有2人出生在同月同日。这相当于把367个东西放入 366个抽屉，至少有2个东西在同一抽屉里。在第二个结论中，不妨想象将5双手套分别编号，即号码为1，2，...，5的手套各有两只，同号的两只是一双。任取6只手套，它们的编号至多有5种，因此其中至少有两只的号码相同。这相当于把6个东西放入5个抽屉，至少有2个东西在同一抽屉里。
\
抽屉原理的一种更一般的表述为：
\
“把多于kn+1个东西任意分放进n个空抽屉（k是正整数），那么一定有一个抽屉中放进了至少k+1个东西。”
\
利用上述原理容易证明：“任意7个整数中，至少有3个数的两两之差是3的倍数。”因为任一整数除以3时余数只有0、1、2三种可能，所以7个整数中至少有3个数除以3所得余数相同，即它们两两之差是3的倍数。
\
如果问题所讨论的对象有无限多个，抽屉原理还有另一种表述：
\
“把无限多个东西任意分放进n个空抽屉（n是自然数），那么一定有一个抽屉中放进了无限多个东西。”
\
用高斯函数来叙述一般形式的抽屉原理的是：将m个元素放入n个抽屉，则在其中一个抽屉里至少会有[(m-1)/n]+1个元素。
\
集合论的表述是：设A和B为同基数的有限集，f:A→B为一个映射，则f为单射的充要条件是f为满射。
\
抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
\
这个问题可以用如下方法简单明了地证出：
\
在平面上用6个点A、B、C、D、E、F分别代表参加集会的任意6个人。如果两人以前彼此认识，那么就在代表他们的两点间连成一条红线；否则连一条蓝线。考虑A点与其余各点间的5条连线AB，AC，...，AF，它们的颜色不超过2种。根据抽屉原理可知其中至少有3条连线同色，不妨设AB，AC，AD同为红色。如果BC，BD ，CD 3条连线中有一条（不妨设为BC）也为红色，那么三角形ABC即一个红色三角形，A、B、C代表的3个人以前彼此相识：如果BC、BD、CD 3条连线全为蓝色，那么三角形BCD即一个蓝色三角形，B、C、D代表的3个人以前彼此不相识。不论哪种情形发生，都符合问题的结论。
\
六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例，这个简单问题的证明思想可用来得出另外一些深入的结论。这些结论构成了组合数学中的重要内容-----拉姆塞理论。从六人集会问题的证明中，我们又一次看到了抽屉原理的应用。
)
Nim取石子游戏
性质:
(
游戏内容：
\
有两个玩家面对若干堆石子进行游戏。设有k≥1堆石子，各堆分别含有n_1,n_2...n_k枚硬币。
\
游戏规则：
\
(1):游戏中两个人交替进行游戏（我们称第一个取的为1号，第二个取的为2号）。
\
(2):当玩家取石子的时候，先选择硬币中的一堆，然后可以从堆中取走任意数量的硬币。
\
当所有的堆为空时，游戏结束。最后取子者（即能够取走最后一堆中剩下的所有硬币）获胜。
)
特殊情况：
(
如果一开始只有n_1：那么1号取完n_1，游戏结束。
\
如果一开始只有两堆(n_1,n_2)：那么对于1号来说，他不关心n_1,n_2，他关心的是n_1,n_2是否相等。
\
如果n1≠n2，那么1号取多的那一堆，使得两堆相等，等2号来取的时候，2号取完只会产生两种情况：①：存在两堆不相等 ②：只有一堆了。
\
对于②：一号赢，游戏结束。
\
对于①，一号继续构造成两堆相等，一直如此，会变成状态②，一号赢.
\
去考虑一般情况。
)
思路:
(
我们知道对于一个十进制数，都有一个对应的二进制数。我把每堆分成几个子堆，怎么分呢？
\
就是应用刚刚说的拆成2的非负次幂的数[2^0，2^1，2^2....2^x]。
\
有什么用呢？
\
在只有2堆石子Nim取石子游戏中，各种大小的子堆的总数只能是0，1，2。
\
考虑各种大小的子堆的总堆数是偶数是什么情况？
\
两个堆相等嘛，2号赢的情况。
\
子堆的总堆数不都是偶数。
)
重点：
(
现在考虑各堆大小为n_1,n_2...n_k的一般Nim取石子游戏。将每一个数n_i表示成2的非负次幂的数。
)
(
于是Nim取子游戏是平衡的。
\
于是我们有1号能够在非平衡Nim取子游戏中取胜，2号能够在平衡Nim取子游戏中取胜。
\
如果局势是非平衡的状态，那么1号可以从一个堆中取石子，留给2号平衡的状态。而2号怎么做都会构成非平衡状态，从而1号赢；反之，同理。
)
另一种思路:
(
当n mod (m+1)=0时，先手必败;否则先手必胜，必胜策略是每一次都取走当前石子数mod(m+1)的值。
)
SG函数
(
给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。事实上，这个游戏可以认为是所有公平组合游戏的抽象模型。
\
一个重要的性质：从必败态走到的每一个状态都是必胜态，从必胜态操作一步走到的所有状态中至少有一个是必胜态。规定无法操作的状态为必胜态。
\
在最简单的取石子游戏中，设f[N]表示还剩N个石子的状态都是必胜态，那么显然f[N]可以转移到f[N-1]到f[N-M]，这里面只有一个必胜态f[N]就必胜否则必败。
\
SG函数的规定如下：最终状态（不可操作状态）的SG函数为0，其余状态的SG函数规定为所有不等于它的某一个后继的SG函数的最小非负整数，例如一个状态有2个后继状态，它们的SG函数分别为2和3，则当前状态的SG函数分别为0和2，则当前状态SG函数为1。
\
SG函数判断状态是否必胜的规则是如果当前状态的SG函数为0，则当前状态必败，否则当前状态必胜。容易发现引入SG函数后我们之前递推判断必胜必败的规则也可用于SG函数的递推上。往往我们可以找到一些状态和SG函数之间的规律，从而避免递推。
)
图论浅谈——二分图理论与Ramsey理论
二分图
(
二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
)
定义
(
简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。
)
充要条件
(
无向图G为二分图的充分必要条件是，G至少有两个顶点，且其所有回路的长度均为偶数。
\
证先证必要性。
\
设G为二分图<X，E，Y>。由于X，Y非空，故G至少有两个顶点。若C为G中任一回路，令
)
(
其中诸v_i(i=0,1，…，l）必定相间出现于X及Y中，不妨设
)
(
{v_0,v_2,v_4，…，v_l=v_0} Í X
)
(
{v_1,v_3,v_5，…，v_l-1} Í Y
)
(
因此l必为偶数，从而C中有偶数条边。
)
(
再证充分性。
)
(
设G的所有回路具有偶数长度，并设G为连通图（不失一般性，若G不连通，则可对G的各连通分支作下述讨论）。
)
(
令G的顶点集为V，边集为E，现构作X，Y，使<X，E，Y> = G。取v0ÎV，置
)
(
X = {v | v= v0或v到v0有偶数长度的通路}
)
(
Y = V-X
)
(
X显然非空。现需证Y非空，且没有任何边的两个端点都在X中或都在Y中。
)
(
由于|V|≥2并且G为一连通图，因此v0必定有相邻顶点，设为v1，那么v1ÎY；故Y不空。
)
(
设有边（u,v），使uÎX，vÎX。那么，v0到u有偶数长度的通路，或u = v0；v0到v有偶数长度的通路，或v = v0。无论何种情况，均有一条从v0到v0的奇数长度的闭路径，因而有从v0到v0的奇数长度的回路（因从闭路径上可能删去的回路长度总为偶数），与题设矛盾。故不可能有边（u,v）使u,v均在X中。
)
(
“没有任何边的两个端点全在Y中”的证明可仿上进行，请读者思考。
)
性质
(
二分图中，点覆盖数是匹配数。
\
（1）二分图的最大匹配数等于最小覆盖数，即求最少的点使得每条边都至少和其中的一个点相关联，很显然直接取最大匹配的一段节点即可。
\
（2）二分图的独立数等于顶点数减去最大匹配数，很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。
\
（3）DAG的最小路径覆盖，将每个点拆点后作最大匹配，结果为n-m，求具体路径的时候顺着匹配边走就可以，匹配边i→j',j→k',k→l'....构成一条有向路径。
\
（4）最大匹配数=左边匹配点+右边未匹配点。因为在最大匹配集中的任意一条边，如果他的左边没标记，右边被标记了，那么我们就可找到一条新的增广路，所以每一条边都至少被一个点覆盖。
\
（5）最小边覆盖=图中点的个数-最大匹配数=最大独立集。
)
判定
(
二分图是这样一个图： 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接！
\
无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。
\
判断二分图的常见方法是染色法： 开始对任意一未染色的顶点染色，之后判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色， 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断，bfs和dfs可以搞定！
\
易知：任何无回路的的图均是二分图。
)
从两个形似的问题看数学模型的构建
性质：
例题：
(
将数组{8,23,4,16,77,-5,53,100}中的元素按从大到小的顺序排列,最少需要交换几次?【1003 - NOIP 2008 普及组初赛试题第 14 题】
\
第一次77和53交换
\
8 23 4 16 53 -5 77 100
\
第二次 53 和-5交换
\
8 23 4 16 -5 53 77 100
\
第三次 23 和-5交换
\
8 -5 4 16 23 53 77 100
\
第四次 8 与4交换
\
4 -5 8 16 23 53 77 100
\
第五次 4与-5 交换
\
-5 4 8 16 23 53 77 100
)
#include<iostream>
#include<climits>
#define MAXN 1000001
using namespace std;
int a[MAXN];
int main()
{
ios::sync_with_stdio(false);
int n,k=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n-1;i++)
{
int minn=INT_MAX,x;
for(int j=i+1;j<n;j++)
{
if(minn>a[j])
{
minn=a[j];
x=j;
}
}
if(minn<a[i])
{
int t=a[i];
a[i]=minn;
a[x]=t;
k++;
}
}
cout<<k<<endl;
return 0;
}
( 或 )
#include<iostream>
#include<climits>
#define MAXN 1000001
using namespace std;
int a[MAXN];
int main()
{
ios::sync_with_stdio(false);
int n,k=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=n-1;i>0;i--)
{
int maxn=-INT_MAX,x;
for(int j=i-1;j>=0;j--)
{
if(maxn<a[j])
{
maxn=a[j];
x=j;
}
}
if(a[i]<maxn)
{
int t=a[i];
a[i]=maxn;
a[x]=t;
k++;
}
}
cout<<k<<endl;
return 0;
}