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.

Possible Duplicate:
Combinatorics-N boys and M girls are learning acting skills from a theatre in Mumbai.

N boys and M girls are learning acting skills from a theatre. To perform a play they need to form a group of P actors containing not less than 4 boys and not less than 1 girl. The theatre requires you to write a program that tells them the number of ways the group can be formed.

Note: Composition should be unique and not the order in which the composition is made of.

I have tried a lot but can't get over some of my confusions. How can i solve this ?

share|improve this question

marked as duplicate by Byron Schmuland, André Nicolas, Arturo Magidin, Kannappan Sampath, Brian M. Scott Feb 23 '12 at 5:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
You should tell us what "your confusions" are... –  Arturo Magidin Feb 23 '12 at 4:45
    
@ Arturo Magidin I was considering a case of 6 boys and 2 girls. Now i started with 6C4 * 2C1 + 6C5 * 2C2 + 6C6 * ? . Now i can substitute 2C1 or 2C2 in place of ? . Do i have to consider this case for each case ? –  steve Feb 23 '12 at 4:48
    
(1) You are saying what $N$ and $M$ is, but you don't say what $P$ is; without $P$, you aren't calculating anything. (2) What is it your summands are supposed to be counting? The first summand seems to be that you are selecting four boys and one girl (so your $P$ would be 5); but the next summand suggests you are selecting 5 boys and 2 girls (now your cast is 7?). –  Arturo Magidin Feb 23 '12 at 4:53
    
@ Arturo Magidin P is the total number of actors in a play. They could vary to satisfy the condition of atleast. –  steve Feb 23 '12 at 4:56
    
@steve: I am aware what $P$ is. My point is that if you want to solve the problem with specific numbers, it is not enough to specify how many boys and how many girls there are, you also need to specify what $P$ is. Otherwise, your answer needs to have $P$s all over the place. That's why your attempted answer is nonsense: without a specific $P$, or without leaving $P$ indicated, whatever it is you think you are counting has nothing whatsoever to do with the problem at hand. –  Arturo Magidin Feb 23 '12 at 5:08
add comment

2 Answers 2

If $N\lt 4$, $M\lt 1$, or $P\lt 5$, then you are sunk: there is no way to accomplish the task.

So assume $N\geq 4$, $M\geq 1$, and $P\geq 5$.

How can a particular casting fail to satisfy the conditions? If it is made up entirely of boys (only possible if $M\geq P$), or it contains either no boys, exactly one boy, exactly two boys, or exact three boys (only possible if $M\geq P$, $M\geq P-1$, $M\geq P-2$, or $M\geq P-3$, respectively).

  1. In how many ways can your cast have no girls? You have $\binom{N}{P}$ ways of selecting $P$ boys.

  2. In how many ways can your cast have no boys? You have $\binom{M}{P}$ ways of doing it.

  3. In how many ways can your cast have exactly one boy? There are $\binom{N}{1}$ ways of choosing the boy, and $\binom{M}{P-1}$ ways of choosing the girls.

Continue this way. Then figure out how many total casts you can make without regard of how many boys and girls there are. The number you are looking for will be the total minus the sum of the "bad casts" we are counting above.

share|improve this answer
    
can you please consider the case of 6 boys and 2 girls –  steve Feb 23 '12 at 4:53
    
@steve: Okay, I've considered it. Now what? Seriously: you need three pieces of information to make this a problem with no variables: the value of $N$ (how many boys), the value of $M$ (how many girls), and the value of $P$ (how many people are in the play). The fact that you keep ignoring $P$ is, no doubt, a big part of why you aren't understanding how to do the problem. And I've given you all the information you need to consider any specific case, like $6$ boys, $2$ girls, and $5$ players. Just go through the cases. –  Arturo Magidin Feb 23 '12 at 4:54
add comment

You can think about the problem in either of two ways. One is the way that you seem to have in mind in your comment: add up the possibilities for every possible boy-girl split, from $4$ boys and $P-4$ girls to $P-1$ boys and $1$ girl. (I’m assuming that $N\ge 4$, $M\ge 1$, and $P\ge 5$, so that there is at least one possible combination.) If you do this, you have to evaluate

$$\sum_{n=4}^{P-1}\binom{N}n\binom{M}{P-n}\;:\tag{1}$$

the number of ways of picking $n$ boys out of $N$ is $\binom{N}n$, and the number of ways of picking $P-n$ girls out of $M$ is $\binom{M}{P-n}$, so the number of ways of forming a combination with $n$ boys and $P-n$ girls is $\binom{N}n\binom{M}{P-n}$, and you need to sum these over all possible values of $n$.

If you’re writing a computer program to solve the problem, this is entirely feasible, but it would be rather painful to do by hand if $P$ were very large.

The other possibility is to count the unacceptable combinations and subtract that number from the total. In other words, if there are $u$ unacceptable combinations, calculate $$\binom{N+M}P-u\;.\tag{2}$$ The advantage to this is that if $P$ is at all large, there are fewer ways to form unacceptable combinations than to form acceptable ones:

  • you could have $P$ boys and no girls, or
  • $P$ girls and no boys, or
  • $P-1$ girls and $1$ boy, or
  • $P-2$ girls and $2$ boys, or
  • $P-3$ girls and $3$ boys.

That’s a mere five boy-girl splits to worry about, and instead of the $P-4$ terms of the sum in $(1)$, you’ll have only five terms (and the one subtraction in $(2)$). Thus, as soon a $P$ gets up to $10$ or so you’re better off using the second method.

share|improve this answer
add comment

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