Counting with Sets in Discrete Mathematics

---

---

Sets work on discrete elements and hence they play an important role in counting theory and combinatorics in discrete mathematics. By using sets, we can apply important principles, such as the additive and multiplicative principles, with greater clarity.

In this chapter, we will explain how counting works with sets. We will be focusing on important concepts like union, intersection, and Cartesian products. In addition, we will present several examples to demonstrate these principles in action.

The Additive Principle with Sets

The basic of set based counting also relies on additive principle. This principle tells us how to count when two events or sets are disjoint. It means there is no overlap between them. The principle states that if two sets, A and B, they are disjoint.

The total number of elements in the union of A and B is simply the sum of the elements in A and B −

$$\mathrm{|A \:\cup\: B| \:=\: |A| \:+\: |B|}$$

The key here is that there must be no overlap between the sets. If the sets overlap, we need to subtract the overlapping elements to avoid counting them twice.

Example of Shirts and Pants

Let us see one example for a better understanding. Imagine we have 9 shirts and 5 pairs of pants. If we want to know how many different outfits we can make by wearing one shirt and one pair of pants in multiplicative principle. But consider this is a special day and we will only wear a shirt or only wear pants. In this case, we add the number of shirts and pants because we cannot wear both −

$$\mathrm{\text{Total choices } =\: 9 \:+\: 5 \:=\: 14}$$

Here, since we are either choosing from the shirt set or the pants set but not both

Extending to More Sets

We can also increase the number of sets for this additive principle. More than two sets can be used but the sets remain disjoint. For example, if we had a third set, maybe 7 hats, we would simply add those to the total −

$$\mathrm{\text{Total choices } =\: 9 \:+\: 5 \:+\: 7}$$

In this case, each set is disjoint. So no overlap exists between them, and the additive principle applies directly.

The Multiplicative Principle with Sets

Like additive, multiplicative principles are also useful with sets. It tells us how to count when two events or sets are combined in a way that each outcome from one set can be paired with an outcome from another set.

It shows that if there are two sets, A and B, the total number of combinations of one element from A and one from B is the product of the number of elements in A and the number of elements in B −

$$\mathrm{|A \:\times\: B| \:=\: |A| \:\cdot\: |B|}$$

Here the idea of the Cartesian product is used.

Example of Shirts and Pants (Again)

Let us see the same example again. If we want to wear both a shirt and a pair of pants, we multiply the number of shirts by the number of pants −

$$\mathrm{\text{Total outfits } =\:9 \:\times\: 5 \:=\: 45}$$

Here, each shirt can be paired with any pair of pants, so the multiplicative principle applies.

Cartesian Product: Pairing Sets

The Cartesian product of two sets is very much useful and it is a set of ordered pairs. Where the first element in each pair comes from the first set, and the second element comes from the second set.

For two sets A and B, their Cartesian product is written as −

$$\mathrm{A \:\times\: B \:= \{ (x, y) \:\mid\: x \:\in\: A,\: y \:\in \:B \}}$$

This means for each element in A, you pair it with every element in B.

Example of Cartesian Product

Let us say we have two sets −

• A = {1, 2}
• B = {3, 4, 5}

The Cartesian product A × B is the set of all ordered pairs where the first element comes from A and the second comes from B −

$$\mathrm{A \:\times\: B \:=\: \{ (1, 3),\: (1, 4),\: (1, 5),\: (2, 3),\: (2, 4),\: (2, 5) \}}$$

The number of elements in the Cartesian product is simply the product of the number of elements in each set −

$$\mathrm{|A \:\times\: B| \:=\: |A| \:\times\: |B| \:=\: 2 \:\times\: 3 \:=\: 6}$$

This example shows how the multiplicative principle works with sets.

Combining Additive and Multiplicative Principles

In several cases we will need to combine both the additive and multiplicative principles in a single problem. This happens when we are counting multiple stages of decision-making. When some stages involve disjoint choices, and others involve combinations of choices.

Example of Shirts, Pants, and Hats

Let us extend our wardrobe example. Suppose now we have 9 shirts, 5 pairs of pants, and 7 hats. If we want to count how many different outfits we can create. To make an outfit we can pick one shirt, one pair of pants, and one hat.

We would multiply the number of shirts by the number of pants and the number of hats −

$$\mathrm{\text{Total outfits } =\: 9 \:\times\: 5 \:\times\: 7 \:=\: 315}$$

But let us consider we are going to dress casually and only wear a shirt and a pant. Or a shirt and a hat. In that case, we first count the combinations for the shirt-pants pairs and the shirt hat pairs, then add them together −

$$\mathrm{\text{Shirt and Pants combinations } =\: 9 \:\times\: 5 \:=\: 45}$$

$$\mathrm{\text{Shirt and Hat combinations } =\: 9 \:\times\: 7 \:=\: 63}$$

The total number of outfit choices is −

$$\mathrm{\text{Total choices } =\: 45 \:+\: 63 \:= \:108}$$

Here, we used the both the multiplicative and additive principles to arrive at the solution.

Sets and Counting Functions

Another useful concept for the way to count with sets is when dealing with functions between sets. A function from set A to set B assigns each element of A exactly one element in B.

If set A has n elements and set B has k elements, the total number of possible functions is −

$$\mathrm{\text{Total functions } \:=\: k^n}$$

This is because for each element in A, there are k choices in B, and we apply the multiplicative principle.

Example of Counting Functions

Let us see one example for this counting functions. Suppose we want to count how many functions there are from the set {1, 2, 3} to the set {a, b, c, d}. For each of the 3 elements in the domain, there are 4 choices in the codomain.

Therefore, the total number of functions is −

$$\mathrm{\text{Total functions } =\: 4^3 \:=\: 64}$$

This is another example of how the multiplicative principle helps when we are working with sets and functions.

Conclusion

In this chapter, we explained how sets provide a helps us for counting in discrete mathematics. We understood how to apply the additive principle that adds disjoint sets and the multiplicative principle that multiplies when pairing elements from different sets. We also explored the Cartesian product of sets.