ABSTRACT

This chapter introduces new and powerful counting tools: generating functions, which have a marvelous way of organizing combinatorial information. It also introduces combinatorial proofs as both a clever proof technique and a way to gain deeper insight into some combinatorial identities. The chapter presents an example on the alternating sum, which naturally lends itself to an argument involving the Principle of Inclusion–Exclusion. The chapter represents the Binomial Theorem using alternate notation that is more conducive to generalizing. There is a generalization of the Binomial Theorem that involves multinomial coefficients. Just as the Binomial Theorem was used to expand a power of a sum of two terms, the Multinomial Theorem can be used to expand a power of a sum of two or more terms. The chapter utilizes counting tehniques to prove combinatorial identities. Combinatorial identities can be useful tools for solving counting problems.