1. 排列与组合

文章链接 (opens new window)

https://gitee.com/fakerlove/combinatorics

教学视频 (opens new window)

https://www.bilibili.com/video/BV1vZ4y1j7gf

**组合数学（Combinatorics）**是纯数学的一个分支，主要研究离散、有限或可数的数学结构。

除了纯数学，组合数学在应用数学、理论物理、计算机科学等分支也有着很多应用。在计算机科学中，组合数学又被称作 “离散数学”。

在美国数学会的学科分类中，组合数学下设五个子学科，分别为：计数组合、设计理论、图论、极值组合、代数组合。

1.0 题目+例子

1.1 法则

1.1.0 概念

专业解释

组合数学（Combinatorial mathematics），又称为离散数学。广义的组合数学就是离散数学，狭义的组合数学是离散数学除图论、代数结构、数理逻辑等的部分。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。

早期排列组合的例子---->幻方

中国最早的组合数学，关于幻方的起源，中国有“河图”和“洛书”之说。相传在远古时期，伏羲氏取得天下，把国家治理得井井有条，感动了上天，于是黄河中跃出一匹龙马，背上驮着一张图，作为礼物献给他，这就是“河图”，也是最早的幻方。伏羲氏凭借着“河图”而演绎出了八卦，后来大禹治洪水时，洛水中浮出一只大乌龟，它的背上有图有字，人们称之为“洛书”。“洛书”所画的图中共有黑、白圆圈45个。把这些连在一起的小圆和数目表示出来，得到九个。这九个数就可以组成一个纵横图，人们把由九个数3行3列的幻方称为3阶幻方，除此之外，还有4阶、5阶...

幻方（Magic Square）是一种将数字安排在正方形格子中，使每行、列和对角线上的数字和都相等的方法。

幻方也是一种中国传统游戏。旧时在官府、学堂多见。它是将从一 到若干个数的自然数排成纵横各为若干个数的正方形，使在同一行、同一列和同一对角线上的几个数的和都相等。

幻方（OEIS中的数列A006052）的数目还没有得到解决。

在一个由若干个排列整齐的数组成的正方形中，正方形中任意一横行、一纵行及对角线的几个数之和都相等，具有这种性质的图表，称为“幻方”。中国古代称为“河图、“洛书”，又叫“纵横图”。

1.1.1 加法法则

若$|A|=m,|B|=n，A\cap B=\phi ,$则$|A\cup B|=m+n$

1.1.2 乘法法则

若$|A|=m,|B|=n，A\times B=\{(a,b)|a\in A,b\in B\},$则$|A\times B|=m\times n$

1.1.3 减法法则

定义A的补集$\overline{A}$,$\overline{A}=U|A=\{x\in U,x\in A\}$

计算A的个数$|A|=|U|-|\overline{A}|$​

1.1.4 除法法则

1.2 一一对应

一一对应是计数时常用的一种技巧，若性质A技术比较困难，性质B的计数比较容易，

但性质A和性质B一一对应，则对A的计数可转换为性质B的计数

例子

有100位乒乓球选手通过淘汰赛，

最后产生一名冠军，先分50分赛。第一轮结束留下50名胜利者。第二轮将50名胜出的选手分成25对进行比赛。以此类推。

请问一共进行了多少场比赛？？

暴力求解

$50+25+12+6+3+2+1=99$

使用一一对应的思想

比赛的台数和每一场比赛淘汰一名选手一一对应。100名选手要选出一名单打冠军，必须淘汰99名，故必须进行99台比赛。1000名选手要选出1名单打冠军，就必须进行999场比赛

1.3 排列组合

编号的乒乓球

4个乒乓球：

1号，2号，3号，4号，取出其中的3个

如果考虑顺序，则称为排列数P(4,3)

$P(4,3)=4*3*2=24$​。无重排序

如果不考虑顺序，则称之为组合数$C(4,3)$

$C(4,3)=\frac{4!}{3!}=4$​​。无重组合

1.3.1 排列

从$n$个不同的元素中，取$r$个不重复分元素，按次序排序，称为从$n$个中取$r$​个的无重排列，排列的个数用$P(n,r)$表示。或者$P_n^r$。一般不说可重即无重。

$P(n,r)=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}$​

1.3.2 组合

1) 概念

从$n$个不同元素中取$r$个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从$n$个中取$r$个的无重组合$n\ge r$

