Subsets of subsets

From the 1992 Irish Maths Olympiad:

Let A be a nonempty set with n elements. Find the number of ways of choosing a pair of subsets (B,C) of A such that B is a nonempty subset of C.

__________

My first thought upon reading this problem was that it would be trivial to solve for anyone knowing the following useful fact:

A set containing n elements has exactly 2^n subsets.

I assumed that the answer would come out after a minute’s thought. Then I tried solving it, and quickly realised I had underestimated it.

While the number of choices for the subset C is indeed 2^n, for a particular choice of C, the number of choices for B depends on the number of elements in C, and this could be anything from 1 to n. It appeared the problem was not going to yield to a simple multiplication after all.

Fine. I should still be able to come up with an expression for the answer, using the above fact and the following:

The number of k-element subsets of an n-element set is \binom{n}{k}.

Using these, it follows that the number of possible pairs is

1 \times \binom{n}{0} + 2\times \binom{n}{1} + 4\times \binom{n}{2} + \cdots +2^n \times \binom{n}{n} - 2^n

(The final term above is there to remove all the pairs in which one of the subsets is empty.)

This is all well and good, but actually trying to calculate this turns out to be quite tedious, and only gets worse the larger n becomes. After attempting and failing to find a clever trick to quickly evaluate the expression, I abandoned this approach altogether.

What if, instead of focusing on the subsets one by one, we focus on the individual elements…?

 

Any particular element of A could be (i) in neither B nor C, (ii) in C but not in B, or (iii) in both B and C. These three options are available to each of the n elements in A, so the number of possible pairs of subsets is just 3^n. However, this includes all cases in which B is empty, so the final total is

\boxed{3^n-2^n}

 

On reflection this is an excellent problem – it is a perfect example of how something can be counted in two different ways, and while it took one failed attempt before stumbling upon the simplest approach, I did end up with the identity

1 \times \binom{n}{0} + 2\times \binom{n}{1} + 4\times \binom{n}{2} + \cdots +2^n \times \binom{n}{n}  = 3^n

This does suggest that the problem could have been solved by first obtaining the expression on the left hand side, then spotting that this is just the binomial expansion of (2+1)^n. Hats off to anyone who solves the problem this way!  If I had somehow spotted this myself, I still would have been left wondering: why 3^n?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s