# Choosing elements from sets

OK, so I've always been terrible at combinatorics and I'm trying to generalize some combinatorial problems and I can't figure out where I'm going wrong. Take the following problem:

Assume we are given disjoint finite sets $A_1,A_2,\ldots,A_n$ with $A=\bigcup_i A_i$. How many sets can we form with exactly one element chosen from each $A_i$?

It would seem that the answer is $\prod_i |A_i|$. But then take the following problem:

Assume we draw 4 cards out of a deck. What is the probability that they are of different suits?

This would have the obvious solution:

$$\frac{52\times 39\times 26\times 13}{{52\choose 4}}$$

However, if I let $A_1,\ldots,A_4$ be the different suits, then the above would give me:

$$\frac{13^4}{{52\choose 4}}.$$

Where's my logic going wrong?

I had originally reasoned that if we write $\mathcal{F}=\{(x_1,\ldots,x_n)\mid x_i\in A_i \}$, then we have a map:

$$f:\mathcal{F}\to \mathcal{P}(A),\;\;f(x_1,\ldots,x_n)=\{x_1,\ldots,x_n\}$$

This is clearly a bijection to the subset of elements of $\mathcal{P}(A)$ that satisfy the requirement. Thus, it should be the right answer. My book, however, gave the following as the correct answer to the card problem:

$$\frac{52\times 39\times 26\times 13}{{52\choose 4}}$$

while based on the comments what I thought was the right answer:

$$\frac{13^4}{{52\choose 4}} = \frac{52\times 39\times 26\times 13}{52\times 51\times 50\times 49}$$

is actually correct.

-
I guess the $A_i$ are disjoint and you want to choose exactly one element from each $A_i$? –  Michael Greinecker May 10 '13 at 15:10
Yes, the $A_i$ are disjoint. –  user75789 May 10 '13 at 15:12
It seems like based on the comments, the second answer is correct (this is what I initially wrote down). However, the solution sheet in the back of my textbook claims that the first one is correct... I was puzzled by this, since there's an obvious bijection from the set of size $13^4$ to the subsets of size $4$ of the deck that satisfies the property. –  user75789 May 10 '13 at 15:32

Suppose that the deck has been separated into piles, each containing the cards of one suit, and you’re counting the number of ways to draw one card from each pile. There are $13^4$ ways to do that, since you may take any of the $13$ cards in each of the $4$ piles. Every one of these ways gives you a card from each suit, so in this scheme the probability of drawing one card from each suit is

$$\frac{13^4}{13^4}=1\;.$$

Note that the denominator is not $\binom{52}4$: in this scheme we are not selecting $4$ cards from a single pile of $52$ cards, but rather one card from each of $4$ piles of $13$ cards.

Now return to the original scheme: the suits have not been separated, and you’re drawing $4$ cards from a single pile of $52$ cards. We’ll count the ways to get one card from each suit. The first card drawn may be from any suit, so there are $52$ possible choices. The second must be from one of the other three suits, so there are $52-13=39$ possible choices. Similarly, there are $26$ choices for the third card and $13$ for the fourth card, for a total of $52\cdot39\cdot26\cdot13$ possible sequences of draws resulting in one card from each suit. This calculation uses exactly the same multiplication principle as the calculation that there are $13^4$ ways to draw one card from each suit in the first scheme; it’s just that the relevant sets $A_i$ are different.

Your denominator of $\binom{52}4$, however, is incorrect: it’s the number of sets of $4$ cards that can be drawn from the $52$-card deck, and in the numerator you’re counting $4$-card sequences, not sets. There are actually $52\cdot51\cdot50\cdot49$ possible sequences of draws: the first card can be any of the $52$, the second can be any of the remaining $51$, and so on. Thus, in this scheme the probability of getting one card from each suit is

$$\frac{52\cdot39\cdot26\cdot13}{52\cdot51\cdot50\cdot49}\;.$$

The denominator here is actually $4!\binom{52}4$, the extra factor of $4!$ accounting for the fact that each set of $4$ cards can be drawn in any of $4!$ different orders and therefore corresponds to $24!$ different $4$-card sequences.

-
What bugs me about combinatorics is that in our class we had 10 students and usually about 5 different answers to each question. How do I make this stuff rigorous, since at each step there's a lot of appeal to intuition? I'm curious, since the first answer to the card problem gives the same numeric answer as the solution in the back of the textbook... –  user75789 May 10 '13 at 15:27
@user75789: It is rigorous: there’s no intuition involved. Experience in analyzing such problems, perhaps, but not intuition. I’m not sure which answer you’re calling the first one; the only correct answer appearing either in your question or my answer is $$\frac{52\cdot39\cdot26\cdot13}{52\cdot51\cdot50\cdot49}\;.$$ –  Brian M. Scott May 10 '13 at 15:30

The second answer is the correct one. which is also the same as the direct calculation: $$\frac{52}{52}\frac{39}{51}\frac{26}{50}\frac{13}{49}$$

The first calculation is obviously wrong, as the result is greater than $1$. The logical explanation, is that the way you count the possible number of "good" draws is ordered, e.g. the same set of $4$ different suited cards is counted $4!$ times. However, is the denominator, you counted only unordered draws. Divide the first answer by $4!$ and you will get the same answer is your second, which is right.

-