# enumerative combinatorics

Enumerative combinatorics deals with the question: if we know that a set $S$ is finite, how can we determine the exact number of elements that $S$ contains?

Basic principles and techniques of enumerative combinatorics include:

• the involution principle;

• the use of generating functions.

The principles listed above are disarmingly simple and seemingly obvious. Nonetheless, when used properly they are powerful tools for producing bijective proofs of combinatorial identities    . On the other hand, while generating functions can frequently be used to give quick proofs of identities, it is sometimes difficult to extract combinatorial proofs from such proofs.

The most fundamental principle of enumerative combinatorics and the basis of all counting is the addition principle. It says that if $S$ is a finite set  , then

 $|S|=\sum_{x\in S}1.$

More generally, if $S=A\sqcup B$, then

 $|S|=\sum_{x\in A\sqcup B}1=\sum_{x\in A}1+\sum_{x\in B}1=|A|+|B|.$

By induction  on $n$, we also get

 $\biggl{|}\bigsqcup_{i\in[n]}S_{i}\biggr{|}=\sum_{i\in[n]}|S_{i}|.$

As an application of the addition principle, we prove the multiplication principle.

###### Proposition 1.

Multiplication principle. If $S$ and $T$ are finite sets, then

 $|S\times T|=|S|\cdot|T|.$
###### Proof.

 $|S\times T|=\sum_{(x,y)\in S\times T}1.$

But we can write $S\times T$ as the disjoint union  $S\times T=\bigsqcup_{y\in T}S\times\{y\}.$

The projection map $S\times\{y\}\to S$ is a bijection, so $|S\times\{y\}|=|S|$. Hence it follows that

 $\displaystyle|S\times T|$ $\displaystyle=\sum_{y\in T}|S\times\{y\}|$ $\displaystyle=\sum_{y\in T}|S|$ $\displaystyle=|S|\cdot\sum_{y\in T}1$ $\displaystyle=|S|\cdot|T|,$

The involution principle says that if $\varphi\colon S\to S$ is an involution, then for any $X\subset S$, $|X|=|\varphi(X)|$. The following example illustrates the involution principle.

###### Proposition 2.

Enumerating elements of the powerset. Let $[n]=\{1,2,\dots,n\}$ and let $2^{[n]}$ be the powerset of $[n]$. Then the cardinality of $2^{[n]}$ is $2^{n}$.

###### Proof.

In other words, $\varphi(S)$ is the symmetric difference   of $S$ and $\{n\}$ — if $n$ is an element of $S$, we remove it, and if $n$ is not an element of $S$, we insert it. The function $\varphi$ is an involution, hence a bijection. Now notice that $2^{[n-1]}\subset 2^{[n]}$ and $\varphi(2^{[n-1]})=2^{[n]}\setminus 2^{[n-1]}$. In other words,

 $2^{[n]}=2^{[n-1]}\sqcup\varphi(2^{[n-1]}).$

Since $\varphi$ is a bijection, this implies that

 $|2^{[n]}|=2\cdot|2^{[n-1]}|.$

By induction on $n$ we obtain

 $|2^{[n]}|=2^{n}\cdot|2^{}|.$

Now $=\emptyset$, so $2^{}=\{\emptyset\}$. Thus $|2^{}|=1$, implying that

 $|2^{[n]}|=2^{n},$

which is what we wanted to show. ∎

As we have seen above, it is possible to use the addition principle to count the number of elements in the disjoint union of finite sets. But what if we want to count the number of elements in a non-disjoint union of finite sets? The inclusion-exclusion principle gives us a way to do this. A common way of stating the inclusion-exclusion principle is as the following proposition  .

###### Proposition 3.

Inclusion-exclusion principle. Let $S_{1},\dots,S_{n}$ be finite sets. Then

 $\biggl{|}\bigcup_{i\in[n]}S_{i}\biggr{|}=\sum_{T\in 2^{[n]}}(-1)^{|T|}\biggl{|% }\bigcap_{i\in T}S_{i}\biggr{|}.$
###### Proposition 4.

Let $S$ and $T$ be finite sets. Then

 $|S|+|T|=|S\cup T|+|S\cap T|.$

###### Proof.

 $\displaystyle|S|+|T|$ $\displaystyle=|(S\setminus T)\sqcup(S\cap T)|+|(T\setminus S)\sqcup(S\cap T)|$ $\displaystyle=|S\setminus T|+|S\cap T|+|T\setminus S|+|S\cap T|.$
Now observe that $S\cup T=(S\setminus T)\sqcup(S\cap T)\sqcup(T\setminus S)$. So by a second application of the addition principle,
 $|S\cup T|+|S\cap T|=|S\setminus T|+|S\cap T|+|T\setminus S|+|S\cap T|.$
Hence $|S|+|T|=|S\cup T|+|S\cap T|$. ∎