从排列组合到江苏高考数学附加题最后一题
排列组合
●前置知识：null
●QQ826755370
-“哇，OIer居然能做江苏高考数学附加题的最后一题？”
-“嗯，可以的，我们来试试。”
-“这怎么做啊，逗我吧。”
-“先把下面的内容看完再做。”
排列
●普通排列
现在有1、2、3三个数，每个数字只能用一次，问它们能组成几个不同的三位数？
方法一：我会枚举
123 132 213 231 312 321
嗯，一共是六种。
方法二：我会算
我们从高位往低位选数，百位上有3种可能，到了十位上时剩下了2个数可以选，而到了个位时就只剩下1个数了，乘起来，所以答案是6种。
我们再来看下一个问题。
现在有1、2、3、4三个数，每个数字只能用一次，问它们能组成几个不同的三位数？
方法一：我还是会枚举
123 124 132 134 142 143 213 214 231 234 241 243
312 314 321 324 341 342 412 413 421 423 431 432
嗯，一共是24种，但是现在我们发现，枚举稍微有点烦了。
方法二：我还会算
类比刚才的算法，百位上有4种选法，十位上3种，个位上2种，乘起来，答案是24种。
我们把这种问题称为排列，同时我们把在n个数中选择m个数（n>=m)的排列的方案总数记为P(n,m),也可以写成以下的形式：
根据我们刚才的计算过程，很容易得到：
更多情况下，我们用阶乘表示：
需要注意的是，存在以下两种规定：
●圆排列
有7个大爷大妈，现在要从中选择4个坐成一圈打麻将，请问有几种坐法。
方法一：我……不会枚举了。
方法二：运用排列的知识解决。
这里需要注意的是，下图的两种情况算一种，右边的坐法可以由左边的坐法顺时针旋转90度得到。 如何解决这一问题呢？我们就将其看作线性的排列，但是始终将同一个人放置在第一位，这样就能避免重复。那么在确定好哪4个人打麻将后，第一位原本有4种选择，现在只剩了1种，所以我们得到答案：
从而我们得到圆排列公式：
●带有重复元素的排列
一个集合内有n个、m种元素，第i个元素有cnt[i]个，求这n个元素的全排列个数。我们不难发现，一个相同的排列被重复计算的次数为：
所以最终的答案为：
组合
●普通组合
给出一个不严谨的定义：不考虑顺序的排列就是组合。同表示排列的P，我们用C表示组合。那么我们该如何所呢，其实不难发现，在P(n,m)的排列里，同一张组合方式被计算了m!次，所以我们得到组合数公式：
●杨辉三角与组合数
先观察下图的杨辉三角（如果不知道杨辉三角是什么请自行百度）。
看图片上方的一行字，为什么会这么巧呢？难道组合数可以通过可以和杨辉三角一样通过递推得到？下面给出两种证明。
证明一：我们可以将C(n,m)分为两类。
（1）不含第n个数，方案数为C(n-1,m)。
（2）含第n个数，方案数为C(n-1,m-1)。
所以我们得到以下的公式：
证明二：这里我偷个懒，直接放一张图。
等一等，我们该如何证明杨辉三角的正确性？不要急，看一看下面的二项式定理。
●二项式定理
如果你看懂了上面的内容，那么这个定理对你来说很轻松的，二项式定理是这个小破玩意儿：
是不是有点头晕，让我们来换个说法：(a+b)^n中a^(n-m)b^m项的系数为C(n,m)。
证明如下：
即n个(a+b)连乘，从中选择m个b，那么剩下(n-m)个a，所以C(n,m)即为a^(n-m)b^m的系数。
●卡特兰数
我们定义卡特兰数Cat[i]表示用n-1条对角线将一个凸n＋2边形分割为互不重叠的三角形的方案总数。
卡特兰数存在以下递推公式：
证明：
这东西的证明比较玄学难，我也不会证，发一张图，能看懂的就看吧。
卡特兰数还能解决这些与它的定义看似没有半毛钱关系的问题：
1.如图所示的路径数量问题（从左下角走到右上角，只能在红线的右侧走）。
2.出栈方案问题（luogo P1044）
van♂结撒花★,°:.☆(￣▽￣)/$:.°★ 。
-“喂(#`O′)，等等，江苏的那道高考题该怎么写啊？”
●那道题的解法
由于题目在文章的开头，所以这里再发一遍：
对不起，发错了。这才是真正的题目：
这题的的第一问过水，我们直接看第二问。
我们在排好序的原序列上有两种操作可以产生一个逆序对为2的排列：
（1）任意交换两对相邻的数，共有C(n-1,2)种方案。
（2）将一个数向前移动两次，共有(n-2)种方案。