Elementary Combinatorics
摘要
In this chapter, we introduce some basic tools of combinatorial reasoning and ingenuity that help deal with intricacies of varied types of enumeration problems. We first introduce two fundamental “rules of counting”. The fundamental inclusion-exclusion principle is about comparing sizes of the union and intersection of more than two nonempty sets. We also discuss some important identities involving multinomial coefficients. Combinatorics also offer tools to study existence of an optimal arrangement that satisfies some specified constraints. In large number of cases, we have an unknown sequence \(\big (a_n\big )\) that satisfies a recurrence relation, and we need to find an explicit formula for \(a_n\) , subject to given initial values. In the last section, we discuss some important methods of solving recurrence relations.