2) 组合模型

若球不同，盒子相同，则是从$n$个中取$r$个的组合的模型

固有

$C(n,r)=\frac{n!}{r!(n-r)!}$

3) 性质

$C(n,r)=C(n,n-r)$

$C(n,l)C(l,r)=C(n,r)C(n-r,l-r)$

班级中共有$n$位同学，选$l$位班委，班委中选出$r$位为核心

=先从$n$个同学中选出$r$个核心，再从剩下的$n-r$中选剩下的$l-r$个班委

1.3.3 全排列

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

公式：全排列数f(n)=n!(定义0!=1)，如1,2,3三个元素的全排列为：

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

共$3*2*1=6$种。

1.4 圆排列和项链排列

如果在一圆周上讨论排列问题即将一排列排到一圆周上，称为圆周排列问题，在这以前讨论的排列是排成一列。

从n个中取出r个进行排列数以$Q(n,r)$表示

$Q(n,r)=\frac{P(n,r)}{r}$

1.5 全排列算法

参考资料

https://www.cnblogs.com/nowornever-L/p/6008954.html

问题

对于给定的集合$A=\{a_1,a_2,...,a_n\}$,其中的n个元素互不相同，如何输出这n个元素的所有排列（全排列）。

例子

• 词组的排列
• 幻方排列

1.5.1 递归算法

由$\{1,2,\cdots,n-1\}$排列生成$\{1,2,\cdots,n\}$的排列

这里以$A=\{a,b,c\}$为例，来说明全排列的生成方法，对于这个集合，其包含3个元素，所有的排列情况有3!=6种，对于每一种排列，其第一个元素有3种选择a,b,c，对于第一个元素为a的排列，其第二个元素有2种选择b,c；第一个元素为b的排列，第二个元素也有2种选择a，c，……，依次类推，我们可以将集合的全排列与一棵多叉树对应。如下图所示

在此树中，每一个从树根到叶子节点的路径，就对应了集合A的一个排列。通过递归算法，可以避免多叉树的构建过程，直接生成集合A的全排列，代码如下。

template <typename T>
inline void swap(T* array, unsigned int i, unsigned int j)
{
    T t = array[i];
    array[i] = array[j];
    array[j] = t;
}

/*
 * 递归输出序列的全排列
 */
void FullArray(char* array, size_t array_size, unsigned int index)
{
    if(index >= array_size)
    {
        for(unsigned int i = 0; i < array_size; ++i)
        {
            cout << array[i] << ' ';
        }

        cout << '\n';

        return;
    }

    for(unsigned int i = index; i < array_size; ++i)
    {
        swap(array, i, index);

        FullArray1(array, array_size, index + 1);

        swap(array, i, index);
    }
}

1.5.2 字典序

• 全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法

• 每个排列的后继都可以从它的前驱经过最少的变化而得到

• 全排列生成算法的一个重要思路，就是将集合A中的元素的排列，与某种顺序建立一一映射的关系，按照这种顺序，将集合的所有排列全部输出。这种顺序需要保证，既可以输出全部的排列，又不能重复输出某种排列，或者循环输出一部分排列。

字典序就是用此种思想输出全排列的一种方式。

例子

这里以$A=\{1,2,3,4\}$来说明用字典序输出全排列的方法。

首先，对于集合A的某种排列所形成的序列，字典序是比较序列大小的一种方式。

以$A=\{1,2,3,4\}$为例，其所形成的排列$1234<1243$，比较的方法是从前到后依次比较两个序列的对应元素，如果当前位置对应元素相同，则继续比较下一个位置，直到第一个元素不同的位置为止，元素值大的元素在字典序中就大于元素值小的元素。

上面的$a_1[1...4]=1234$和$a_2[1...4]=1243$，对于$i=1,i=2$，两序列的对应元素相等，但是当$i=2$时，有$a_1[2]=3<a_2[2]=4$，所以$1234<1243$​​

使用字典序输出全排列的思路是，首先输出字典序最小的排列，然后输出字典序次小的排列，……，最后输出字典序最大的排列。这里就涉及到一个问题，对于一个已知排列，如何求出其字典序中的下一个排列。这里给出算法。

