了解置换公式:C(n+1,m) = C(n,m) + C(n,m-1)
最编程
2024-04-08 17:10:06
...
我昨天在琢磨该如何理解这个组合公式,代数的推导对理解和记忆我觉得帮助不是很大,只有能够理解公式的内涵才算是真的懂了。
C(n+1,m) = C(n,m) + C(n,m-1)。
很有意思的是,我去百度了下,虽然有人提出了相同的问题。不过“大神”的回答只有一句话 :“假定一种情形”。然后就没了,有点摸不到头脑。
还好脑子没锈,思考了一下,哦,原来是这么回事:
想像一个装有n个球的袋子,和一个单独的球,想要丛中取出m个球:
1.直接思考,显然方式为C(n+1,m).
2。考虑是否取得单独的球,分情况讨论:
A。不取单独的球,则方法为C(n,m).
B. 考虑取得单独的球,则方法为c(n-1,m).
二者等价,即为原来等式的左右两端。证明完毕。
推荐阅读
-
计算组合数 c(n,m) 的四种方法
-
组合数 C(m,n)
-
寻找组合数 C(m,n) 的多种计算方法
-
解组合数 C(n,m) 的四种方法
-
了解置换公式:C(n+1,m) = C(n,m) + C(n,m-1)
-
寻找组合数 C(m,n) 的多种计算方法
-
组合数问题(组合数学 + 二维前缀和)--分析:有多组数据,肯定要考虑预处理,然后(O(1) answer\).\n,m<;=2000\)可以考虑线性递归的组合数\(C[i][j]=C[i-1][j]+C[i-1][j-1]\),因为只有k的倍数才会对答案有贡献、所以可以直接对 k 模进行递归,然后进行二维前缀和 \(f[i][j]=f[i-1][j]+f[i][j -1]-f[i-1][j-1]\) 计算时只需看是否为零即可。
-
计算组合数 C(n,m)
-
C 回溯 实现组合数 从 N 个数中选择 M 个数
-
数论杂谈 - 利用模块快速求解组合数 C(n,m)