从排列组合到江苏高考数学附加题最后一题

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