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

2018-07-31 12:07:14


排列组合

●前置知识: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.如图所示的路径数量问题(从左下角走到右上角,只能在红线的右侧走)。

Catalan

2.出栈方案问题(luogo P1044

luogu

van♂结撒花★,°:.☆( ̄▽ ̄)/ $:*.°★* 。 -“喂(#`O′),等等,江苏的那道高考题该怎么写啊?” ###●那道题的解法 由于题目在文章的开头,所以这里再发一遍: ![题目](https://cdn.luogu.com.cn/upload/pic/26061.png) 对不起,发错了。这才是真正的题目: ![真正的题目](https://cdn.luogu.com.cn/upload/pic/26014.png) 这题的的第一问过水,我们直接看第二问。 我们在排好序的原序列上有两种操作可以产生一个逆序对为2的排列: (1)任意交换两对相邻的数,共有C(n-1,2)种方案。 (2)将一个数向前移动两次,共有(n-2)种方案。 $$ fn(2)(n\ge5)=C{n-1}^2+(n-2)=\frac{(n-1)(n-2)}{2}+n-2=\frac{n^2-n-2}{2} $$ ##真正的完结撒花!*★,°*:.☆( ̄▽ ̄)/$ :.°★