组合数

灵感来源： 算法课

一、定义及性质

想必大家高中时就已接触过组合数，组合数是这样定义的：
  从含有 $n$n 个元素的集合中，挑选出 $r$r 个元素组成子集，不考虑元素的排列次序，所能形成的子集的个数就称为组合数，记为 $\displaystyle C_n^r$Cnr​，计算公式如下：
$C_n^r = \frac{n!}{r!(n-r)!}$Cnr​=r!(n−r)!n!​

关于组合数，有很多巧妙的性质：

1. 根据定义不难得出 $C_n^r = C_n^{n-r}$Cnr​=Cnn−r​.

2. 考虑 $C_n^0+C_n^1+C_n^2+\cdots+C_n^n$Cn0​+Cn1​+Cn2​+⋯+Cnn​ 的值，这是什么意思呢？
   不难看出，这就是集合的全部子集个数(含空集). 如果用
   $x_j = \begin{cases} 1,\textrm{ 第 $j$ 个元素被选取}\\ 0,\text{ otherwise} \end{cases} j = 1,2,\cdots,n$xj​={1, 第 j 个元素被选取0, otherwise​j=1,2,⋯,n

   来表示每个元素被选取的情况，可知，每个元素都有两种可能，所以一共有 $2^n$2n 种可能，即 $C_n^0+C_n^1+C_n^2+\cdots+C_n^n = 2^n$Cn0​+Cn1​+Cn2​+⋯+Cnn​=2n.

3. $C_{n+1}^r = C_n^r + C_n^{r-1}$Cn+1r​=Cnr​+Cnr−1​. 下面来解释一下：

   首先将 $n+1$n+1 个元素分为两部分：元素 $i$i 和其他元素($i$i 为任意给定的 $1$1 到 $n$n 之间的数).

   $C_{n+1}^r$Cn+1r​ 是指从 $n+1$n+1 个元素中选出 $r$r 个元素的可能组合数目. 分为两种情况考虑：

   • 这 $r$r 个元素中不含元素 $i$i，那么需要从剩余的元素中选出 $r$r 个元素，可能的数目为 $C_n^{r}$Cnr​.
   • 这 $r$r 个元素中含有元素 $i$i，那么只需从剩余的元素中选出 $r-1$r−1 个元素即可，可能的数目为 $C_n^{r-1}$Cnr−1​.

​ 所以，总的可能数 $C_{n+1}^r = C_n^r + C_n^{r-1}$Cn+1r​=Cnr​+Cnr−1​.

二、计算方法

在实际计算组合数时，当然，我们可以根据组合数的定义进行计算，即直接套用公式：
$C_n^r = \frac{n!}{r!(n-r)!}$Cnr​=r!(n−r)!n!​

但如果我想说的只是这样，就不会有这篇文章了.

哦？那你想说什么？

一种循环迭代的求解思路. 根据前面的性质，有
$C_{n}^r = \begin{cases} 1,r\in \{0,n\}\\ C_{n-1}^r + C_{n-1}^{r-1} \end{cases}$Cnr​={1,r∈{0,n}Cn−1r​+Cn−1r−1​​

有了递推关系，就能直接写出递归程序，但这样做看不清背后的细节.

先将递推关系表示成表格形式(将一组依赖关系和初值给出)

其中 $i$i 表示组合数中的上标，$j$j 表示下标.

之后给出所有的依赖关系

可以看出，$C_n^r$Cnr​ 值的计算依赖于平行四边形区域中的值. 该区域共有 $r+1$r+1 行，宽度为 $n-r+1$n−r+1，将其重新排列为长方形：

所以有两种计算思路：一种是一行一行地计算，一种是一列一列地计算，两种方法的实现是完全一样的.
可以用一个二维数组来计算，但这样做，算法的空间复杂度为 $O(r(n-r))$O(r(n−r))，可不可以再降低一点呢？

当然可以. 可以看出，计算新的一行或新的一列时只用到了前一行或者前一列的值，所以可以通过不断更新一个一维数组来实现：若是按行计算，空间复杂度为 $O(n-r)$O(n−r)；若是按列计算，空间复杂度为 $O(r)$O(r).

这里采用按行计算的方式，代码(含递归法)如下：

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)

// 1. 循环迭代计算
int cn1(n, r) 
{
	if(r < n-r)
		r = n-r;

	int *a = malloc((n-r+1)*sizeof(int));
	int i, j;
	int tmp;

	// 初始化首行的值 
	for(i = 1; i <= n-r; i++)
		a[i] = 1;

	// 依次计算第 i 行的值
	for(i = 1; i <= r; i++) 
	{
		a[1] = a[1] + 1;
		for(j = 2; j <= n-r; j++)
			a[j] = a[j] + a[j-1];
	}

	tmp = a[n-r];
	free(a);
	return tmp;
}

// 2. 递归计算
int cn2(n, r)
{
	if(r == 0 || r == n)
		return 1;
	return cn2(n-1, r) + cn2(n-1, r-1);
}

// 主程序
int main(void) 
{
	int n, r;
	int result1, result2;

	printf("请输入参数 n 和 r(空格分隔)：\n");
	scanf("%d%d", &n, &r);

	result1 = cn1(n, r);
    result2 = cn2(n, r);

	printf("循环迭代法的计算结果为：%d.\n", result1);
	printf("递归法的计算结果为：%d.\n", result2);

	return 0;
}

因为 $C_n^{r} = C_n^{n-r}$Cnr​=Cnn−r​，所以，若 $n-r > r$n−r>r，那么我们可以按行计算 $C_n^{n-r}$Cnn−r​，保证空间复杂度为 $O(\min\{n-r,r\})$O(min{n−r,r}).