Definition of Combination in Combinatorics and Proof of the Binomial Theorem
Definition
- A subset of a finite set is called a combination.
- The number of subsets with cardinality $k$ of a set with cardinality $n$ is denoted by $\binom{n}{k}$ or $_{n}C_{k}$, and is called the binomial coefficient. $$ \binom{n}{k} = {}_{n}C_{k} = \frac{ n! }{ k! (n-k)! } $$
Simple Definition
The number of ways to choose $k$ items from $n$ distinct items without regard to order is called a combination, and it is denoted by $\binom{n}{k}$ or $_{n}C_{k}$.
$$ \binom{n}{k} = {}_{n}C_{k} = \frac{ n! }{ k! (n-k)! } = \frac{ _{n}P_{k} }{ k! } $$
Here, $_{n}P_{k}$ is a permutation.
Theorem
Binomial Theorem
$$ (x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k} $$
Pascal’s Identity
$$ \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1} $$
Binomial Coefficient Sum Formula
$$ 2^{n} = \sum_{k=0}^{n} \binom{n}{k} $$
Binomial Coefficient Subtraction Formula
$$ \binom{n}{k} \left( {\frac{ n }{ k }} \right)^{-1} = \binom{n-1}{k-1} $$
Binomial Coefficient Sum of Squares Formula
$$ \binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^{2} $$
Explanation
Note that, except for the binomial theorem, the names of the formulas above are not names actually in use; they were assigned arbitrarily just for convenience.
The binomial theorem is the most famous and important theorem in combinatorics, and it is widely applied regardless of field.
Proof
Proofs other than that of the binomial theorem are dealt with separately in the article for each formula.
When expanding $(x+y)^{n}$, the coefficient of $x^{k} y^{n-k}$ is the same as the number of ways of choosing $x$ $n$ times and $y$ $n-r$ times among the factors $(x+y)$ of $$ (x+y)^{n} = (x+y)(x+y)(x+y) \cdots (x+y) $$ Therefore, since the number of combinations $_n C _r$ becomes the coefficient of $x^{k} y^{n-k}$, the following holds. $$ (x+y)^{n} = \sum_{k=0}^{n} {_n C _k} x^{k} y^{n-k} $$
■