组合数学常用公式

组合数学常用公式

二项式定理

二项式系数相关性质:

  • 对称性:Cnm=CnnmC_n^m = C_n^{n-m}

  • 增减性与最大值:二项式系数前半部分逐渐增大,后半部分逐渐减小,中间取最大值。

    最大值max={Cnn2Cnn12=Cnn+12\text{最大值} max=\begin{cases} C_n^{\frac{n}{2}} \\ C_n^{\frac{n-1}{2}}=C_n^{\frac{n+1}{2}}\end{cases}

  • 二项式系数之和

    Cn0+Cn1+Cn2+Cn3+...+Cnn1+Cnn=2nC_n^0+C_n^1+C_n^2+C_n^3+...+C_n^{n-1}+C_n^n=2^n

  • 二项式奇数项系数之和等于偶数项系数之和,即

    Cn1+Cn3+Cn5+...=Cn0+Cn2+Cn4+Cn6+...=2n1C_n^1+C_n^3+C_n^5+...=C_n^0+C_n^2+C_n^4+C_n^6+...=2^{n-1}

杨辉三角

杨辉三角

组合数公式

CnmC_n^m计算

  • 方式一:公式计算
    计算都是在逆元或者阶乘基础上计算的

Cnm=n!m!(nm)!C_n^m = \frac{n!}{m!*(n-m)!}

ll C(ll n, ll m)
{
	if(n < m) return 0;
	return fact[n] * invfac[m] % mod * invfac[n - m] % mod;
}
  • 方式二:递推方式
    需要建表,所以如果计算范围比较大时需要的空间也大
    递推公式 :

Cnm=Cn1m+Cn1m1C_n^m = C_{n-1}^{m} + C_{n-1}^{m-1}

for(int i = 1; i <= n; i++)
	for(int j = 0; j <= i; j++)
	{
		if(i == j || j == 0) c[i][j] = 1;
		else c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
	}

排列组合方法

1. 隔板法

引入: 10 个相同小球放进 3 个不同盒子,每个盒子至少放进一个, 求种类数。

在10 个小球中间插入隔板, 共有 101=910-1=9 个位置, 需要插入 31=23-1=2 个隔板将其分成 3 部分。 共 C92=36C_9^2 = 36 种。

  • 一般隔板法:

nn 个相同的元素分成 kk 部分,每部分至少分得一个元素, 即在 n1n-1 个空隙中插入 k1k-1 个隔板,情况数为

Cn1k1C_{n-1}^{k-1}

等价于 x1+x2+x3+...+xk=n,xi1x_1+ x_2+x_3+...+x_k=n, x_i \geq 1 的可行解个数。

  • 添元素隔板法:

nn 个相同的元素分成 kk 部分,每部分可以为空, 等价于我们先让元素个数添加上 kk 个,然后在 n+kn+k 个元素中分成 kk 部分, 最后再在 kk 部分的每一个部分都拿走一个元素,共拿走 kk 个元素。 即在 n+k1n+k-1 个空隙中插入 k1k-1 个隔板,情况数为

Cn+k1k1C_{n+k-1}^{k-1}

等价于 x1+x2+x3+...+xk=n,xi0x_1+ x_2+x_3+...+x_k=n, x_i \geq 0 的可行解个数。

此时该式可以转化为一般隔板法, 我们让 xi1x_i \geq 1 即可,操作是将每一个 xix_i 元素加上 11 ,相当于等式两边同时加了 kk ,即 x1+x2+...+xk=n+k,xi1x_1+x_2+...+x_k=n+k,x_i \geq 1 ,即可转化为一般隔板法。

  • 隔板法应用

把10个相同的小球放到3个不同的箱子,第一个箱子至少1个,第二个箱子至少3个,第3个箱子可以为

空,有几种情况?

我们可以在第二个箱子先放入10个小球中的2个,小球剩8个放3个箱子,然后在第三个箱子放入8

个小球之外的1个小球(即补充了一个球),则问题转化为把9个相同小球放3不同箱子,每箱至

少1个,几种方法?

C82=28C^2_8=28


   转载规则


《组合数学常用公式》 行码棋 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
Latex语法 Latex语法
Latex语法 在begin{document}和end{document}之间的就是正文区,而在这之前的就是导言区。 1 宏包导入 \usepackage{宏包1, 宏包2} 2 中文支持 无论是在线工具还是本地工具,LaTeX默认
2023-03-09 2024-02-20
下一篇 
《动手学深度学习》笔记 《动手学深度学习》笔记
本笔记主要参考《动手学深度学习》 进行学习记录,不做无意义的书本内容摘抄。 课程网址:https://courses.d2l.ai/zh-v2/ 使用深度学习框架为:Pytorch 内容不断更新中⋯⋯\cdots \cdots⋯⋯ 2
2023-01-15 2024-10-17
  目录