Lesson 38 — Combinations and Newton's Binomial

Combinations and binomial

Simple combination

$C_n^p = \binom{n}{p} = \frac{n!}{p!(n-p)!}$

Read: "$n$ choose $p$". Holds for $0 \leq p \leq n$.

Difference from arrangement

$\binom{n}{p}$ does NOT order. Each subset of $p$ elements is counted once. Relation: $A_n^p = p! \binom{n}{p}$ — arrangement orders after selecting.

Properties

Pascal's triangle

                    1
                  1   1
                1   2   1
              1   3   3   1
            1   4   6   4   1
          1   5  10  10   5   1
        1   6  15  20  15   6   1

Row $n$ (starting at 0) has the coefficients $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$.

Binomial theorem (Newton)

$(a + b)^n = \sum_{p=0}^n \binom{n}{p} a^{n-p} b^p$

Examples:

• $(a + b)^2 = a^2 + 2ab + b^2$
• $(a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$
• $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$

General term

$T_{p+1} = \binom{n}{p} a^{n-p} b^p$ — the $(p+1)$-th term of $(a+b)^n$.

Multinomial (generalization)

$(x_1 + x_2 + \cdots + x_k)^n = \sum \binom{n}{n_1, n_2, \ldots, n_k} x_1^{n_1} \cdots x_k^{n_k}$

with $\binom{n}{n_1, \ldots, n_k} = \frac{n!}{n_1! \cdots n_k!}$ and $\sum n_i = n$.