-
基本公式:
[{n choose k} = {n choose n - k} \ Pascal三角形:{n choose k} = {n - 1 choose k - 1} + {n - 1 choose k}\ 恒等式:sum {n choose i} = 2 ^ n\ 二项式定理: (x + y)^n = sum_{i = 0}^{n} {n choose i} x^i y ^ {n - i} ] -
经验式:
[(r + 1) ^ k = sum_{i = 0}^{k} {k choose i} r ^ i\
k {n choose k} = n {n - 1 choose k - 1}, 证明: (n - 1) - (k - 1) = n - k\
在二项式定理里,令x = 1, y = -1:\
sum_{i = 0}^{n} {n choose i} (-1) ^ n = 0\
移项:sum_{i = 0, i ~is~ odd}^{n} {n choose i} = sum_{i = 0, i ~is~ even}^{n} {n choose i} = 2 ^{n - 1}\
]
[sum_{i = 0}^{n} i{n choose i} = n * 2 ^ {n - 1}\
证明:取二项式定理:(1 + n) ^ n = sum_{i = 0}^{n} {n choose i}\
两边求导: n(1 + n)^{n - 1} = sum_{i = 1}^{n} i{n choose i}n ^ {i - 1}, 取x = 1\
对于sum_{i = 0} ^{ n} i ^k {n choose i} 求k次导即可\
]
[sum_{i = 0}^{n} {i choose k} = {n + 1 choose k + 1} \
sum_{i = 0}^{k} {n + i choose i} = {n + k + 1 choose k}\
分别对Pascal公式的第一项和最后意向反复迭代展开即可.
]
-
范德蒙特卷积:
[sum_{k = 0}^{n} {m1 choose k}{m2 choose n - k} = {m1 + m2 choose n} ]考虑组合意义证明, ({m1 + m2 choose n})是(m1 + m2)向上向右的步子中向上的步数是(n)的方案数.
那么我们把式子展开, 在前(m1)步中, 我们走(k)步,那么在后面的(m2)步中,我们一定要走(n - k)步
所以有$$sum_{k = 0}^{n} {n choose k} ^ 2 = {2n choose n} $$
-
乱七八糟的式子:
[sum_{i = 1} {n choose i}{i choose m}(-1)^{i + m} = [n = m] ]