排列和组合一

作者: acc8226 | 来源:发表于2021-04-11 21:10 被阅读0次

排列 permutation

$P_n^r$ 或者 $P(n, r)$

基本模型就是放球模型. 从 n 个取出 r 个不同的盒子里(盒子有顺序)
$\begin{align} P(n, r) & = n(n-1)(n-2) \cdots (n-r+1) \\ & = {n! \over (n-r)! }\end{align}$

全排列 $P(n, n) = n!$

排列组合的递推关系
第一个关系:
$P(n, r) = nP(n-1, r-1)$

第二个关系:
取第一个球 n种可能乘以 n-1个球 * r-1个盒子
不取第一个球则是 n-1个球 * r个盒子
$P(n, r) = nP(n-1, r-1) + P(n-1, r)$

$P(n,0) = n!/(n-0)! = 1 /1 = 1$

组合

就是全排列除以 r的全排列
$\begin{align} C(n, r) & = {n! \over {r! (n-r)!} }\end{align}$

n 个球选出 r 个自然就等于剩下的 n - r 个方法
$C(n, r) = C(n, n-r)$

组合模型(分析的话结合选班委的案例)
$C(n, r) C(r, l) = C(n, l)C(n-r, l-r)$

举例:
由于 $0!=1$
所以 $C(n,0)=C(n,n)=1$

分析: 4个球中取5个做组合的方案有0种
$C(4,5)$ = 0

隔路模型

和组合相关
c(m+n, n) 就是(0,0) 移动到(m, n)点

组合恒等式

C(n, r) = C(n-1, r-1) + C(n-1, r)

C(m+n, r) = C(m, 0)C(n, r) + C(m, 1)C(n, r-1) + ... + C(m, r)C(n, 0)

圆排列

从 n 个中取出 r 个, 排列数等于 $P(n, r) / r. 2<=r<=n$
相当于全排列中出去r个可以裁剪的位置

八卦图是圆排列, 它的个数为 8! / 8

项链排列

从 n 个中取出 r 个, 排列数等于 $P(n, r) / 2r. 3<=r<=n$
相当于在圆排列的基础上再考虑翻转这种情况.

多重排列

pingpang 8个字母能有多少种排列

无重排列再去重.
我们有若干个元素, r1个1, r2个2, ... rt个t, 元素个数之和为t, 那么它的全排列被记为: $P(n_;r_1,r_2 \cdots ,r_t) = {n! \over r_1!r_2! \cdots r_t! }$

二项式定理:
$(a + b)^n = \sum_{0 \le k \le n} {n! \over k! (n-k)! }a^{k} b^{n-k} =\sum_{0 \le k \le n} C(n, k)a^{k} b^{n-k}$

多项式定理:
$(a_1 + a_2 + \cdots + a_t)^n = \sum{n! \over r_1!r_2! \cdots r_t! }a_1^{r1} \cdots a_t^{rt}$

举例: 乒乓球入洞问题
编号1~9的球分别进入6个洞口, 有多少种入洞的方案.

可重组合

在 $A = \lbrace{1, 2, 3, \cdots n}\rbrace$ 中取出 r 个元素 $\{a_1, a_2, a_3, \cdots a_r \}, 且 a_i \in A, i = 1, 2, \cdots, r$ , 且允许 $a_i = a_j, i \neq j$

排列和组合一

排列 permutation

组合

隔路模型

组合恒等式

圆排列

项链排列

多重排列

可重组合

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

排列和组合 一

排列 permutation

组合

隔路模型

组合恒等式

圆排列

项链排列

多重排列

可重组合

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

排列和组合一