Combinations

Overview

A $k$ -combination of $n$ objects is an unordered "choice" of $k$ objects from the collection of $n$ objects. Alternatively viewed, it is a set of $k$ objects - ordering within a set does not matter. Combinations are derived by considering the number of $k$ -combinatorics/permutations of $n$ objects and discarding order, i.e. dividing by $k!$ .

(\binom{n}{k}) = \frac{(n)_{k}}{k!} = \frac{n!}{k! (n - k)!}, where k < n

Pascal's Triangle

Pascal's triangle is a visual representation of binomial coefficients. The top of the triangle looks as follows:

Each term is generated by adding the two terms above it, formalized via recurrence $$\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}$$

Stars and Bars

The stars and bars chart refers to a graphical depiction of distributing $n$ objects (represented as $*$ ) into $k$ different buckets (delineated via $|$ ). An example chart looks like so:

* * | * * * | * | | *

Notice there are $k - 1$ bars interspersed amongst the $n$ stars. Thus there exist

(\binom{n + k - 1}{k - 1}) possibilities .

Binomial Theorem

Let $n \in Z^{+}$ and $x, y \in R$ where $R$ is some commutative ring. Then

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} .

In a commutative rng, the following identity, which forgoes terms $x^{0}$ and $y^{0}$ , can be used instead:

(x + y)^{n} = x^{n} + y^{n} + \sum_{k = 1}^{n - 1} (\binom{n}{k}) x^{n - k} y^{k} .

Freshman Exponentiation

Let $p$ be a prime. Then the following identity holds in ring $Z_{p}$ :

(x + y)^{p} = x^{p} + y^{p} .

Identities

Hockey stick Identity

Let $n, k \in N$ such that $n \geq k$ . The hockey stick identity states that

\sum_{i = k}^{n} (\binom{i}{k}) = (\binom{n + 1}{k + 1})

Vandermonde's Identity

Let $m, n, k \in N$ . Then Vandermonde's identity states that

(\binom{m + n}{k}) = \sum_{j = 0}^{k} (\binom{m}{j}) (\binom{n}{k - j})

Common Examples

Bit Strings

A bit string can be used to represent subsets of some finite set. A 1 value usually corresponds to inclusion in a subset, whereas a 0 value corresponds to exclusion. Thus, given set e.g. $A = {1, 2, 3, 4}$ , $0110_{2}$ would correspond to subset ${2, 3}$ .

Bit strings also make it clear that the number of subsets with even cardinality must be equal to the number of subsets with odd cardinality. Hence,

(\binom{n}{0}) - (\binom{n}{1}) + \dots + (- 1)^{n} (\binom{n}{n}) = 0

Lattice Paths

A lattice path is one of the shorted possible paths connecting two points on a lattice, moving only horizontally and vertically. By representing each horizontal move by 1 and each vertical move by 1, we see every lattice path has a corresponding bit string.

In this example, the total number of lattice paths from point $(0, 0)$ to $(3, 2)$ is therefore

(\binom{5}{2}) = (\binom{5}{3}) .