组合数学(原书第5版) 美 Richard Brualdi

什么是组合数学

数学归纳法

b-ominoe b 格牌 覆盖棋盘的(条形牌) (3页)

幻方

一个 n x n 矩阵,其行~列~对角线上元素和都相等.和叫幻和.

    8 1 6
    3 5 7
    4 9 2
    // 这个3阶幻方的幻和是15
    n 阶幻方的幻和公式 s = n * (n^2 + 1) / 2

la Loubere 构造幻方的方法.可以造出 n 为奇数时的幻方. (5页)

36军官问题

拉丁方

拉丁方是一个 n x n 矩阵,其元素特点是每一行每一列都是 (1,2,..,n) 的一种排列,且没有两行或者两列出现相同的排列.

或者是这样, (1,2,..,n)里的元素,在拉丁方的每一行每一列都出现一次.

    // 3阶拉丁方 每一行每一列都有 (1,2,3) 这3个数
    1 2 3
    3 1 2
    2 3 1

    // 又一个3阶拉丁方
    1 3 2
    3 2 1
    2 1 3

    // 这个不是拉丁方,第2列没有3,第3列没有2
    1 2 3
    3 2 1
    2 1 3

正交拉丁方

如果有两个 n x n 的拉丁方矩阵 A B ,它们的元素按相应位置组成一个新元素c1(a1,b1),得到一个新的 n x n 矩阵 C.它的每个元素都互不相同.那么,A B是互相正交的拉丁方.

    // 3阶拉丁方 A
    1 2 3
    3 1 2
    2 3 1

    // 3阶拉丁方 B
    1 3 2
    3 2 1
    2 1 3
 
    // 组合 A B , 其元素都是互不相同的
    (1,1) (2,3) (3,2)
    (3,3) (1,2) (2,1)
    (2,2) (3,1) (1,3)

2阶拉丁方例子,也就是 A B 这两种情况了.

    // A
    1 2
    2 1

    // B
    2 1
    1 2

    // 组合 A B ,可见元素有相同的,2阶拉丁方不存在正交的.
    (1,2) (2,1)
    (2,1) (1,2)

相互重叠的圆

每个圆之间都相交,可以划分出多少个区域? 两个圆相交(不是相切)会有2个交点.

二 排列与组合

加法原理 (16页)

书上的定义没有看懂,这是百科词条:

加法原理是分类计数原理,常用于排列组合中,具体是指:做一件事情,完成它有n类方式,第一类方式有M1种方法,第二类方式有M2种方法,……,

第n类方式有Mn种方法,那么完成这件事情共有M1+M2+……+Mn种方法.

例如,从上海到三亚.交通工具有飞机,船,火车3种,飞机有3班次,火车有2班次,船有1班次,那么上海到三亚的办法有3 + 2 + 1 = 6种.

乘法原理

百科词条:做一件事,完成它需要分成 n 个步骤,做第一步有 m1 种不同方法,做第二步有 m2 种不同方法,……,做第 n 步有 mn 种不同方法,那么完成这件事共有 m1 * m2 *...* mn 种不同的方法.

联系: 加法原理和乘法原理是两个基本原理,它们的区别在于一个与分类有关,另一个与分步有关.运用以上两个原理的关键在于分类要恰当,分步要合理.分类必须包括所有情况,又不要交错在一起产生重复,要依据同一标准划分;而分步则应使各步依次完成,保证整个事件得到完成,不得多余~重复,也不得缺少某一步骤.

减法原理 (18页)
除法原理

令 S 是一个有限集合,把它划分成 k 个部分使得每一个部分的对象数目相同,于是,部分的数目 k = |S| / 部分中的对象数目个数

有6个苹果,9个橘子,做成1个水果篮,至少有1个水果.有多少种做法?

思路: 如果只要苹果(做法1),有6种,分别是1~6个苹果.如果只要橘子(做法2),有9种.如果都要(做法3),那么乘法原理有 6 X 9 = 54 种.所以一共有 9 + 6 + 54 = 69种.

从百科定义思考: 做水果篮是一个事件,完成这件事有3种做法,1种有6种方法,2种9种,3种要分两步骤做,分别是6种和9种方法所以6X9,最后加法原理累加3种做法的方法数.

10000 ~ 99999 之间偶数个数 ?

这两个数之间有 99999 - 10000 = 89999 + = 90000 个数,由于奇数偶数交替出现,所以偶数为 90000/2 = 45000 个.

用组合的思路,这是一个五位偶数,所以要求个位是偶数.那么从高位到低位写出这个数,分五部.第一步有 1~9 9个选择, 2,3,4 位都是 0~9 10个选择,

个位是 0 2 4 6 8 5个选择,那么根据乘法原理得到, 9 * 10 * 10 * 10 * 5 = 45000 .

