现在的位置: 首页 > 综合 > 正文

组合数学->排列组合

2013年11月01日 ⁄ 综合 ⁄ 共 1195字 ⁄ 字号 评论关闭

先写一下知识点,书上写的公式基本都是阶乘之类的,但acm需要的是递推关系,所以看见阶乘就不用记了。

下面的T路计数和卡特兰数被坑死了,拿个水题用复杂的方法想,其实就一个水dp看一眼就知道的。组合数学都是用dp写的,只需要会几个常用模型。

排列 和 组合是两个不同的知识,高中一直没区分清楚。T路计数和卡塔兰数的公式长好推只需要知道dp方法,而重点实际上是:组合的隔板法、卡塔兰数的模型。

一、 计数的基本原则

 相等原则、加法原则、乘法原则

例1.1:n名选手参加乒乓球单打淘汰赛,需要打多少场比赛才能产生冠军?

解:n - 1

二、 排列

    1.n 元集的 r- 排列

n 个不同的数中选出 r 个:

    2.n 元集的 r- 可重复排列

从 n 个数中可重复的选出 r 个数为: 

例2.2: 由1、2、3、4、5、6 可组成多少个大于 35000的5位数?

解:1>万位数字为3的5位数 2 * 6^3 = 432  2>万位数字大于3的5位数 3 * 6^4 = 3888

    3.多重集的排列

由 n1 个 a1,n2 个 a2...nk 个 ak组成的集合: 

例2.3:求多重集 M = {5 * a, 3 * b}的 6- 排列的个数。

解:M 的 6- 子集有如下3个:A1 = {5*a, 1*b}, A2 = {4*a,2*b}, A3 = {3*a,3*b}

 三、T路的计数

    数学上的公式基本都有阶乘的,所以这一节的 T路计数只需要知道原理实现起来就是一个水dp

    1.T路

T步、T条件:其实就是往右上角或右下角走一格

整点 A(a,α) 到整点 B(b,β) 的T路的条数:

证明:书上的证明是扯蛋,为了清晰用 δx δy 表示,注意到 等边三角形 直接用 多重集的排列就口算出来了

    2.反射原理

由整点 A 到 整点 B 且经过 x 轴的条数等于由 A‘ (a, -α) 到 B 的条数:

A 到 B 不经过 x 轴的条数为上面两个相减。

    3.Catalan(卡塔兰)数

    重点了解卡塔兰数的模型,见后面的百度百科

由点 (0,0) 到点 (2n,0) 不经过 x 轴且位于上半平面的 T路的条数:

证明:转化为由点 (1,1) 到点 (2n-1,1)不经过 x 轴且位于上半平面

四、组合

    1.n 元集的 r- 组合

从 n 个不同的数中选 r 个:

    2.n 元集的 r- 可重复组合

从集合中可重复的选取 r 个元素:熟练隔板法等方法

    3.组合数的基本性质

4.多项式定理/二项式定理


    5.组合恒等式

五、二项式反演公式

<=>

********************************************************************************************************************************************************************************************************************

隔板法的应用:点击打开链接

卡塔兰数模型:点击打开链接

卡塔兰数专题:点击打开链接

抱歉!评论已关闭.