排列
(n) 个不同元素 任取 (m) 个 有序
[A^m_n=frac{n!}{(n-m)!}
]
全排列
不全相异元素全排列
在 (n) 个元素中，有 (n_1) 个元素彼此相同，又有 (n_2) 个元素彼此相同... 又有 (n_m) 个元素彼此相同（ (sumlimits_{i=1}^mn_i=n) ）
[frac{n!}{n_1!n_2!ldots n_m!}
]
相异元素可重复全排列
n个位置，每个位置上有m种选择
[n^m
]
选排列
n的降r阶乘
[n！(n-r)!
]
全错位排列
设有一串数1到n，对应位置1到N，设n排在了第K位（(1le K<N) ) ，考虑第N位的情况
- 当k排在第N位时，除了n和k外还有n-2个数，n-2个数的错排 (f_{n-2})
- 当k不排在第N位时，因为n已经确定位置了，所以剩下n-1个数错排 (f_{n-1})
n放在K位置上有n-1种选法，所以
[f_n=(n-1)(f_{n-1}+f_{n-2})
]
圆排列
n个相异元素的循环全排列
若旋转可得的两种情况则视为一种情况，因为没有首尾之分所以为 (n!/n)
[(n-1)!
]
n个相异元素里每次取出m个元素的循环排列
从n个相异元素里选出m个元素的直线排列种数为 (A^m_n=C^m_n·m!) ，等式的右边为先按组合选出m个元素，再将这m个元素全排列，因为没有首尾之分所以除以m
[x=C^m_n(n-1)!=frac{A^m_n}{m}
]
若不计顺、逆时针方向，再除以2就行了
组合
(n) 个不同元素 任取 (m) 个 无序
[displaystyle C_n^m=frac{n!}{m!(n-m)!}
]
也记做 (displaystyleinom{n}{m}) 读作 「 (n) 选 (m) 」
规定 (displaystyleinom{n}{0} = 1)
性质
- (displaystyleinom{n}{m}=inom{n}{n-m})
- (displaystyleinom{n}{m}=inom{n-1}{m}+inom{n-1}{m-1})
- (displaystyleinom{n}{0}+inom{n}{1}+inom{n}{2}+cdots+inom{n}{n}=2^n)
证明
1.2.略 3.每个数都有选或不选两种可能 自证不难 QED
重复组合
从n个不同元素中，每次取出r个可以重复的元素并成一组，记做 (H^r_n)
[H^r_n=C^r_{n+r-1}=frac{(n+r-1)!}{r!(n-1)!}
]
证明
求组合数
二项式定理
[(a+b)^n=sumlimits^n_{k=0}C_n^ka^kb^k
]
自证不难
证明
数学归纳法 利用 (displaystyleinom{n}{k}+inom{n}{k-1}=inom{n+1}{k}) 做归纳
显然 (n=1) 时是成立的
假设 (n=m) 时命题成立 当 (n=m+1) 时
[(a+b)^{m+1}=(a+b)(a+b)^m\=(a+b)sumlimits_{k=0}^mC^k_ma^kb^{m-k}\=sumlimits_{k=0}^mC_m^ka^{k+1}b^{m-k}+sumlimits_{k=0}^mC_m^ka^{k}b^{m-k+1}\=sumlimits_{k=1}^{m+1}C_m^{k-1}a^{k}b^{m-k+1}+sumlimits_{k=0}^mC_m^ka^{k}b^{m-k+1}\=sumlimits_{k=0}^{m+1}(C_m^k+C_m^{k-1})a^{k}b^{m-k+1}\=sumlimits_{k=0}^{m+1}C_{m+1}^ka^{k}b^{m+1-k}
]
QED