Combinations of Combinations?

Date: 12/15/2003 at 17:31:32
From: Charles
Subject: Combinations of combinations!

I understand the formula n!/((n-r)!*r!) to compute the number of 
combinations of r objects selected from n objects.  My question is
this--having determined nCr, how do I calculate M, the number of
resulting sets which contain, say, t items?

For example, I have 4 items A, B, C, and D.  Selecting any 3 gives 4
combinations; ABC, ABD, BCD, and ACD.  These 4 sets contain 2
occurrences of AB.  In this simple example t = 2 and the result M is
2.  Similarly, if t=1 then M = 3.

My question is how do I compute M in the general case?  None of the
standard texts seem to deal with this problem.  I am 57 and studying
A-Level maths.

Date: 12/15/2003 at 19:07:42
From: Doctor Schwa
Subject: Re: Combinations of combinations!

Hi Charles -

Nice question!  Here's how I see it.

Out of the combinations (4 of them in your example) with 3 letters out
of 4 total, the first letter (A) has a 3/4 chance of being in the
combination you list.  Then, once that letter is used up, the second
letter (B) has a 2/3 chance of being in the combination (since the
combination has 2 letters left unused, out of a total of 3 letters
left after using A).

So, the answer is (4 choose 3) * (3/4) * (2/3).  In the general case,
you'll have

  (n choose r) * (r/n) * (r-1)/(n-1) * ...,

where the "..." goes on for t factors (ending with (r-t+1)/(n-t+1), I
guess).

Then that product can be rewritten with factorials, since r*(r-1)*...
with t terms in it is r!/(r-t)!

  (n choose r) * (r!/(r-t)!) * ((n-t)!/n!), or overall

    n! * r! * (n-t)!
  --------------------
  (n-r)! r! (r-t)! n!

which reduces a whole lot, to

       (n-t)!
  ----------------
   (n-r)! * (r-t)!

and then since the two numbers in the bottom add up to n-t, it
miraculously turns into (n-t choose r-t).  Wow!

So there must be a simpler reason why (n-t) choose (r-t) is the right
answer.  And now that I get to this point, I see it:

To make a choice of r things from n, which contains a certain
specified t symbols, you first choose the specified t symbols (only 1
way to do that!) and then choose the other (r-t) from the remaining (n-t).

So it really is only a combination problem, after all!

Thanks for the fun problem,

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 12/17/2003 at 18:24:07
From: Charles
Subject: Thank you (Combinations of combinations!)

Thanks, that's a neat solution.  It has helped me very much
consolidate my thinking on the subject.