Sách toán/Kết hợp theo thứ tự

Combinations

A combination is essentially a subset. It is like a permutation, except with no regard to order. Suppose we have a set of $n$ elements and take $r$ elements. The number of possible combinations is ${\frac {_{n}P_{r}}{r!}}={\frac {n!}{r!\times (n-r)!}}=_{n}C_{r}=\displaystyle {n \choose r}$.

Note also that $\sum _{r=0}^{k}\displaystyle {m \choose r}\times \displaystyle {n \choose k-r}=\displaystyle {m+n \choose k}$

Combinations are found in binomial expansion. Consider the following binomial expansions:

$(x+y)^{1}=x+y$

$(x+y)^{2}=x^{2}+2xy+y^{2}$

$(x+y)^{3}=x^{3}+3x^{2}y+3xy^{2}+y^{3}$

$(x+y)^{4}=x^{4}+4x^{3}y+6x^{2}y^{1}+4xy^{2}+y^{3}$

As you may have noticed from the above, for any positive integer $n$, $(x+y)^{n}=\sum _{i=0}^{n}[\displaystyle {n \choose r}\times x^{n-r}\times y^{r}]$

Another observation from the above is known as Pascal's law. It states that $\displaystyle {n \choose r}=\displaystyle {n-1 \choose r}+\displaystyle {n-1 \choose r-1}$

This allows us to construct Pascal's triangle, which is useful for determining combinations: