2012 | OriginalPaper | Chapter

# 5. Counting Things: Combinatorics

Published in:
Sets, Logic and Maths for Computing

## Abstract

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.