仍然是偶数,加一个条件,5个数字都不相同.有多少个?

先选择个位,再从万位到十位.因为每个位不能重复,所以下个选择要剔除选上个选中的.

// 思路

这里有一个细节容易出错,先看第一种方法,个位选 0 ,那么万位到十位就是, 9 * 8 * 7 * 6 = 3024

第二种方法,个位选 2 ,那么其它位是, 8 * 8 * 7 * 6 = 2688 当个位选 4,6,8 时,也一样如此.

那么相当于使用了5种方法(或者2种方法,后4种一样)完成选偶数这件事,那么根据加法原理,一共有偶素: 3024 + 2688 * 4 =13776

这个细节在于,选0为个位时,万位有9种选法(1~9),而选2,4,6,8时,万位有8种选法.(1~9,除去2,4,6,8其中一个)

这个例子说明,优先选择约束性最强的选择. (20页)
    // 判断一个数字每个位都不同
    string num = number.ToString();
    bool issame = false;
    for (int j = 0; j < num.Length; j++)
    {
        // 拿出一个数字, 从字符串数组末尾开始,如果找到其它位还有这个数,说明重复
        if(num.LastIndexOf(num[j])!=j)
        {
            issame = true;
            break;
        }
    }
    // 10进制最大的各个位不同的数
    9876543210
    // 1 - 10位自然数,每位数不同
    数位   个数    奇数     偶数 
    1      9       5       4
    2      81      40      41
    3      648     320     328
    4      4536    2240    2296
    5      27216   13440   13776
    6      136080  67200   68880
    7      544320  268800  275520
    8      1632960 806400  826560
    9      3265920 1612800 1653120
    10     126000  58320   67680

1 1 1 3 8 这五个数可以生成多少五位数 ?

先看 3,8 这两个数放到五位数的任何位上,有5 * 4 = 20 种方法.第一步,3或者8有5种位置,第二部,3或者8有4种位置,乘法原理.

还剩下3个位置,剩下的3个1无论怎么放,在3,8已经确定位置的情况下,不会影响数字.所以就是有20种五位数.

如果是 1 1 1 3 3 如何? 10种

上面两个问题用加法和乘法原理不容易解决,因为集合有重复的元素,先学习排列.这是一个多重集合的排列数. (20页)

排列

n个元素的集合,r数目的排列数公式:

P(n,r) = n!/(n-r)! 线性排列

例如P(1,2,3) 任取2个数排列, 3!/(3-2)! = 6 种

P(n,r) / r = n! / (r * (n-r)!) 循环排列

线性排列和循环排列的区别在于,循环排列没有开始和结束,而线性排列有第一个元素和最后一个元素.这会产生一个现象,如果循环排列指定一个元素为开始元素,

按一个方向循环,到这个元素的相邻元素循环一周,会得到一个线性排列.这个排列在指定不同开始元素时不同.也就是说,一个循环排列可以包含多个线性排列.

集合的组合

n 个元素的集合 S ,拿出 r 个元素,这 r 个元素是 S 的子集(无序).有多少种拿法.

S{a,b,c} n = 3,r = 2 有3个子集 {a,b} {a,c} {b,c}

(n r) = n! / (r! * (n-r)!) (25页)

帕斯卡公式 (26页)

集合Sn的子集个数数量公式: (27页)

(n 0) + (n 1) + ... + (n n) = 2^n

例如S {1,2,3} 的所有子集是: {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} 和 空集

多重集合排列 (28页)

多重集合 (百科词条)

多重集或多重集合是数学中的一个概念,是集合概念的推广.在一个集合中,相同的元素只能出现一次,因此只能显示出有或无的属性.

在多重集之中,同一个元素可以出现多次.正式的多重集的概念大约出现在二十世纪七十年代.多重集的势的计算和一般集合的计算方法一样,

出现多次的元素则需要按出现的次数计算,不能只算一次.一个元素在多重集里出现的次数称为这个元素在多重集里面的重数(或重次~重复度).

例如 S {a,b,c,c,b,a} ,元素个数是6,元素种数是3

多重集合 S 的排列数公式.其中,n 是 S 的元素个数, k 是元素的种数,n1是元素1的个数,n2是元素2的个数,nk是元素k的个数.那么 S 的 n 排列数为:

n! / (n1!n2!...nk!)

使用这个公式可以解决之前提到的问题: 1 1 1 3 8 可以生成多少五位数?

这是 n = 5,k = 3 的多重集合,5位数正好就是 n 排列,使用公式 5!/(3!*1!*1!) = 20

这个公式的证明思路举上面这个例子说明: 5位数,现象成5个格子,每个格子放一种数,有3个1,那么需要3个格子,3,8各需要一个格子,此时相当于

