DoorKickers的博客

博客

SBzlt's Math note

2020-03-25 22:12:05 By DoorKickers

Binomial Coefficients

Let (rk) to denote that choose k elements from a set containing r terms without considering order.

With combinational interpretation. (rk)=n(n1)(nk+1)k(k1)1=n!(nk)! k!

There are some identities that hold when r is a positive real number and k is non-negative integer.

The first is symmetry identity {r \choose k} = {r \choose r - k} Next, we got *absorption identity* {r \choose k} = \frac{r}{k}{r - 1 \choose k - 1} If we multiply both sides by k, then we have k{r \choose k} = r{r - 1 \choose k - 1} There is a companion identity of the above one. \begin{align}(r - k){r \choose k} &= (r - k) {r \choose r - k} \\&=r{r - 1 \choose r - k - 1} \\&=r{r - 1 \choose k}\end{align} One of the other important formula is called *addition formula* {r \choose k} = {r - 1\choose k - 1} + {r - 1 \choose k} And it's easy to prove.

Beside these, we also have two identities of summation form. \sum_{k = -r}^{n}{{r + k \choose k}} = {r + n + 1 \choose n} and \sum_{k = 0}^{n}{k \choose m} = {n + 1 \choose m + 1} Notice that the summation 0 + 1 + 2 + \dots + n is a special case of former identity when m = 1 , and its result is equal to \frac{n(n+ 1)}{2} which is {n + 1 \choose 2} manipulated by that formula.

Here is one of the most important identity in binomial coefficients. (x + y)^r =\sum_{k}{{r \choose k}x^ky^{r - k}} And when x = y = 1 and r = n is nonnegative integer, we got {n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose n} = 2^n If we replace x by -1, then {n \choose 0} - {n \choose 1} + {n \choose 2} - {n \choose 3} + \dots + (-1)^n{n \choose n} = 0

Assumed that y = 1 and writing z instead of x to emphasize that an arbitrary complex number can be involved here. (1 + z)^r = \sum_{k}{{r \choose k}z^k}

评论

[+5]
Orz zlt!!!
  • 2020-03-28 14:05:13
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。