Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a few questions regarding Cartesian products that will help me optimize a complicated SQL query I'm working on.

Suppose I have 52 playing cards, and I want to know how many combinations of pairs (first two cards) a dealer can draw at the beginning. Obviously, this would be less than $52*52$ since the dealer cannot draw the same card twice. So, to me it seems the answer is $(52*52) - 52$, since there's 52 "pairs" of the same card, in other words $52*51$.

However, I'd like to better understand the math behind this so I can apply it to any number of cards and any size sets:

  1. Given n cards, how many ordered sets of y cards can be created? For example, if I had 100,000 cards, how many unique sets of 10 cards could I make?

  2. Given n cards, how many unordered sets of y cards can be created? For example, if I had 100 cards, how many unique unordered sets of 3 could I make?

What's the mathematical formula that represents both these answers? Thanks!

share|improve this question

1 Answer 1

up vote 6 down vote accepted

The concepts you are looking for are known as "permutations" and "combinations."

  1. If you have $n$ items, and you want to count how many ordered $r$-tuples you can make without repetitions, the answer is someimtes written $P^n_r$, and: $$P^{n}_{r} = n(n-1)(n-2)\cdots (n-r+1).$$ This follows from the "multiplication rule": if event $A$ can occur in $p$ ways, and event $B$ can occur in $q$ ways, then the number of ways in which both events $A$ and $B$ can occur is $pq$.

    Your answer of $52\times 51$ for ordered pairs of playing cards is correct if you care about which one is the first card and which one is the second. Another way to see this is that there are 52 possible ways in which the first card is dealt; and there are 51 ways for the second card to be dealt (as there are only 51 cards left).

  2. If you don't care about the order, then you have what are called "combinations" (without repeititons). The common symbol is $$\binom{n}{k}$$ which is pronounces "$n$ choose $k$". The symbol represents the number of ways in which you can select $k$ elements from $n$ possibilities, without repetition. In other words, the number of ways to choose subsets with $k$ elements from a set with $n$ elements. The formula is $$\binom{n}{k}=\frac{n!}{k!(n-k)!},\quad \text{if }0\leq k\leq n$$ where $n! = n\times (n-1)\times\cdots\times 2\times 1$.

    To see this, note that there are $\frac{n!}{(n-k)!} = n(n-1)\cdots(n-k+1)$ ways of selecting $k$ items if you do care about the order. But since we don't care about the order, how many times did we pick each subset? For instance, a subset consisting of $1$, $2$, and $3$ is selected six times: once as 1-2-3, once as 1-3-2, once as 2-1-3, once as 2-3-1, once as 3-1-2, and once as 3-2-1.

    Well, there are $k$ items, and so there are $P^k_k$ ways of ordering them; this is exactly $k!$ ways. So we counted each $k$-subset $k!$ ways. So the final answer is $\frac{n!}{(n-k)!}$ divided by $k!$, giving the formula above, $$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$

See also this previous question and answer for the general principles and formulas.

share|improve this answer
    
Excellent! This is basically everything I was hoping for. BTW, if I wanted to plug some real numbers into these formulas, is there a better way than solving each portion using calc.exe (that also doesn't involve really expensive software)? –  Mike Christensen Jan 24 '12 at 17:09
1  
By "real numbers" do you mean "actual numbers", or do you mean real numbers in the sense of "not necessarily positive integers"? If the latter, then these kind of counting formulas don't work. If you mean actual numbers, then there is a lot of simplication that happens with factorials (because you have lots of products), and you can also give very good estimates using Sterling's approximation, that $n!$ is approximately equal to $\sqrt{2\pi n}\left(\frac{n}{e}\right)^n$. –  Arturo Magidin Jan 24 '12 at 17:15
    
Hah! Sorry, I forgot I was talking with a bunch of mathematicians. I meant solve the equations with some realistic numbers - For example, I tried the formula with $n=52$ and $k=2$ (how many unordered pairs of 52 cards) and I get 1,326, I want to make sure that's correct. Using calc.exe is somewhat of a hassle and involves several steps, so I'm curious if there's better software. –  Mike Christensen Jan 24 '12 at 17:29
2  
I suspect most spreadsheets will have the binomial coefficients $\binom{n}{k}$ and permutation formulas already coded in. Open Office, which should be mostly compatible with, say, Excel, has PERMUT(n,k) for the number of ways to select $k$ items out of $n$, order matters, no repetitions, PERMUTA(n,k) if repetitions are allowed and order matters, COMBIN(n,k) for $\binom{n}{k}$, and COMBINA(n,k) for combinations with repetitions. They should all be able to recognize the factorial function as well. –  Arturo Magidin Jan 24 '12 at 17:36
1  
Oh that's handy! Yes, in Excel =PERMUT(52,2) gives me 2,652 and =COMBIN(52,2) gives me my answer of 1,326. Perfect.. –  Mike Christensen Jan 24 '12 at 17:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.