• 对于排列$a[1...n]$，找到所有满足$a[k]<a[k+1](0<k<n-1)$的k的最大值，如果这样的k不存在，则说明当前排列已经是a的所有排列中字典序最大者，所有排列输出完毕。
• 在$a[k+1...n]$中，寻找满足这样条件的元素l，使得在所有$a[l]>a[k]$的元素中，$a[l]$取得最小值。也就是说$a[l]>a[k]$，但是小于所有其他大于$a[k]$​的元素。
• 交换$a[l]$与$a[k]$.
• 对于a[k+1...n]，反转该区间内元素的顺序。也就是说a[k+1]与a[n]交换，a[k+2]与a[n-1]交换，……，这样就得到了a[1...n]在字典序中的下一个排列。

这里我们以排列$a[1...8]=13876542$​为例，来解释一下上述算法。首先我们发现，1(38)76542，括号位置是第一处满足$a[k]<a[k+1]$的位置，此时k=2。所以我们在a[3...8]的区间内寻找比$a[2]=3$大的最小元素，找到$a[7]=4$满足条件，交换a[2]和a[7]得到新排列14876532，对于此排列的3～8区间，反转该区间的元素，将$a[3]-a[8]，a[4]-a[7]，a[5]-a[6]$分别交换，就得到了13876542字典序的下一个元素14235678。下面是该算法的实现代码

/*
 * 将数组中的元素翻转
 */
inline void Reverse(unsigned int* array, size_t array_size)
{
    for(unsigned i = 0; 2 * i < array_size - 1; ++i)
    {
        unsigned int t = array[i];
        array[i] = array[array_size - 1 - i];
        array[array_size - 1 - i] = t;
    }
}

inline int LexiNext(unsigned int* lexinum, size_t array_size)
{
    unsigned int i, j, k, t;

    i = array_size - 2;

    while(i != UINT_MAX && lexinum[i] > lexinum[i + 1])
    {
        --i;
    }

    //达到字典序最大值
    if(i == UINT_MAX)
    {
        return 1;
    }

    for(j = array_size - 1, k = UINT_MAX; j > i; --j)
    {
        if(lexinum[j] > lexinum[i])
        {
            if(k == UINT_MAX)
            {
                k = j;
            }
            else
            {
                if(lexinum[j] < lexinum[k])
                {
                    k = j;
                }
            }
        }
    }

    t = lexinum[i];
    lexinum[i] = lexinum[k];
    lexinum[k] = t;

    Reverse(lexinum + i + 1, array_size - i - 1);
    return 0;
}

/*
 * 根据字典序输出排列
 */
inline void ArrayPrint(const char* array, size_t array_size, const unsigned int* lexinum)
{
    for(unsigned int i = 0; i < array_size; ++i)
    {
        cout << array[lexinum[i]] << ' ';
    }

    cout << '\n';
}

/*
 * 基于逆序数的全排列输出
 */
void FullArray(char* array, size_t array_size)
{
    unsigned int lexinumber[array_size];

    for(unsigned int i = 0; i < array_size; ++i)
    {
        lexinumber[i] = i;
    }

    ArrayPrint(array, array_size, lexinumber);

    while(!LexiNext(lexinumber, array_size))
    {
        ArrayPrint(array, array_size, lexinumber);
    }
}

使用字典序输出集合的全排列需要注意，因为字典序涉及两个排列之间的比较，对于元素集合不方便比较的情况，可以将它们在数组中的索引作为元素，按照字典序生成索引的全排列，然后按照索引输出对应集合元素的排列，示例代码使用的就是此方法。对于集合$A=\{a,b,c,d\}$，可以对其索引1234进行全排列生成。这么做还有一个好处，就是对于字典序全排列生成算法，需要从字典序最小的排列开始才能够生成集合的所有排列，如果原始集合A中的元素不是有序的情况，字典序法将无法得到所有的排列结果，需要对原集合排序之后再执行生成算法，生成索引的全排列，避免了对原始集合的排序操作。

字典序算法还有一个优点，就是不受重复元素的影响。例如1224，交换中间的两个2，实际上得到的还是同一个排列，而字典序则是严格按照排列元素的大小关系来生成的。对于包含重复元素的输入集合，需要先将相同的元素放在一起，以集合$A=\{a,d,b,c,d,b\}$​为例，如果直接对其索引123456进行全排列，将不会得到想要的结果，这里将重复的元素放到相邻的位置，不同元素之间不一定有序，得到排列$A^\prime=\{a,d,d,b,b,c\}$，然后将不同的元素，对应不同的索引值，生成索引排列122334，再执行全排列算法，即可得到最终结果。

