ABSTRACT
Combinatorics is the art of counting. Usually, we are interested in counting objects that depend on a parameter (or two, or three...), for example the number of compositions of n with only 1s and 2s. (Here the parameter is n.) It is pretty straightforward to enumerate the number of such compositions for small values of n by exhibiting all possibilities, but as n increases, the number of compositions grows exponentially, and so we need to be smarter about counting. In this chapter we will give an overview of some basic techniques and ideas of combinatorics. We will illustrate important techniques such as the use of recurrence relations and generating functions with basic examples, which we will build upon and expand on in subsequent chapters.
