二项式系数与基本计数
二项式系数计算从有限集中选择固定大小子集的方法数量，是组合枚举的基本组成部分。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
二项式系数 C(n,k) 是从 n 个元素的集合中选择 k 个元素的子集的数量，等于 n!/(k!(n-k)!)；基本计数是将加法和乘法法则系统地应用于有限配置。
Scope
本主题探讨基本的计数原理——加法法则和乘法法则——以及二项式系数 C(n,k) 的核心作用、其恒等式（帕斯卡法则、二项式定理、范德蒙德恒等式）及其在帕斯卡三角形中的出现。它建立了所有枚举组合学赖以构建的基本工具包。
Core questions
- 从 n 个不同的对象中选择 k 个对象有多少种方法？
- 加法和乘法法则如何分解计数问题？
- 哪些恒等式将二项式系数与二项式定理联系起来？
- 帕斯卡三角形如何递归地编码这些系数？
Key concepts
- 加法法则和乘法法则
- 排列与组合
- 阶乘
- 帕斯卡三角形
- 范德蒙德恒等式
- 多项式系数
Key theories
- 二项式定理
- 展开式 (x+y)^n = C(n,k) x^k y^(n-k) 的求和形式将二项式系数表示为二项式幂中的代数系数，将计数与多项式代数联系起来。
- 帕斯卡法则
- 递推关系 C(n,k) = C(n-1,k-1) + C(n-1,k) 从其上方的两个二项式系数构建每个二项式系数，生成帕斯卡三角形并反映所选子集是否包含一个特定元素。
Clinical relevance
二项式系数是二项式概率分布、组合算法分析以及任何需要计算无序选择的场景的基础，使其在概率论、统计学和计算机科学中无处不在。
History
二项式系数的三角形排列在中国、波斯和印度数学中出现的时间比帕斯卡在1654年的论著早了几个世纪，后者才在西方赋予了这种结构持久的名称。
Key figures
- Blaise Pascal
- Isaac Newton
Related topics
Seminal works
- stanley2011
Frequently asked questions
- 排列和组合有什么区别？
- 排列计算顺序重要的排列方式；组合（由二项式系数计算）计算顺序无关的选择方式。
- 为什么 C(n,0) 等于 1？
- 从一个集合中选择零个元素（即空子集）只有一种方法，因此零元素子集的数量为一。