Combinatorics (or more precisely enumerative combinatorics) is the branch of mathematics that studies counting. One way to try to integrate this topic into the mathematical infrastructure of logic and set theory we have discussed so far is to define the number of elements in a finite set $S$ to be $n$ if and only if there exists a bijection between $S$ and $\bbI _ n$.
Definition . Let $S$ be a set and $n\in\bbN$. We say that $S$ has cardinality $n$ if and only if there exists a bijection $f\colon \Set{ 1,2,\ldots,n }\to S$. In this case, we write $\left|S\right|$ for the cardinality of $S$.
Note that $\bbI _ n=\Set{ 1,2,\ldots,n }$ is the empty set when $n=0$.
Example . With this definition, we can prove that $\left|\Set{ š }\right|=1$.
Proof.
Define $f\colon \Set{ 1 } \to \Set{ š }$ by $f(1)=š$.
Let $x,y \in \Set{ 1 }$ and assume $f(x)=f(y)$. Then $x=1$ and $y=1$ by the definition of finite set notation. Since $1=y$ by symmetry, we see that $x=y$ by substitution.
Thus $f$ is injective.
To see that $f$ is surjective, let $b\in\Set{š}$. Then $b=š$ by the definition of finite set notation. Hence,
$$ \begin{align} f(1) &=š \\ &= b \end{align} $$
by substitution and $1 \in \Set{ 1 }$ by the definition of finite set notation.
Thus, $f$ is surjective.
Since $f$ is both injective and surjective, it is bijective. So
$\left|\Set{ š }\right|=1$ as desired.
$\square$
This definition leaves a bit to be desired, however. One of the first things that any preschooler learns about mathematics is the difference between none, one, and several. Fortunately, there is another kind of mathematical proof that is accepted in journals and by mathematicians as a valid proof that is better suited to this task.
We begin by defining the language of a different kind of proof system that is distinct from the formal axiom system kinds of proofs that we have discussed so far. This form of proof will be based on counting, and so we need something to count.
Definition . A combinatorial collection is anything that can be counted. Each combinatorial collection has a property called its count (or cardinality or size) which represents the number of entities comprising the collection. Two combinatorial collections are said to be equivalent if they have the same count. If $A$ is a combinatorial collection then we write $\left|A\right|$ for the count of $A$.
Anything we can count is an example of a combinatorial collection. For example, we can count the number of elements in a finite set, or the number of ways we can accomplish some task, the number of possible outcomes from some activity, or the number of choices we have in making some decision. In each case the count can be represented by a symbolic expression.
Definition . A combinatorial expression is an expression that represents the cardinality of a combinatorial collection.
Naturally, we can define an expression for any combinatorial collection we might have. Here are some common combinatorial expressions that we will use in what follows.
Combinatorial Expressions
| Expression | Combinatorial definition (what it counts) |
|---|---|
| $0,1,2,3,\ldots$ | Any collection of one, two, three, $\ldots$ things respectively. |
| $n$ | A collection of $n$ things where $n$ is one of $0, 1, 2, 3, \ldots$ . |
| $a+b$ | A collection that can be partitioned into two disjoint collections having size $a$ and $b$ respectively. |
| $a _ 1+a _ 2+\cdots+a _ n$ | A collection that can be partitioned into $n$ disjoint collections of size $a _ 1, a _ 2, \ldots , a _ n$ respectively. |
| $a\cdot b$ | The number of ways of choosing two things in order if there are $a$ ways to choose the first and $b$ ways to choose the second. |
| $a _ 1\cdot a _ 2\cdot a _ 3\cdots a _ n$ | The number of ways of choosing $n$ things in order if there are $a _ 1$ ways |
| $n!$ | The number of ways to permute (rearrange) $n$ distinct things in some order. |
| $n^k$ | The number of ways to choose $k$ things from $n$ things where repetition is allowed and order matters. |
| $(n) _ k$ | The number of ways to choose $k$ things from $n$ things where repetition is not allowed and order matters. |
| $\binom{n}{k}$ | The number ways to choose $k$ things from $n$ things where repetition is not allowed and order doesnāt matter. |
| $\multichoose{n}{k}$ | The number of ways of choosing $k$ things from $n$ things where repetition is allowed and order doesnāt matter. |
| $F _ n$ | The number of ways to partition an ordered list of $n$ items into singletons and pairs (of consecutive items). |
Remarks
Some of the combinatorial expressions given in the previous table have common names and alternate notation in mathematics.
Finally, we need some statements that we can prove with our new kind of proof. The simplest such statements are called combinatorial identities.
Definition . A combinatorial identity is a expression of the form $$A=B$$ where $A$ and $B$ are combinatorial expressions.
The fundamental assumption on which the validity of all counting relies, is that no matter how you count the same collection, if you do it correctly, you will obtain the same result. This simple idea is the foundation for a kind of mathematical proof called a combinatorial argument.
Definition . A combinatorial proof (or combinatorial argument) is proof of a combinatorial identity obtained by counting the same thing (or two equivalent things) in two different ways.
It is truly amazing the extent to which we can build up much of algebra from a combinatorial perspective, and give combinatorial proofs of many algebraic identities. Often, combinatorial interpretations are considered to be easier and more intuitive explanations of a given fact than algebraic or inductive proofs.
Example . The fact that $$5\cdot (3+2)=3\cdot 5+2\cdot 5$$ can be verified by invoking the distributive law and commutative law of multiplication, but that doesnāt give us a sense of what the identity says about counting.
Using a combinatorial argument, however, we can say that the left hand side counts the total number of squares in a collection consisting of $5$ collections, each of which is comprised of two disjoint collections having $3$ things and $2$ things respectively (as illustrated in the left figure below), and the right hand side counts the same collection of squares partitioned into two collections, one consisting of $3$ collections of $5$ squares (the blue ones) and another consisting of $2$ collections of $5$ squares (the orange ones, as illustrated in the right figure below). Since we are counting the same collection of little squares in two different ways, this is a combinatorial proof of the identity above.
Proofs similar to the one in the above example can be generalized to give combinatorial proofs of the algebraic properties of numbers given in the axioms for the real numbers.
In this context, rather than starting with algebraic axioms such as the distributive law, we can start with tactile meanings of numbers, addition, multiplication, division, and so on. These arguments can then be pasted together to deduce all the algebraic axioms we usually work with.
While it is possible to give purely combinatorial proofs of many combinatorial identities, it is also commonplace to use both combinatorial and axiomatic algebraic arguments in the same mathematical proof. Thus, we can use combinatorial arguments even as just one part of a larger proof involving many techniques.
Just as in algebra, it is often convenient to be able to discuss the difference or quotient of two combinatorial expressions. The problem with doing that from a combinatorial perspective is that the difference or quotient of two combinatorial expressions is not always a combinatorial expression. So we have to take some care when defining them to take that into account.
Definition . Let $k$, $m$, and $n$ be combinatorial expressions.
In general, whenever we use such an expression we are assuming it is defined for the expression to make sense. Thinking of these expressions as natural numbers for a moment, we can say that $n-k$ to be defined it is sufficient for $k$ to be less than or equal to $n$. But for $n/k$ to be defined $k$ must be a divisor of $n$. In order to avoid this problem we avoid using division and subtraction wherever possible in combinatorial proofs, except when we need to refer to arbitrary sequences like $1, 2, \ldots, n-2, n-1, n$.
The following combinatorial identities can all be proved using a combinatorial proof using only the definitions given in this chapter. If we were defining combinatorics in an algebraic setting (as you might find in a course on discrete mathematics or combinatorics), these identities are often taken to be the definition of the symbols themselves. From the perspective of combinatorial proofs, these identities are all theorems that we prove by counting the same collection in two different ways.
In the following identities, all variables are combinatorial expressions. Use a purely combinatorial proof to prove the theorems in this section.
zero power $n^0=1$
alternate definition of multiplication $k\cdot n = \underbrace{n+n+\cdots+n} _ {k \text{ summands}} = \underbrace{k+k+\cdots+k} _ {n \text{ summands}} = n\cdot k$
alternate definition of factorial $n! = n\cdot (n-1)\cdots 3\cdot 2\cdot 1$
alternate definition of power $n^k = \underbrace{n\cdot n \cdots n} _ {k \text{ factors}}$
alternate definition of permutation $(n) _ k=n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)$
alternate definition of permutation $(n) _ k\cdot (n-k)!=n!$
alternate definition of choose $\binom{n}{k}\cdot k! \cdot (n-k)! = n!$
alternate definition of multichoose $\multichoose{n}{k} = \binom{n-1+k}{k}$
Some of the usual properties of these expressions that can be derived from these by induction and/or algebra often have interesting combinatorial proofs as well.
our favorite theorem redux $1+1=2$
counting over computing $\binom{6}{2}\cdot\binom{4}{3}=\binom{6}{3}\cdot\binom{3}{2}$
more counting over computing $\multichoose{8}{3}=\multichoose{4}{7}$
terrible twos $n^2=(n) _ 2+n$
binomial complement $\binom{m+n}{m}=\binom{m+n}{n}$
multichoose complement $\multichoose{n+1}{k}=\multichoose{k+1}{n}$
choose vs permute $(n) _ k=\binom{n}{k}\cdot k!$
ordered choice $\binom{n}{k}\cdot\binom{n-k}{j}=\binom{n}{j}\cdot\binom{n-j}{k}=\binom{n}{k+j}\cdot\binom{k+j}{k}$
good things come in pairs $\binom{2n+2}{k} =\binom{2n}{k}+2\cdot\binom{2n}{k-1}+\binom{2n}{k-2}$
good things come in pairs $F _ {n+3}+F _ n=2\cdot F _ {n+2}$
hockey stick redux $\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+\cdots+\binom{n-1}{k}+\binom{n}{k}=\binom{n+1}{k+1}$
multichoose hockey stick $\multichoose{n}{0}+\multichoose{n}{1}+\multichoose{n}{2}+\cdots+\multichoose{n}{k-1}+\multichoose{n}{k}=\multichoose{n+1}{k}$
another multichoose hockey stick $\multichoose{1}{k}+\multichoose{2}{k}+\cdots+\multichoose{n-1}{k}+\multichoose{n}{k}=\multichoose{n}{k+1}$
another ordered choice $(k+1)\cdot \binom{n+1}{k+1} =(n+1)\cdot \binom{n}{k}$
factorial recursion $(n+1)!=(n+1)\cdot n!$
power recursion $n^{k+1}=n\cdot n^k$
permutations recursion $(n+1) _ {k+1}=(n+1)\cdot(n) _ k$
combination recursion $\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}$
Fibonacci recursion $F _ n+F _ {n+1}=F _ {n+2}$
multichoose recursion $\multichoose{n+1}{k}=\multichoose{n}{k}+\multichoose{k}{n}$
another permutations recursion $(n+1) _ {k+1}=(n) _ {k+1}+(k+1)\cdot(n) _ k$
another Gaussā formula $1+2+3+\cdots+n = \binom{n+1}{2}$
Fibonacci sum $1+F _ 1+F _ 2+\cdots+F _ n=F _ {n+2}$
sum of squares $3\cdot(1^2+2^2+3^2+\cdots+(n-1)^2+n^2) = (2n+1)\cdot\binom{n+1}{2}$
sum of cubes $ 1^3+2^3+3^3+\cdots+n^3= \binom{n+1}{2}^2 $
Vandermondeās identity $\binom{m}{0}\cdot\binom{n}{k}+\binom{m}{1}\cdot\binom{n}{k-1}+\ldots+\binom{m}{k-1}\cdot\binom{n}{1}+\binom{m}{k}\cdot\binom{n}{0}=\binom{m+n}{k} $
multichoose Vandermonde $\multichoose{m}{0}\cdot\multichoose{n}{k}+\multichoose{m}{1}\cdot\multichoose{n}{k-1}+\ldots+\multichoose{m}{k-1}\cdot\multichoose{n}{1}+\multichoose{m}{0}\cdot\multichoose{n}{k}=\multichoose{m+n}{k} $
binomial theorem $ \binom{n}{0}\cdot x^n\cdot y^0+\binom{n}{1}\cdot x^{n-1}\cdot y^1+\binom{n}{2}\cdot x^{n-2}\cdot y^2+\cdots+ \binom{n}{n}\cdot x^0\cdot y^n=(x+y)^n$
sum of row of Pascalās triangle $\binom{n}{0}+\binom{n}{1}+\cdots + \binom{n}{n}=2^n$
Fibonacci as binomials $\binom{2n}{0}+\binom{2n-1}{1}+\binom{2n-2}{2}+\cdots + \binom{n}{n}=F _ {2n}$
Fibonacci and binomials $\binom{n}{0}\cdot F _ 0+\binom{n}{1}\cdot F _ 1+\binom{n}{2}\cdot F _ 2+\cdots + \binom{n}{n}\cdot F _ n=F _ {2n}$
sum of row of Pascalās triangle $\binom{n}{0}+\binom{n}{1}+\cdots + \binom{n}{n}=2^n$
the next row down $\binom{2n+1}{1}+\binom{2n+1}{3}+\cdots + \binom{2n+1}{2n+1}=4^n$
linear sum of row of Pascalās triangle $0\cdot \binom{n}{0}+1\cdot\binom{n}{1}+2\cdot \binom{n}{2}+3\cdot \binom{n}{3}+\cdots +n\cdot \binom{n}{n}=n\cdot 2^{n-1}$
another linear sum of a row $0^2\cdot \binom{n}{0}+1^2\cdot\binom{n}{1}+2^2\cdot \binom{n}{2}+3^2\cdot \binom{n}{3}+\cdots +n^2\cdot \binom{n}{n}= 2^{n+1}\cdot\binom{n+1}{2}$
sum of squares of row of Pascalās triangle $\binom{n}{0}^2+\binom{n}{1}^2+\ldots+\binom{n}{n-1}^2+\binom{n}{n}^2=\binom{2n}{n}$
linear sum of squares of row of Pascalās triangle $$0\cdot \binom{n}{0}^2+1\cdot\binom{n}{1}^2+2\cdot \binom{n}{2}^2+3\cdot \binom{n}{3}^2+\cdots +n\cdot \binom{n}{n}^2=n\cdot \binom{2n-1}{n-1}$$
We can apply the method of combinatorial proof to solve counting problems by defining new combinatorial expressions, and then proving identities involving them by counting in two ways.
Frog hopping a staircase Froggy Frog is at the bottom of a staircase with $n$ stairs and wants to get to the top. He can only jump 1 or 2 stairs at a time and never backtracks. Let $W _ n$ be the number of ways Froggy can jump from the bottom of the stairs to the top.
