Pre-requisite

Binomial and Multinomial Theorem

(MISSISSIPPI problem): Number of ways to arrange the letters is \(\frac{11!}{1!4!4!2!}\) (M=1,I=4,S=4,P=2).

Note

  • There are items of \(r\) kinds, and within each kind they are indistinguishable. Say, we have \(k_i\) items of \(x_i\) kind, and so on. The number of ways of arranging a total of \(n\) such items (i.e. \(\sum_{i=1}^r k_i=n\))

    \[{n\choose k_1\cdots k_r}=\frac{n!}{k_1!\cdots k_r!}\]

  • This is also the number of ways a set of \(n\) indistinguishable items can be partitioned into \(r\) subsets. To see why, think about the process where we do the partitioning first (say, \(C\) is the number of ways we can partition) and then we rearrange each subset (\(k_i!\) ways for subset \(i\)) put the items in a sequence. The result is just a rearrangement of the entire sequence of \(n\) items.

Binomial theorem:

  • For evaluating the expression \((x+y)^n=(x+y)\cdots(x+y)\) (\(n\)-times), the process involves choosing either \(x\) or \(y\) from each of the \(n\)-terms.

  • We can choose \(x\) from 0 terms to \(n\) terms. Every time we choose \(x\) from \(k\) such terms, we’re left with no choice but to take \(y\) from the remaining \((n-k)\) terms.

  • The number of ways we can choose \(x\) from any \(k\) of such terms is \({n\choose k}\). This is how many times we have \(x^k y^{n-k}\).

  • Therefore

    \[(x+y)^n=\sum_{k=0}^n {n\choose k} x^k y^{n-k}\]

Tip

  • \(\sum_{k=0}^n {n\choose k}=2^n\) (setting \(x=1\) and \(y=1\)).

  • \(\sum_{k=0}^n (-1)^k {n\choose k}=0\) (setting \(x=-1\) and \(y=1\)).

  • (Vandermonde Identity) \({m+n\choose k}=\sum_{i=0}^k {m\choose i}{n\choose k-i}\).

  • \({n\choose k}={n-1\choose k-1}+{n-1\choose k}\).

Multinomial theorem:

  • For evaluating the expression \((x_1+x_2+\cdots+x_r)^n=(x_1+x_2+\cdots+x_r)\cdots(x_1+x_2+\cdots+x_r)\) (\(n\)-times), the process involves choosing \(x_1\) from \(k_1\) such terms, \(x_2\) from \(k_2\) such terms, and so on.

  • Regardless of how we choose, the \(\sum_{i=1}^r k_i=n\).

  • For each values of \(0\leq k_1,k_2,\cdots k_r\leq n\), this correspond to the to term \(x_1^{k_1}\cdots x_r^{k_r}\).

  • Therefore

    \[(x_1+x_2+\cdots+x_r)^n=\sum_{\sum_{i=1}^r k_i=n} {n\choose k_1\cdots k_r} x_1^{k_1}\cdots x_r^{k_r}\]

Binomial theorem for fractional and negative powers:

  • For evaluating expressions where the power is fractional or negative, we can use the following infinite series expansion

    \[(1+\delta)^\alpha=1+\alpha\delta+\frac{\alpha(\alpha-1)}{2!}\delta^2+\frac{\alpha(\alpha-1)(\alpha-2)}{3!}\delta^3+\cdots\]

  • This series converges only when \(|\delta|< 1\)

Geometry

Important

Lagrange polynomial

Note

  • Given two points in \(\mathbb{R}^2\), \((x_1,y_1)\) and \((x_2,y_2)\), the equation of a line passing through these two points is given by

    \[y-y_1=\frac{y_2-y_1}{x_2-x_1}(x-x_1)\]

    • We can represent this in the normal \(y=ax+b\) format as

      \[y=\frac{y_2-y_1}{x_2-x_1}x+\left(y_1-\frac{y_2-y_1}{x_2-x_1}x_1\right)\]

  • We can represent this in Lagrange’s polynomial form as the following:

    • We form Lagrange basis by taking

      • \(l_0(x)=\frac{x-x_1}{x_2-x_1}\)

      • \(l_1(x)=\frac{x-x_2}{x_1-x_2}\)

    • The final polynomial is formed by

      \[L(x)=y_1 l_0(x)+y_2 l_1(x)=y_1\frac{x-x_1}{x_2-x_1}+y_2\frac{x-x_2}{x_1-x_2}\]

  • TODO Extend to higher dimensions

Wavy Curve Method

Resources

Note