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=(\genfrac{}{}{0ex}{}{n}{r})$.

Note also that $\sum _{r=0}^k(\genfrac{}{}{0ex}{}{m}{r})\times (\genfrac{}{}{0ex}{}{n}{k-r})=(\genfrac{}{}{0ex}{}{m+n}{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+3x{y}^2+y^3$

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

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

Another observation from the above is known as Pascal's law. It states that $(\genfrac{}{}{0ex}{}{n}{r})=(\genfrac{}{}{0ex}{}{n-1}{r})+(\genfrac{}{}{0ex}{}{n-1}{r-1})$

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