组合数学 [计算机机数学专题(6)]

                                                                                                     目录

• 计数原理
• 组合问题的分类
• 排列
• 组合
• 解排列组合问题的 28 个方法
• 母函数
• 莫比乌丝反演
• Lucas 定理

          组合数学起源于人类早期的数学游戏。

          很久以前，中国的古书中便有相关的记载如《易经》的八卦，八卦还是天然的二维矩阵。

          现代的组合学源于 1666 年《组合的艺术》一书的出版。                  

计数原理

           计数原理包含：加法原理、乘法原理、鸽巢原理、容斥原理，这些原理为解决问题提高了许多思路。

           加法原理：如果事件 A 和 事件 B 相互排斥，而事件 A 有 p 种产生方式，事件 B 有 q 种产生方式，则事件 " A 或 B " 有 p + q 种产生方式。

加法原理

           乘法原理：如果事件 A 和 事件 B 相互独立，且事件 A 有 p 种产生方式，事件 B 有 q 种产生方式，则事件 " A 与

乘法原理

            加法原理和乘法原理最重要的区别是事件 A 和 事件 B 的关系，是 "或" 还是 "与"。

            或：要么 A 发生，要么 B 发生，

•                    举例：假设从家到学校有 2 趟公交、3 打游轮 、4趟列车、5班飞机，那么从家到学校共有多少种选择方式 ？

                              因为公交、游轮、列车、飞机都是相互排斥的(或)，所以只能选一种交通工具。

                              要么坐公交、要么上游轮、要么乘列车、要么搭飞机，2 + 3 + 4 + 5 = 14 种。

            与：A 和 B 可以一起产生、有先后关系，   

•                    举例：再假设从家到学校后，还要去市中心办一个交通优惠卡。

                              从学校到市中心也有  2 趟公交、3 打游轮 、4趟列车、5班飞机。那么从 学校 到 市中心 也是 14 种，从 家 到 市中心 是 14 * 14 种，从家到市中心有先后关系会采用乘法原理。

             鸽巢原理：若把 n+1 部手机放进 n 个袋子中，则至少有一个袋子放了俩个或俩个以上部手机。

                               若把 n-1 部手机放进 n 个袋子中，则至少有一个袋子是空的。

             应用鸽巢原理最主要考虑：

                                鸽子是什么，上面是手机；

                                巢是什么，上面是袋子；

                                鸽子和巢各有多少，上面是 n + 1 / n - 1 和 n。

             容斥原理：

组合问题的分类

          组合学主要研究的问题是如何按照一定规则来安排一些物体，具体的 4 种问题：

1.  存在性问题 ：判断满足某种条件的情况或状态是否存在；
2.  计数性问题： 存在多少种满足某种条件的情况或状态；
3.  构造性问题： 如果已判断出满足某种条件的状态是存在的，那么如何构造出；
4.  最优化问题： 找出某种评论标准下的最佳(或较佳)构造方案。

          排列数   

或

或

，从 n 个元素中有序的取 r 个元素的情况数

          组合数   

或

或

，从 n 个元素中无序的取 r 个元素的情况数         

排列

         选排列：n 个不同元素有序的取 r 个排在一起，则有 

 种，读作 n 的降 r 阶乘。                        应用乘法原理推出 

 。

          e.g.  k = 2 ，n = 5， 

排列数 = 从 n 个元素中有序的取 r 个元素的情况数

         圆排列：n 个不同元素有序的取 r 个不分首尾的围成一个圆圈，则有 

 种，记为

。 

圆排列数 = 从 n 个元素中有序的取 r 个元素的情况数 ➗ r 个元素

组合

           n 个不同元素不考虑次序取 r 个排在一起，则有

 种，

 。           在排列的基础上不考虑 r 个元素的次序 即

 =

。

组合数 = 从 n 个元素中有序取 r 个元素的情况数 ➗ 有序的摆放 r 个元素的情况数

           组合数的递推：求一个组合数可以从ta的前面推出。

           假设求

 ？ 

从 n 个元素中取出 r 个                      

 可以从

 递推过来 (根据加法原理)。

从 n 个元素中取 r 个元素的组合数 = 从 n-1 个元素中取 r-1 个元素的组合数 + 从 n-1 个元素中取 r 个元素的组合数

                      分情况讨论，有俩种情况 第 r 个元素 或被取，或不被取。

            以 n = 4，r = 2 举例，桌上有 4 张卡片 ( [A] [B] [C] [D] ) ，抓 2 张卡片放手上(不考虑顺序)，将 TA 分成 选择 [D] 的情况 与 不选择 [D] 的情况(也可以为其ta卡片)。

            如果选择[D]，就只能从 [D] 以外的 3 张卡片中选取 1 张放手上。

            如果不选择[D], 就只能从 [D] 以外的 3 张卡片中选取 2 张放手上。

从 3(即 n-1) 个元素中取 1(即 r-1) 个元素的组合数，

                           不选择[D]，就是  从 3(即 n-1) 个元素中取 2(即 r) 个元素的组合数。

           组合数的递推：求一个组合数可以从ta的前面推出。   

            代码实现，类似于 "动态规划" 的思想......

            代码实现需要考虑，第 r 个元素从哪里来 ？

                                    由 前面的

 相加得到 ，C[n][r] = C[n-1][r] (取 r)   +   C[n-1][r-1] (不取 r)。

#include <stdio.h>

