组合数学基础

本文主要是介绍组合数学基础，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

组合数

\(1.\) 对称性

\[\binom{n}{k}=\binom{n}{n-k} \]

\(2.\) 加法公式

\[\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} \]

其组合意义为钦定最后一个数选或不选的方案数相加。

\[\sum_{i=0}^{n}\binom{n}{i}=2^n \]

其组合意义为所有的选数方案恰好对应了每一个数选或不选的方案数。

\[\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k} \]

其组合意义为从 \(n\) 个数中选取 \(m\) 个数，再从这 \(m\) 个数中选择 \(k\) 个数的方案数等于从 \(n\) 个数中选取 \(k\) 个数，再从剩下的 \(n-k\) 个数中选取 \(m-k\) 个数。

\(3.\) 上指标求和

\[\sum_{i=0}^{n}\binom{i}{k}=\binom{n+1}{k+1} \]

其组合意义为从 \(n + 1\) 个数中选择 \(k + 1\) 个数的方案数。其等价于钦定最后一个选择的元素是第 \(i + 1\) 个，在前 \(i\) 个数中选择 \(k\) 个数的方案数之和。
其对应在杨辉三角上如图所示：

绿色框中的数等于黄色的选中的数相加的和。
具体证明可结合杨辉三角。

\(4.\) 平行求和

\[\sum_{i=0}^{k}\binom{n+i}{i}=\binom{n+k+1}{k} \]

平行求和可将每一项利用对称性转化为上指标求和。
其对应在杨辉三角上如图所示：

绿色框中的数等于黄色的选中的数相加的和。
具体证明可结合杨辉三角。

这篇关于组合数学基础的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！