用3个步骤实现了这个5位数,那么根据乘法原理可得总排列数为: P(5,3) * P((5-3),1) * P((5-3-1),1) 用公式表示

5!/(3!*(5-3)!) * (5-3)!/(1!*(5-3-1)!) * (5-3-1)!/(1!*(5-3-1-1)!)

前项分母与后项分子消去得: (5!/3!) * (1 / 1!) * 1/(1!* 0!) = n! / (n1! * n2!...nk!)

多重集合的组合 (32页)

设 S 是有 k 种对象的多重集合,每种元素都有无限重复数,那么 S 的 r 组合个数: C(r+k-1 r)

8种面包,12个装一盒,有多少种装法?

如题,12个里面有8个种类,所以这是一个多重集合(长度为12).只是装法,不要考虑12个面包的排列,所以是一个多重集合组合问题.

即: 长度为12的集合(S),有8种对象(k),12的组合数(r).

根据上面的公式,组合数为 C(12+8-1 12) = C(19 12) = 19! / (12! * (19-12)!) = 50388

如何验证这个结果,假设8个种类就是数字[1~8],组成一个12位长度的数字,可以有50388个数字.

不考虑顺序,例如 111111222222 和 222222111111 和 112211221122 是一个类型,它们都由6个1,6个2组成.

111111222222 和 111122222222不是一类,因为后面那个数是4个1和8个2组成的.不属于一类组合,多重集合组合是顺序不同,但元素相同,个数也相同.

最笨的方法,所有的这些数都在一个范围内[111111111111 ~ 888888888888],排除含有0和9的数.如果是同种组合,那么数字的种类和每个种类的个数必然相同.

根据这一点判断,写成代码验证.由于12个数字是千亿级别太多了,所以计算机测试的是长度为10的情况,C(10+8-1 10) = 17!(10! * (17-10)!) = 19488

每次开启1000个线程,跑10亿次FOR,一共跑8次,每次花费10分钟.最后使用计算机显示找到了 19448 个组合.说明验证成功,公式没有问题!

有限概率 (34页)

三 鸽巢原理

ramsey定理 (47页)

四 生成排列和组合

生成排列

列出{1,2,3,..,n}的所有排列,计算机算法其实是个递归.算法由Johnson 和 Trotter发现 (53页)

{1,2,3,..,n}的所有排列,可以视为在{1,2,3,..,n-1}的所有排列的每个元素前后位置插入n.而{1,2,3,..,n-1}的排列,可以视为{1,2,3,..,n-2}的所有排列的每个位置插入n-1...

最后一直到{1}的排列,只有一种,而{1,2}的所有排列就是在{1}的排列的元素 1 前后插入 2,得到{1,2} {2,1}.所以这是递归.

注意: {1,2,3,..,n-1}排列插入n的位置的数目是 (n-1)+1 = n .也可以说,存在n种方法,把{1,2,3,..,n-1}的一个排列,变成{1,2,3,..,n}的一个排列.

算法描述 (55-56页)

看了几遍这个算法,大意是:

有一个排序例如 P {2,6,3,1,5,4} ,规定一个方向 d ,比如向右边 d = right. 设 k 是排列中的一个元素,当 k 在 d 方向上,

相邻的那个数,比 k 小,那么 k 是可以移动的.这个排列中, k = 6 , 3 , 5 .因为这3个数的右边分别是 3 , 1 ,4 都比 k 小.

分析几种特殊情况:

最小元素: 1是 P 中的最小元素,没有其它元素比1小了,所以 P 中的最小元素是不可移动的.

最大元素: 6是 P 中的最大元素,当 d = right(left),且6在 P 的最右边(左边)位置时,6 不可移动.所以 P 中的最大元素在 d 方向的最后位置时,不可移动.

移动的规则是关键,那么为何要研究可移动?

以 P {1,2,3,4} , d = left 为例,当判断 P 中有可以移动的元素时,要做3件事.

1.找出最大的可移动整数 m

2.交换 m 和它 d 方向上的相邻元素位置

3.如果有 p > m,那么将 p 的方向反向

按照这个方法会得到最后一个排列,找不到可移动的数,就终止了.

分析算法和程序实现: 算法实现

排列中的逆序

逆序的概念书中的描述是: 设排列 i1,i2,..,in 是集合{1,2,3,..,n}的一个排列.如果 k < l 且 ik > ij,那么(ik,ij)为一个逆序.

看了3遍没有看懂,去查了百科,百科描述是: 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序.

百科看懂了,概念其实简单,就是说一个排列中的两个元素(i,k),如果 i 比 k 大,但 i 的位置在 k 前面,那么(i,k)这一对数叫一个逆序.

再看看书中的公式化的定义,果然数学是抽象的,老外的描述就是很严谨的.在我看来,通俗的描述容易理解,公式化的描述难懂.需要按照这公式实践一下,

