排列和组合 一

2021-04-11  本文已影响0人  acc8226

排列 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

上一篇下一篇

猜你喜欢

热点阅读