Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 beta 3/9/83; site fluke.UUCP
Path: utzoo!linus!decvax!tektronix!uw-beaver!ssc-vax!fluke!prodeng
From: prodeng@fluke.UUCP (Jim Hirning)
Newsgroups: net.math
Subject: Re: my homework
Message-ID: <702@vax2.fluke.UUCP>
Date: Thu, 15-Sep-83 16:14:41 EDT
Article-I.D.: vax2.702
Posted: Thu Sep 15 16:14:41 1983
Date-Received: Fri, 16-Sep-83 19:53:56 EDT
References: <111@cdcvax.UUCP>
Organization: John Fluke Mfg. Co., Everett, Wash
Lines: 43


	In how many ways can we choose 2r people from n married couples
	in such a way that there are exactly k married couples among the
	2r people? (k <= r <= n)

I think the best way to approach this problem is backwards: look at how many
ways we can have k married couples, and then how many ways each of these
sets of k married couples can be extended to 2r people, without adding
any more couples.

Since we have n couples, the number of ways to choose k of them is C(n,k).
(combinations of n things k at a time)

Next, extend.  We must choose 2r - 2k more people (the difference between
the 2r people required and the 2k people we have already chosen in k couples).
But, we must not add any more couples.  Thus we must choose *at most* 1
person from each couple remaining.

To do this, let us first choose the correct number of couples, then for each
couple, choose one person.

Since we must choose 2r - 2k more people, we must choose 2r - 2k couples from
the couples remaining.  Since there are n - k couples remaining, the ways
to choose couples are C(n-k,2r-2k).

For each couple chosen, either spouse may be picked.  So, the number of ways
to choose a spouse from each couple is 2^(number of couples) = 2^(2r-2k).

Thus, the ways to choose 2r people from n married couples, such that we
have exactly k married couples among the 2r people is (the ways to choose
k couples) X (the ways to choose enough couples to extend to 2r people) X
(the ways to choose one spouse per couple) = C(n,k) X C(n-k,2r-2k) X 2^(2r-2k).

Any time that such combinations are undefined (ex: 2r-2k > n-k) the combination
is assigned the value 0.  (I believe this is standard procedure anyway)



So: Answer **** C(n,k) X C(n-k,2r-2k) X 2^(2r-2k) ****


	Debbie Smit