排列组合、牛顿二项式定理、多项式系数

Post author:xfxia
Post published:2023年9月13日
Post category:其他

排列组合

四个原理
- 排列组合总结
- 练习题
二项式系数

四个原理

加法原理

：划分成互不相交的子集
$s_1,s_2,s_3,\dots,s_m$

即：分类讨论，不重不漏

如果有相交，可以用容斥原理

技巧：划分成少量易处理的部分

乘法原理

：第一项任务有p个结果，第二项任务有q个结果。那么合起来就有
$p\times q$
个结果。

加法原理只有一个任务，每个任务都是一种选择

而乘法原理是多个子任务的组合，每个子任务合并起来是一种选择

减法原理

： A= U – A补。当A的补集比A更容易计算时

除法原理

：把有限集S划分成k个部分，使得每一部分包含的对象数目相同。

$k=\frac {|S|}{在一个部分中的对象数目}$

排列组合总结

$\begin{cases} 集合{ \begin{cases} 排列（r排列）：P_n^r=n\times(n-1)\times \dots\times(n-r+1)=\frac {n!}{(n-r)!}\\ \\ 组合（r组合）：C_n^r=\frac {n\times(n-1)\times \dots\times(n-r+1)}{r!}=\frac {n!}{(n-r)!r!} \end{cases} }\\ \\ 多重集合{ \begin{cases} k种元素总和为n的有限多重集{ \begin{cases} 排列{ \begin{cases} n排列:\frac {n!}{n_1!n_2!\dots n_k!}\\ \\ r排列：指数生成函数（x^n的系数就是排列数） \end{cases} }\\ \\ 组合（r组合）：普通生成函数（x^n的系数就是组合数） \end{cases} }\\ \\ k种元素的无限多重集{ \begin{cases} 排列（r排列）：k^r,每个位置有k种选择，一共有r个位置\\ \\ 组合（r组合）：C_{r+k-1}^r,选择r个元素，有k-1块板\\ 相当于x_1+x_2+\dots+x_k=r的非负整数解 \end{cases} } \end{cases} } \end{cases}$

原文链接：https://blog.csdn.net/cheng__yu_/article/details/105827113

排列组合

四个原理

排列组合总结

你可能也喜欢