1.5.3 SJT(换位法)

初始状态$\overleftarrow{1},\overleftarrow{2},\cdots ,\overleftarrow{n-1},\overleftarrow{n},$

1. 找到最大的可移动数m(当一个数指向一个比它小的数是，该数就是可移动数)

2. 交换m和m所指向的数

3. 改变所有比m大的数的方向

4. 重复上面的步骤，直至找不到可移动数

//邻位对换法
void exchange(int length){
    Item * data = (Item *)malloc(sizeof(Item) * length);
    int index, indexOfMax;
    for (index = 0; index < length; ++index){
        data[index].digit = index + 1;
        data[index].direction = -1;
        data[index].mobile = (index != 0) ? 1 : 0;
    }
    indexOfMax = length - 1;
    FILE * fp = fopen("exchange.txt", "w");
    exPrint(data, length, fp);
    while (1== data[indexOfMax].mobile || existMobile(data, length)){
        if (1== data[indexOfMax].mobile){
            int direction = data[indexOfMax].direction;
            exSwap(data, indexOfMax, indexOfMax+direction);
            indexOfMax += direction;
            if ((indexOfMax == 0 && direction == -1) || (indexOfMax == length-1 && direction == 1)){
                toMobileorNot(data, length);
            }
        } else{
            index = findMax(data, length);
            if (index == -1)
                break;
            int direction = data[index].direction;
            exSwap(data, index, index + direction);
            index += direction;
            changeDirection(data, length, index);
            toMobileorNot(data, length);
        }
        exPrint(data, length, fp);
    }
    fclose(fp);
    free(data);
}
 
int existMobile(Item data[], int length){//判断是否存在可移动数
    int index;
    for (index = 0; index < length; ++index){
        if (data[index].mobile == 1)
            return 1;
    }
    return 0;
}
 
int findMax(Item data[], int length){//找到最大的可移动数
    int ans = -1;
    for (int index = 0; index < length; ++index){
        if (data[index].mobile == 1){
            if (ans == -1)
                ans = index;
            else if (data[index].digit > data[ans].digit)
                ans = index;
        }
    }
 
    return ans;
}
 
void changeDirection(Item data[], int length, int index){//改变大于可移动数的数的方向
    for (int i = 0; i < length; ++i){
        if (data[i].digit > data[index].digit){
            data[i].direction = -data[i].direction;
        }
    }
}
 
void toMobileorNot(Item data[], int length){
    if (data[0].direction == 1 && data[0].digit > data[1].digit)
        data[0].mobile = 1;
    else
        data[0].mobile = 0;
 
    for (int i = 1; i < (length - 1); ++i){
        int direction = data[i].direction;
        if (data[i].digit > data[i+direction].digit)
            data[i].mobile = 1;
        else
            data[i].mobile = 0;
    }
 
    if (data[length-1].direction == -1 && data[length-1].digit > data[length-2].digit)
        data[length-1].mobile = 1;
    else
        data[length-1].mobile = 0;
}
 
void exPrint(Item data[], int length, FILE * fp){
    for (int index = 0; index < length; ++index){
        fprintf(fp, "%d ", data[index].digit);
    }
    fprintf(fp, "\n");
}
 
void exSwap(Item data[], int i, int j){
    Item tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
}

1.5.4 序数法

$n$个元素的全排列有$n!$​个，如果将排列按顺序编号，并能够按照某种方法建立起每一个序号与一个排列之间的对应关系，那么就可以根据序号确定排列，反过来也可以根据排列确定它的序号。根据排列的序号生成对应排列的方法就称为序数法。

$$n!=n(n−1)!=[(n−1)+1](n−1)! \\ =(n−1)(n−1)!+(n−1)!$$

同理可得

$$(n−1)!=(n−2)(n−2)!+(n−2)!$$

代入上式可得

$$n!=(n−1)(n−1)!+(n−2)(n−2)!+(n−2)! \\ =(n−1)(n−1)!+(n−2)(n−2)!+(n−3)(n−3)!+⋯+2⋅2!+2! \\ = \sum_{n−1}^{k=1}k⋅k!+1$$

上式减1得

$$n!−1=(n−1)(n−1)!+(n−2)(n−2)!+⋯+2⋅2!+1⋅1!$$

可得到0到$n!-1$的整数m可以唯一地表示为

