Skip to content

3.12 Binomial Coefficients

  1. Find the number of ways to arrange \(n\) persons at a round table. Two ways are identical if each person has the same left neighbor in both ways.

    image​

    We have bijections between seeds and people \(|\{\text{such bijections\}}|=n!\)​

    Also we have \(f:\{\text{Bijections}\}\to\{\text{similar configrations}\}\)​

    1. Put the marked point to the left of position 1. In the corresponding bijection person 1 is the first one
    2. Put the marked point to the left of position 2, then the corresponding bijection person 2 is the first one
    3. Put the marked point to the left of position 3, then the corresponding bijection person 3 is the first one

    The preimage of every configation has the same number of elements \(n\)​

    Thus \(\left|\lbrace\text{configration}\rbrace\right|=\frac{n!}{n}=\left(n-1\right)!\)​

  2. Why do the binomial coefficients correspond to the coefficients of expansion of \((x + y)^{n}\)?image​

    To formal prove, we use induction

    Suppose \((x+y)^{n-1}=\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-1-k}y^{k}\), then we know \((x+y)^{n}=(x+y)^{n-1}(x+y)\)​

    Then \(=\left(\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-1-k}y^{k}\right)\left(x+y\right)=\sum_{k=0} ^{n-1}\binom{n-1}{k}x^{n-k}y^{k}+\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-k-1}y^{k+1}\)​

    \(=\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-k}y^{k}+\sum_{k=-1}^{n}\binom{n-1}{k-1}x^{n-k} y^{k}=\sum_{k=0}^{n}\left(\binom{n-1}{k-1}+\binom{n-1}{k}\right)x^{n-k}y^{k}=\sum _{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}\)​

  3. Prove that the number of up-right paths on the rectangular grid of size \(a \times b\) equals \(\binom{a+b}{a}\).

    We use the paths that are formed from the segment \(\rightarrow,\uparrow\)​

    Induction on \(a+b\)​

    image​

  4. Prove the following identities:

    (a) \(\binom{n}{k} = \binom{n}{n-k}\);

    image​

    (b) \(\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0\);

    image​

    (c) \(\binom{n}{m} \binom{m}{r} = \binom{n}{r} \binom{n-r}{m-r}\);

    image​

    (d) \(\binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^2\);

    image​

    (e) \(\binom{k+l}{k}= \sum_{i=0}^{k}\binom{l+i-1}{i}\)

    \(\text{| paths to }(k, l) | = \binom{k+l}{k}\)

    \(\binom{l-1+i}{i} = \text{| paths to }(i, l-1) |\)

    Let’s \((i, l-1)\) be the last point that the path crosses in row \(l-1\).
    That is, once the path reaches \((i, l-1)\), then it must go up to row \(l\), then go left to \((k, l)\).

    This is uniquely determined.

‍