This problem came up at breakfast. Alice and Bob have 20 different coloured cups and $10$ different coloured plates. They always set the table so that each has a plate and a cup. How many different ways are they able to do this?
I have an answer which seems to be correct but the thing which shocks me is the size of this number. There are $4.5(10^{23})$ ways to do this for the above example. Have I done something wrong?
My answer: for n cups and r plates, where n>r, the number of unique unordered subsets with r elements of the n cups is given by the binomial coefficient nCr. As the ordering of these cups matters when assigning them to the plates we permute these r times by multiplying by r!. Thus, the number of cup-plate combinations K is given by:
$K = \binom{n}{r}r! = \frac{n!}{(n-r)!}$
For $20$ cups and $10$ plates this is $6.7e11$ options.
Now we assign these options to Alice and Bob using a special case of the above formula where $r=2$. The number of ways to set the table N is given by:
$N=K(K-1)$
This gives $4.5e23$ ways of setting the table for 20 distinct cups and $10$ distinct plates for $2$ people.
This number is so big I can hardly believe it. For small examples however, the first formula holds. For example one can check these cup (C) and plate (P) combinations:
$2C, 1P \rightarrow 2$ combinations
$3C, 2P \rightarrow 6$ combinations
$4C, 2P \rightarrow 12$ combinations
$4C, 3P \rightarrow 24$ combinations
$5C, 3P \rightarrow 60$ combinations
Anybody care to confirm or repute this?
Okay, let's first look at the answer. Then you might realise where you have gone wrong. If not I have explained it at the end.
Giving n cups, r plates to 2 people.
There are $n$ cups. So give them each one cup. Choose 2 cups in $ ^nC_2$ ways and distribute to them in $2!$ ways. I hope you are familiar with the permutation notation. $$ ^nP_r = \frac{n!}{(n-r)!}$$
That will make the number is ways to pick the cups $$ ^nC_2 \times 2! = \frac{n!}{(n-2)!} =\ ^nP_2 $$
Then there are $r$ plates. Pick two and allot in the same way. That means we can distribute the plates in $\ ^rP_2$ ways.
Therefore $n$ cups and $r$ plates can be picked for 2 people in $ ^ nP_2\times \ ^rP_2$ ways. For this problem, $n=20$ and $r=10$. So there are $ ^ {20}P_2\times \ ^{10}P_2$ ways. This number is equal to $$\frac{20!}{18!}\times \frac{10!}{8!}=20\times 19 \times 10\times 9=34200$$.
Now coming to the part where you have gone wrong, first you did $ ^nP_r$. That means you have found out the number of ways to couple the cups and the plates. And then you said you wanted to do $K(K+1)$ which obviously is $\ ^KP_2$. That means you are giving from among $K$ things to two people. That's fine, but look at what are those $K$ things are. They are the number of ways you can couple the cups and plates. You are distributing to 2 people from the number of ways. You can't distribute the number of ways. You can distribute cups, or plates, but not ways.
Now, I get your line of thought. You thought that at the end, each of Alice and Bob will get a pair of cup and a plate. So you are counting how many ways they can be coupled. And then picking 2 couplings out of those and giving one to each. But you have to remember that all these couplings will not exist simultaneously. Those $K$ couplings comprise of plate 1 coupled with cup 1, and also plate 1 coupled with cup 2. Obviously, the case, where you pick these two couplings and give them each to Alice and Bob, is invalid.