Introduction

In the last two units we have exposed you to a variety of combinatorial techniques. In this unit we look at a few more ways of counting arrangements of objects when order matters, and when it doesn’t.

In this, we focus on the ways in which a natural number can be written as a sum of natural numbers. In the process you will be introduced to a useful ‘recurrence relation’.

We link this, with the different ways in which n objects can be distributed among m containers. As you will see, there are four broad possible kinds of distributions. In each case, we consider ways of counting all the distributions. In the process you will also be introduced to Stirling numbers.

Objectives

After going through this unit, you should be able to:

• define an integer partition, and count the number of partitions of an integer;
• count the number of ways of distributing distinguishable and indistinguishable objects, respectively, into distinguishable containers;
• count the number of ways of distributing distinguishable and indistinguishable objects, respectively, into indistinguishable containers.