Ω

组合数学(原书第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页)

多重集合排列 (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定理

四 生成排列和组合

列出{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}的一个排列.

附录

附录 (394页)