$$m=a_{k−1}(k−1)!+a_{k−2}(k−2)!+⋯+a_2⋅2!+a_1$$

其中$a_i$满足$0\le a_i\le k,i=1,2,3\cdots,k-1$

所以可以证明0到$n!-1$的$n!$个整数和序数$(a_{n-1},a_{n-2},\cdots,a_2,a_1)$​​

序数法生成全排列算法

由排列$P_1P_2P_3\cdots P_n$对应的序数$(a_{n-1},a_{n-2},\cdots,a_2,a_1)$的规则为$a_i=i+1$的右边比$i+1$小的数字的个数

例1：由排列数确定排列的序号 以1,2,3,4的排列4213为例，排列4213为例，排列4213，4的右边比它小的数有3位，故$ a_3=3$；3的右边比3小的数为0，故$a_2=0$，2的右方比2小的数为1，故$a_1=1$​，故排列4213对应的序数为(301)。 例2：由排列的序号确定排列数

承接上一个例子，$a_3 = 3$，故4在排列中所在的位右方小的数有3个，故在排列数中的第一位为4。$a_2=0$，故3的右方没有比它小的，故在排列数中的第四位上，以此类推，得到最终的排列数为4213。 例三，n=4的序数$(a_3,a_2,a_1)$与对应的排列

1.6 允许重复的组合与不相邻的组合

1.6.1 多重排列

• 在排列中，元素是可以重复的
• 在某些情况下，元素的个数不仅可以重复，而且元素的个数的有限的

我们有若干个元素，$r_1$​个1，$r_2$​和2，$\cdots r_t$​​个$t$.这些元素的个数之和为$n$,name，它的全排列被记为$P(n;r_1,r_2,\cdots,r_t)$

$P(n;r_1,r_2,\cdots,r_t)=\frac{n!}{r_1!r_2!\cdots r_t!}$​

重要应用:二项式定理

$(a+b)^n=\sum_{0\le k\le n}\frac{n!}{k!(n-k)!a^kb^{n-k}}=\sum_{o\le k\le n}C(n,k)a^kb^{n-k}$​

根据多重排列，可以推出-->多项式定理

$(a_1+a_2+\cdots+a_t)^n=\sum \frac{n!}{r_1!r_2!\cdots r_t!}a^{r_1}\cdots a_t^{r_t}$

例子-->乒乓球入洞游戏

共有6个洞口，洞口每次只能进入一个乒乓球，一组编号为1-9的9个乒乓球滚入洞口的方案有多少?

解决方案

• 门板标号后为14个元素全排列
• 门板标号方案数为5
• 所以方案数为$\frac{14!}{5!}=726485760$

解决方案二-->隔板法

1.6.2 可重组合

可重组合概念介绍

从$A=\{1,2,3,\cdots,n\}$中取$r$个元素$\{a_1,a_2,\cdots,a_r\},a_i\in A,i=1,2,\cdots,r$，且允许$a_i=a_j,i\le j,$记为$\overline{C}(n,r)$​

在$n$个不同的元素中取$r$个进行组合，允许重复的组合数为$C(n+r-1,r)$

问题一

一个水果盘有4个梨，2个橘子，2个橙子，在果盘中选取4个水果，会产生多少种结果？？

解决方案--》门框隔离法

可以看出结果为$C(n+r-1,r)$

问题二

已知线性方程$x_1+x_2+\cdots+x_n=b$，n和b都是整数，$n\ge 1$，求此方程的非负整数解的个数？？

定理：线性方程$x_1+x_2+\cdots+x_n=b$​的非负整数解为$C(n+b-1,b)$

1.6.3 不相邻组合

定义

不相邻的组合是指从$A=\{1,2,\cdots,n\}$中取$r$个不相邻的数进行组合(不可重),即不存在相邻的两个数$j,j+1$​​的组合。

结论

$A=\{1,2,\cdots,n\}$中取$r$个不相邻的数进行组合与从$(n-r+1)$个元素中取$r$个进行无重组合一一对应，其组合数为$C(n-r+1,r)$

例子

例$n=6,r=3$的不相邻组合有$\{1,3,5\},\{2,4,6\}$

1.7 组合的意义

1.7.1 Stirling公式

在组合数学中经常遇见$n!$的计算。$n!$增长速度极快。给出了近似求$n!$的近似公式

$$n!\sim \sqrt{2n\pi}(\frac{n}{e})^n$$