二项式系数学习笔记 二项式系数学习笔记

1.二项式定理

(dbinom{n}{k}=dbinom{n-1}{k}+dbinom{n-1}{k-1})

(kdbinom{n}{k}=ndbinom{n-1}{k-1})

(dbinom{n}{0}+dbinom{n}{1}+dotsb+dbinom{n}{n}=2^n (ngeq 0))

(dbinom{n}{0}+dbinom{n}{2}+dotsb=dbinom{n}{1}+dbinom{n}{3}+dots=2^{n-1} (ngeq 1))

(1dbinom{n}{1}+2dbinom{n}{2}+dotsb+ndbinom{n}{n}=n2^{n-1} (ngeq 1))

(1dbinom{n}{1}+4dbinom{n}{2}+9dbinom{n}{3}+dotsb+n^2dbinom{n}{n}=n(n+1)2^{n-2} (ngeq 1))

二项式定理

((x+y)^n=sumlimits_{k=0}^{n}dbinom{n}{k}x^{n-k}y^k=sumlimits_{k=0}^{n}dbinom{n}{k}x^k y^{n-k})

((1+x)^n=sumlimits_{k=0}^{n}dbinom{n}{k}x^k)

(((1+x)^n)^{'}=left(sumlimits_{k=0}^{n}dbinom{n}{k}x^k ight)^{'}=sumlimits_{k=1}^{n}kdbinom{n}{k}x^{k-1})

令 (x=1), 得 (n2^{n-1}=sumlimits_{k=1}^{n}kdbinom{n}{k})

如此求导操作，即可得到(sumlimits_{k=1}^{n}k^pdbinom{n}{k})相对于任何正整数(p)的恒等式。

(sumlimits_{k=0}^{n}dbinom{n}{k}^2=dbinom{2n}{n} (ngeq 0)) 由Vandermonde卷积即可证明。

(dbinom{r}{0}+dbinom{r+1}{1}+dotsb+dbinom{r+k}{k}=dbinom{r+k+1}{k} (rin R , kin Z))

Vandermonde 卷积:

对于所有的正整数 (m_1,m_2) 和 (n)，有(sumlimits_{k=0}^{n}dbinom{m_1}{k}dbinom{m_2}{n-k}=dbinom{m_1+m_2}{n})

证明 Vandermonde 卷积:
设大小为(m_1+m_2)的集合(S)，把(S)任意划分为(A,B)两集合，且(|A|=m_1,|B|=m_2)，则对(S)划分(n)子集等价于对 (A) 划分 (k) 子集和对 (B) 划分 (n-k) 子集，由加法原理可知， Vandermonde 卷积公式成立。

应用1: (sumlimits_{k=1}^{n}kdbinom{n}{k}^2=ndbinom{2n-1}{n-1})

证明:
(sumlimits_{k=1}^{n}kdbinom{n}{k}^2=sumlimits_{k=1}^{n}kdbinom{n}{k}dbinom{n}{k}=nsumlimits_{k=1}^{n}dbinom{n-1}{k-1}dbinom{n}{k}=nsumlimits_{k=0}^{n}dbinom{n-1}{n-k}dbinom{n}{k}=ndbinom{2n-1}{n}=ndbinom{2n-1}{n-1})

应用2: (sumlimits_{k=1}^{n}dbinom{n}{k}dbinom{n}{k-1}=dbinom{2n}{n-1})

证明:
(sumlimits_{k=1}^{n}dbinom{n}{k}dbinom{n}{k-1}=sumlimits_{k=1}^{n}dbinom{n}{n-k}dbinom{n}{k-1})
令 (r=k-1)，得 (sumlimits_{k=1}^{n}dbinom{n}{n-k}dbinom{n}{k-1}=sumlimits_{r=0}^{n-1}dbinom{n}{n-1-r}dbinom{n}{r}=dbinom{2n}{n-1})

2.二项式系数的单峰性

二项式系数的单峰性

对于正整数(n)，二项式系数(dbinom{n}{0},dbinom{n}{1},dbinom{n}{2},dotsb,dbinom{n}{n})中的最大者为(dbinom{n}{leftlfloorfrac{n}{2} ight floor}=dbinom{n}{leftlceilfrac{n}{2} ight ceil})。

Sperner 定理:

设 (S) 是 (n) 元素集合。(S)的反链是集合 (S) 的子集的一个集合 (mathcal{A})，其中 (mathcal{A}) 中的子集不互相包含。则 (S) 上的一个反链最多包含(dbinom{n}{leftlfloorfrac{n}{2} ight floor}=dbinom{n}{leftlceilfrac{n}{2} ight ceil})个集合。

构造这样一个(S)上最大的反链的方法是取(k=leftlfloorfrac{n}{2} ight floor=leftlceilfrac{n}{2} ight ceil)，然后取 (mathcal{A_k}) 为 (S) 所有的 (k) 子集。

(S) 的最大链的数目等于(n!)。

3.多项式定理

((x_1+x_2+dots+x_t)^n)，多项式系数为(dbinom{n}{n_1,n_2,dots,n_t}=frac{n}{n_1!n_2!dotsb n_t!})，其中(n_1,n_2,dots,n_t)是非负整数且(n_1+n_2+dots+n_t=n)

多项式系数的帕斯卡公式是(dbinom{n}{n_1,n_2,dots,n_t}=dbinom{n-1}{n_1-1,n_2,dots,n_t}+dbinom{n-1}{n_1,n_2-1,dots,n_t}+dotsb+dbinom{n-1}{n_1,n_2,dots,n_t-1})

多项式定理

((x_1+x_2+dots+x_t)^n=sumdbinom{n}{n_1,n_2,dots,n_t}x_1^{n_1}x_2^{n_2}dotsb x_t^{n_t})

其中
(dbinom{n}{n_1,n_2,dots,n_t}=dbinom{n}{n_1}dbinom{n-n_1}{n_2}dotsbdbinom{n-n_1-dotsb-n_{t-1}}{n_t}=frac{n}{n_1!n_2!dotsb n_t!})