rab@cdcvax.UUCP (Roger Bielefeld) (09/13/83)
I find the discussion of "2=1" extremely boring. How about using this news group for something useful -- like my homework? Here's the first assigned problem in a course in combinatorial mathematics I'm auditing in preparation for a Ph.D. qualifier in computer science: 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)
prodeng@fluke.UUCP (Jim Hirning) (09/15/83)
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