排列数与组合数
排列数
从nnn个元素中取出mmm个元素,按照一定的顺序排成一列,叫做从nnn个元素中取出mmm个元素的排列。这样的全部的排列个数,叫做排列数,写作 AnmA^m_nAnm 。
组合数
从nnn个不同元素中,不停地重复选择mmm个元素打一个组合,这样打组合打总数叫做组合数,写作 ∗∗∗∗∗*****∗∗∗∗∗。
二项式定理
『(a+b)n=Cn0an+Cn1an−1b+Cn2an−2b2+……+Cnkan−kbk+Cnnbn』极长的二项式定理\color{#03BEF4}\mathsf{『(a + b)^n = C^0_na^n + C^1_na^{n-1}b + C^2_na^{n-2}b^2+…… + C^k_na^{n-k}b^k+C^n_nb^n』}\\\scriptsize\mathsf{极长的二项式定理} 『(a+b)n=Cn0 an+Cn1 an−1b+Cn2 an−2b2+……+Cnk an−kbk+Cnn bn』极长的二项式定理
##基本概念
二项式展开式:等式右边的多项式叫做(a+b)n(a+b)^n(a+b)n的二项展开式
二项式系数:展开式中的各项系数
项数:二项式总共有n+1n+1n+1项
通项:展开式的第k+1k+1k+1项,记作Tk+1=Cknan−kbkT_{k+1} = C^n_k a^{n-k} b^kTk+1 =Ckn an−kbk
二项式定理性质
二项式系数对称性:展开式中,与首末两项等距的任意两项二项式系数相等
Ckn=Cn−knC^n_k = C^n_{n-k}Ckn =Cn−kn
二项式系数最大值:
展开式中,最中间那一项(或中间两项)的二项式系数最大
当nnn为偶数时,最大二项式系数为Cnn/2C^{n/2}_nCnn/2
当nnn为奇数时,最大二项式系数为Cn(n−1)/2C^{(n-1)/2}_nCn(n−1)/2
二项式系数和
二项展开式中,所以二项式的系数和等于2n2^n2n,即:
Cnn+Cn1+Cn2+Cn3+⋅⋅⋅+c2n=2nC^n_n+C^1_n+C^2_n+C^3_n+···+c^n_2=2^nCnn +Cn1 +Cn2 +Cn3 +⋅⋅⋅+c2n =2n
奇数项中二项式系数和等于偶数项二项式系数和,即:
Cn0+Cn2+Cn4+⋅⋅⋅Cn1C^0_n+C^2_n+C^4_n+···C^1_nCn0 +Cn2 +Cn4 +⋅⋅⋅Cn1
卡特兰数递推式
H(n)=(4n−2/n+1)H(n−1)H(n)=(4n-2/n+1)H(n-1)H(n)=(4n−2/n+1)H(n−1)
H(n)=C2nn−C2nn−1H(n)=C^n_{2n}-C^{n-1}_{2n}H(n)=C2nn −C2nn−1
H(n)=1/n+1C2nnH(n)=1/n+1C^n_{2n}H(n)=1/n+1C2nn
H(n)=4n−2/n+1H(n−1)H(n)=4n-2/n+1H(n-1)H(n)=4n−2/n+1H(n−1)
斯特林数字
S(n,m)=m∗S(n−1,m)+S(n−1,m−1)S(n,m)=m*S(n-1,m)+S(n-1,m-1)S(n,m)=m∗S(n−1,m)+S(n−1,m−1)
『i=0为边界』\color{#FA4129}\mathsf{『i=0为边界』}\\\scriptsize\mathsf{} 『i=0为边界』
S(i,j)=J∗S(i−1,J)S(i,j)=J*S(i-1,J)S(i,j)=J∗S(i−1,J)