How to count subsets

Tivadar Danka small portrait Tivadar Danka
Subsets of a set with three elements

Understanding math will make you a better engineer.

So, I am writing the best and most comprehensive book about it.

There is a profound lesson even in some of the simplest mathematical problems: a good representation is half the success. For example, can you count the number of subsets in a finite set?

Let's see what the solution can teach us!

First things first: notations and definitions. A set between the absolute value symbols denotes the number of elements in the given set. This is called cardinality.

A: the number of elements in A(the cardinality of A)\begin{align*} |A|: &\text{ the number of elements in } A \\ &(\text{the \textit{cardinality} of } A) \end{align*}

Moreover, 2\textstyle 2 raised to the power of a set is just the set of all its subsets. (That is, its power set.)

2A: the set of all subsets of A(the power set of A)\begin{align*} 2^A: &\text{ the set of all subsets of } A \\ &(\text{the \textit{power set} of } A) \end{align*}

Back to counting subsets!

A natural idea is to count the subsets of a given size separately and then sum them up. This works as well but requires knowledge about binomial coefficients.

Grouping subsets by its elements

However, we can find a much better way by looking at subsets differently!

We can represent each subset with a 0-1 vector, whose components encode the membership of the given elements. This is much easier to count.

Encoding subsets with membership vectors

The membership vectors establish a bijection between the power set and the Cartesian product {0,1}×{0,1}×{0,1} \{0, 1\} \times \{0, 1\} \times \{0, 1\} . Counting the elements of one is the same as counting the other. And elements of Cartesian products are easy to count!

To be more precise, we have the bijection

f:2{1,2,3}{0,1}3,{1,2,3}S(c1,c2,c3){0,1}3,\begin{align*} f: 2^{\{1, 2, 3\}} &\to \{0, 1\}^3, \\ \{1, 2, 3\} \supseteq S &\mapsto (c_1, c_2, c_3) \in \{0, 1\}^{3}, \end{align*}

where cic_i is defined by

ci={0if iS1if iS. c_i = \begin{cases} 0 & \text{if } i \notin S \\ 1 & \text{if } i \in S. \end{cases}

By visualizing {0,1}\{0, 1\} and its powers, we notice a pattern: with each product, the number of elements doubles! Thus, their cardinality is easy to calculate.

Counting the elements of Cartesian products

This method can be applied to any finite set as well. By encoding the subsets by a membership vector, we can establish a bijection between the power set and the powers of {0,1}\{0, 1\}. In this general case, the bijection is defined by

f:2A{0,1}A,AS(c1,c2,,cA){0,1}A,\begin{align*} f: 2^{A} &\to \{0, 1\}^{|A|}, \\ A \supseteq S &\mapsto (c_1, c_2, \dots, c_{|A|}) \in \{0, 1\}^{|A|}, \end{align*}

where cic_i is again

ci={0if iS1if iS. c_i = \begin{cases} 0 & \text{if } i \notin S \\ 1 & \text{if } i \in S. \end{cases}

Thus, we obtain the general formula describing the cardinality of power sets:

2A={0,1}A=2A.|2^A| = |\{0, 1\}^{|A|}| = 2^{|A|}.

You can see for yourself how far a good representation can take us! By utilizing a simple bijection, we transformed the problem into a much simpler one.

In mathematics, this is often the key.

Having a deep understanding of math will make you a better engineer.

I want to help you with this, so I am writing a comprehensive book that takes you from high school math to the advanced stuff.
Join me on this journey and let's do this together!