Let S = $\{1, 2, 3, ..., n\}$. Let set A be a selection of integers from S. Let set B also be a selection of integers from set S.

  1. How many ways are there of choosing the elements for both A and B such that every element in A is also in B?

  2. How many ways are there of choosing the elements for both A and B such that every element in A is also in B, and B contains at least one element not in A?

I'm not certain about it, but I have the feeling that problem one can be solved by just finding all possible subsets of B, so its solution is $2^n$. But given this line of reasoning, I can't seem to figure out what I should subtract from $2^n$ to account for any cases where all elements are the same in both sets. I'm stumped.

Thanks for any help.


We solve the first problem. You can then solve the second by using the count of the first problem, and counting how many of these are "bad" (do not satisfy the added condition of the second problem).

We want to choose two subsets $A$ and $B$ of $S$ such that $A\subseteq B$.

Suppose that we have chosen such sets $A$, $B$. We will say that an element $k$ of $S$ is of Type 1 if $k\in A$. We will say $k$ is of Type 2 if $k$ is in $B$ but not in $A$. And we will say $k$ is of Type $3$ if it is not in $B$.

Define $f:S\to\{1,2,3\}$ by letting $f(k)$ be the type of $k$.

Every function $f:S\to\{1,2,3\}$ determines a choice of $A$ and $B$ such that $A\subseteq B$. And conversely every choice of $A\subseteq B$ determines a function. Thus the number of choices is the number of functions, it is $3^n$.

Remark: We can also solve the problem a longer way. Let $0\le i\le n$. We can choose $i$ elements of $S$ to be in $A$ in $\binom{n}{i}$ ways. That leaves $n-i$ elements of $S$. We can pick a subset of this set to add to $A$ to make $B$ in $2^{n-i}$ ways. It follows that the total number of possibilities is $$\sum_{i=0}^n \binom{n}{i}2^{n-i}.\tag{1}$$ We recognize (1) as the Binomial Theorem expansion of $(1+2)^n$.

| cite | improve this answer | |
  • $\begingroup$ Thank you! This makes a lot of intuitive sense, and I appreciate the additional solution. As for part b, I can see now why my original solution is so far off, but I'd like to make sure that I'm understanding this properly now. Would the answer be $3^n - 2^n$? My explanation would be that, for every subset of $S$ there will be one case where $A$ and $B$ are the same subset. These are the cases that I need to remove. This is simply the number of subsets of $S$, which is $2^n$. Does that sound logical? $\endgroup$ – user176049 Sep 21 '14 at 17:16
  • $\begingroup$ You are welcome. You have counted the "bad" ones correctly. $\endgroup$ – André Nicolas Sep 21 '14 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy