Swipe to navigate through the chapters of this book
Up to now, our work has been almost entirely qualitative. The concepts of a set, relation, function, recursion and induction are non-numerical, although they have important numerical applications as, for example, sets of integers or recursive definitions on the natural numbers. In this chapter, we turn to quantitative matters, and specifically to problems of counting. We will tackle two kinds of question.
First: Are there rules for determining the number of elements of a large set from the number of elements of smaller ones? Here we will learn how to use two very simple rules: addition (for unions of disjoint sets) and multiplication (for Cartesian products of arbitrary sets).
Second: Are there rules for calculating the number of possible selections of k items out of a set with n elements? Here we will see that the question is less straightforward, as there are several different kinds of selection, and they give us very different outcomes. We will untangle four basic modes of selection, give arithmetical formulae for them and practice their application. In the final section, we will turn to the problems of counting rearrangements and configured partitions of a set.
Please log in to get access to this content
Almost every text on discrete mathematics has a chapter on this material somewhere in the middle and, although terminology, notation and order of presentation differ from book to book the material covered is usually much the same. One clear beginner’s exposition is:
Haggarty R (2002) Discrete mathematics for computing. Pearson, Harlow, chapter 6
More detailed presentations include:
Johnsonbaugh R (2009) Discrete mathematics, 6th edn. Pearson, Upper Saddle River, chapter 6
Lipschutz S (1997) Discrete mathematics, Schaum’s outline series. McGraw Hill, New York, chapter 6
For more advanced texts dedicated to the subject, see, for example:
Andreescu T et al (2004) Counting strategies: a path to combinatorics for undergraduates. Springer/Birkhauser, New York/Boston
Herman J et al (1997) Counting and configurations: problems in combinatorics, arithmetic and geometry, CMS books in mathematics. Springer, New York
As mentioned by the Hatter, a good place to begin reading about multisets is the relevant article in Wikipedia.
- Counting Things: Combinatorics
- Springer London
- Sequence number
- Chapter number