才能明白它的涵义.通俗的好处是入门快,缺点是了解浅.公式化的好处是严谨点到精髓,缺点是不易理解,对想了解它的人不友好.

{3,1,5,2,4} 这个排列有几个逆序?根据公式要领,排列位置与元素大小相反是为逆序.那么有4个:

{3,1} {3,2} {5,2} {5,4} 例如{3,1},3比1大,但是3排在1前面,所以是逆序.

逆序列: 度量一个排列的无序程度.

逆序列的概念书中看了3遍算是明白了,还是以{3,1,5,2,4}为例,如何求出它的逆序列?这个逆序列又怎样度量其无序程度?

先看它的4个逆序,看第2个数,分别是 1 2 2 4,根据概念,这第2个数是含有这个元素的逆序的个数.例如1,表示含有元素1的逆序个数有1个,

找到它是{3,1}.再看2,2有2个,说明含有元素2的逆序个数是2个,就是{3,2} {5,2}.最后看4,有1个.那么,集合里的3,5呢?

这两个元素的逆序是0,因为没有比它大还排在它前面的数.按元素由小到大的顺序写出它们的逆序个数序列就是:

{1(1),2(2),3(0),4(1),5(0)} 去掉元素直接写出逆序列是 1,2,0,1,0

那么这又如何度量排列的无序程度呢?

排列{1,2,3,4,5}的逆序列为 0,0,0,0,0 .因为它是有序的.排列{5,4,3,2,1}的逆序列为 4,3,2,1,0

可见,每一个排列都有一个逆序列."不同的排列有不同的逆序列" (58页)

算法 由逆序求对应的排列

求{1,2,3,4,5,6,7,8}的一个排列,它的逆序是: 5,3,4,0,2,1,1,0 .根据书中的算法2,说明如下:

先放8个空位 {[],[],[],[],[],[],[],[]}

根据逆序列可以确定元素放在哪一个位置.

逆序列第1个值 5 ,表示元素 1 有5个逆序,那么元素1之前就要有5个比1大的元素,这些元素占有5个空位,所以元素1在第6个空位上.

第1步结果: {[],[],[],[],[], 1 ,[],[]}

逆序列第2个值 3,表示元素 2 有3个逆序,那么元素2就要在第4个空位上.

第2步结果: {[],[],[], 2 ,[], 1 ,[],[]}

逆序列第3个值 4,表示元素 3 有4个逆序,那么元素3就要在第5个空位上,第5个空位在空位列的第7个位置上,因为前2步填了2个空位.

第3步结果: {[],[],[], 2 ,[], 1 , 3 ,[]}

继续按照逻辑找到空位,最终结果是:

{4 , 8 , 6 , 2 , 5 , 1 , 3 , 7}

排序算法

计算机排序算法有选择排序,冒泡排序.书中介绍的这个方法是通用的排序算法.做法是:"连续交换相邻的数"

例如: {3,6,1,2,4,5} 排序成{1,2,3,4,5,6}.那么连续交换相邻的数步骤如下:


一共有6个步骤,它的原理就在于逆序列,排列的逆序列是 2,2,0,1,1,0 它的元素之和正好是 6.

程序代码如下

    long[] p = new long[] { 3,6,1,2,4,5 };
    int len = p.Length - 1;
    // 循环次数和逆序列有关,逆序列元素之和越小,循环次数越少,最少为 p.length次(没有考虑优化)
    // int count = 0;
    for (int i = 0; i < len; i++)
    {
        if (p[i] > p[i + 1])
        {
            long tmp = p[i];
            p[i] = p[i + 1];
            p[i + 1] = tmp;
            i = -1;
        }
        // count++;
    }


生成组合

生成集合S的所有组合(子集) (60页)

生成r子集 (67页)

五 二项式系数

牛顿二项式定理 (90页)

六 容斥原理及应用

七 递推关系和生成函数

八 特殊计数序列

Catalan数列

C(n) = (1/(n+1))*(2n n) = (1/(n+1)) * ((2n)! / ((2n-n)! * n!)) (n=0,1,2)

九 相异代表系

十 组合设计

模运算

十一 图论导引

欧拉闭迹,欧拉开迹

哈密顿圈

香农开关游戏

十二 再论图论

十三 有向图和网络

十四 Polya计数

练习题答案与提示

354页

读书日志

-- 2020年5月24日 --

从第6章就几乎完全看不懂了,所以略看了全书,了解了几个名词.组合数学知识对计算机算法尤其是排列组合有很强的相关性,很多算法直接来源于书中的定理.

对数学基础差的人将,读懂这书将的知识,不是容易的事.需要增进数学思维才行.当解决问题的算法没有依据时,可以到数学中寻找线索,看看有没有相关的理论.