int main( void )
{
	int C[256][256] = {0}, N;
	scanf("%d", &N);
	
	for( int n = 0; n<= N; n ++ )
	{
		C[n][0] = 1;     // 规定 C(n, 0) = 1
		for( int r = 1; r <= n; r ++ )
		    C[n][r] = C[n-1][r-1] + C[n-1][r];
	}
	
	for( int i = 0; i <= N; i ++, putchar(10) )
	    for( int j = 0; j <= i; j ++ )
	        printf(" %d ", C[i][j]);  // C(n, r)
	
	return 0;
}

          发现组合书数递推输出的结果组成一个杨辉三角。

          在《算法导论》等专业性强的书，经常会以下降阶乘幂表示组合。

          组合公式： 

           下降阶乘幂：

            e.g.            

，使用下降阶乘幂的表达形式要比组合形式计算容易的多。           下降阶乘幂指将含有 

 的式子改成沿 n 阶阶梯逐步下降的乘积形式，即 

。           

。

使用回溯法实现排列、组合。

#include <stdio.h>
int main( void )
{
    int flag;
    while
    (
        printf("先生，扣 0 为排列，扣 1 为组合:>  "),
        scanf("%d",&flag),
        flag != 0 && flag != 1  // while 的结束条件
    );
    
    int n, r;
    printf("这位先生，实现 %s 前要输入 n, r:>  ", flag ? "组合:P(n, r) ":"排列:C(n, r)");
    scanf("%d%*c%d", &n, &r);
    
    int s1, s2, s;   s1 = s2 = 1;    s = 0;
    int i, j, a[ 32 ];
    for( j = 1; j <= r; j ++ )
    {
    	s1 = s1 * (n - j + 1);        // 猜猜看～
    	s2 = s2 * (n - j + 1) / j;    // 这俩个公式是啥 ？？
    }
    i = 1; a[ i ] = 1;
    
    while( 1 )
    {
    	int t = 1;
    	for( j = 1; j < i; j ++ )
    	    if( flag == 0 && a[ j ] == a[ i ] || flag == 1 && a[ j ] >= a[ i ] )
    	  {   t = 0; break;  }
    	if( t && i == r )
    	{
    		for( j = 1; j <= r; j ++ )
    		    printf("%c", a[ j ] + 64 );     // 以大写字母输出
    		printf("%-4c", ' ');
    		if( ++s % 5 == 0 )                  // 每行 5 个
    		     putchar( 10 );
    	}
    	if( t && i < r )
    	 {   i ++, a[ i ] = 1; continue; }    
    	while( a[ i ] == n )                        // 回溯
    	    i --;
    	if( i > 0 )
    	    a[ i ] ++;
    	else
    	    break;
    }
    printf("%d\n", s);
    return 0;
}

解排列组合问题的 21 个方法

•            NO.1：相邻问题采用捆绑法。

                   e.g.  若有 A、B、C、D、E 五人排队，A 和 B 要求俩人相邻请问有多少种排法 ？

捆绑法思想：把 几个 看成 一个，A 和 B 变成一个，总共是 4 个排队是考虑顺序的。

                     4 个人里面选 4 个排队即P(4，4)，还有 A 和 B 也有顺序即 P(2, 2)，一共是 P(4, 4) * P(2, 2) = 48。

•             NO.2：不相邻问题采用插空法。

                    e.g.  在一张节目单中原有 6 个节目再添加 3 个节目进去，若想保持这些节目相对顺序不变，共有多少种排法 ？

插空法思想：只适合有缝隙的对象，而后放入另一个对象即可。           

插空法图解

•              NO.3：定序问题采用缩倍法

                     e.g.  A、B、C、D、E 五人站成一排，倘若 B 必须站在 A 的右边(可以不相邻)那么不同的排法有多少种 ？

缩倍法思想：应用于排列问题中限制某几个元素必须保持一定的顺序。

                     A、B、C、D、E 五人无论怎么排，要么 B 在 A 的左边，要么在右边，刚好这俩种也是对称的。

                     所以 B 必须站在 A 的右边是原问题的一半即 P(5, 5) / 2。

•               NO.4：标号排位问题采用分布法

                      e.g.  乒乓球队的 10 名队员有 3 名主力对员，派 5 名参加比赛，3 名主力队员要安排在第一、三、五的位置，其余 7 名队员选 2 名安排到第二、四的位置，那么不同的出场顺序多少种 ？

分布法思想： 将元素排到指定位置上，可先把某个(些)元素按照规则排入，第二步再排另一个(些)元素，如此反复即可完成。

                      选出第一、三、五的位置的人，因为考虑 3 名主力队员站的位置顺序，就有 P(3，3) 种；

                      接着从其余的 7 名队员中选出 2 名，因为不考虑顺序，是有 C(2，2) 种。放入第二、四的位置又考虑顺序即 P(2，2)。

                      不同的出场顺序有 P(3，3) * C(2，2) * P(2，2) 种。

•                NO.5：有序分配问题采用逐分法

                       e.g.  12 名同学分到 3 个不同的路口调查，若每个路口 4 人，则不同的分配方案有 ?

逐分法思想：把所有元素分成若干组，后排列。

                       12 人排成 3 队，每队 4 人， 1队：C(12，4) ，2队：C(8，4)，3队：C(4，4)。 

                       分组后 3组 出现相同元素，需要再除以 P(3，3)，又因为路口不同还要乘以P(3，3)，俩俩抵消只剩 C(12,4)*C(8,4)*C(4,4)。                             

                       排列组合问题，要跳出来记住本质，不要拘泥于眼前的几小步......   

母函数

              http://www.wutianqi.com/blog/596.html

莫比乌丝反演

Lucas 定理

[ 更ing... ]