Mixing
Combinations involving distinct sets of variables
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let's say I have two entirely distinct groupings of things that I wish to combine. The first set contains three items: $A, B, C$, while the second set contains five items: $V, W, X, Y, Z$. Now let's suppose that I have to combine items from these sets to form groups of 3 items, ensuring that 1 and only 1 item from the first set is present, with no repetition allowed. So $A, V, Y$ would not be considered distinct from $A, Y, V$. The basics of permutations and combinations are easy enough to grasp, and even this problem can be approached with reasonable efficiency by treating it as a combination of two elements from the second set, then multiplying the outcome by the number of distinct items in the first set. But what if we were given a range?
Say, for example, that now I say the set of 3 items needs to have 'at least' one item from the first set, but could potentially have more? If more than two distinct sets are introduced and I'm asked to come up with combinations between those, or for larger sets, it gets more complicated still.
These problems keep coming up for me lately, and I'm in need of a scaleable approach.
combinatorics combinations
asked Jul 16 at 19:25
user242007
27517
add a comment |Â
up vote
2
down vote
favorite
Let's say I have two entirely distinct groupings of things that I wish to combine. The first set contains three items: $A, B, C$, while the second set contains five items: $V, W, X, Y, Z$. Now let's suppose that I have to combine items from these sets to form groups of 3 items, ensuring that 1 and only 1 item from the first set is present, with no repetition allowed. So $A, V, Y$ would not be considered distinct from $A, Y, V$. The basics of permutations and combinations are easy enough to grasp, and even this problem can be approached with reasonable efficiency by treating it as a combination of two elements from the second set, then multiplying the outcome by the number of distinct items in the first set. But what if we were given a range?
Say, for example, that now I say the set of 3 items needs to have 'at least' one item from the first set, but could potentially have more? If more than two distinct sets are introduced and I'm asked to come up with combinations between those, or for larger sets, it gets more complicated still.
These problems keep coming up for me lately, and I'm in need of a scaleable approach.
combinatorics combinations
asked Jul 16 at 19:25
user242007
27517
Larger generalized example: Suppose you have $M$ men and $W$ women and you wish to form a committee of size $k$ such that you have at least $m$ men and at least $w$ women. There will be $sumlimits_i=m^k-wbinomMibinomWk-i$ such possibilities. This can simplify further in certain special situations such as needing "at least one man and at least one woman" by noting vandermonde's identity giving a total of $binomM+Wk-binomMk-binomWk$, but it does not otherwise simplify nicely.
– JMoravitz
Jul 16 at 19:39
This is seen from direct application of binomial coefficients and the rules of sum and product.
– JMoravitz
Jul 16 at 19:39
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let's say I have two entirely distinct groupings of things that I wish to combine. The first set contains three items: $A, B, C$, while the second set contains five items: $V, W, X, Y, Z$. Now let's suppose that I have to combine items from these sets to form groups of 3 items, ensuring that 1 and only 1 item from the first set is present, with no repetition allowed. So $A, V, Y$ would not be considered distinct from $A, Y, V$. The basics of permutations and combinations are easy enough to grasp, and even this problem can be approached with reasonable efficiency by treating it as a combination of two elements from the second set, then multiplying the outcome by the number of distinct items in the first set. But what if we were given a range?
Say, for example, that now I say the set of 3 items needs to have 'at least' one item from the first set, but could potentially have more? If more than two distinct sets are introduced and I'm asked to come up with combinations between those, or for larger sets, it gets more complicated still.
These problems keep coming up for me lately, and I'm in need of a scaleable approach.
combinatorics combinations
asked Jul 16 at 19:25
user242007
27517
Let's say I have two entirely distinct groupings of things that I wish to combine. The first set contains three items: $A, B, C$, while the second set contains five items: $V, W, X, Y, Z$. Now let's suppose that I have to combine items from these sets to form groups of 3 items, ensuring that 1 and only 1 item from the first set is present, with no repetition allowed. So $A, V, Y$ would not be considered distinct from $A, Y, V$. The basics of permutations and combinations are easy enough to grasp, and even this problem can be approached with reasonable efficiency by treating it as a combination of two elements from the second set, then multiplying the outcome by the number of distinct items in the first set. But what if we were given a range?
Say, for example, that now I say the set of 3 items needs to have 'at least' one item from the first set, but could potentially have more? If more than two distinct sets are introduced and I'm asked to come up with combinations between those, or for larger sets, it gets more complicated still.
These problems keep coming up for me lately, and I'm in need of a scaleable approach.
combinatorics combinations
asked Jul 16 at 19:25
user242007
27517
asked Jul 16 at 19:25
user242007
27517
asked Jul 16 at 19:25
user242007
27517
asked Jul 16 at 19:25
user242007
27517
27517
Larger generalized example: Suppose you have $M$ men and $W$ women and you wish to form a committee of size $k$ such that you have at least $m$ men and at least $w$ women. There will be $sumlimits_i=m^k-wbinomMibinomWk-i$ such possibilities. This can simplify further in certain special situations such as needing "at least one man and at least one woman" by noting vandermonde's identity giving a total of $binomM+Wk-binomMk-binomWk$, but it does not otherwise simplify nicely.
– JMoravitz
Jul 16 at 19:39
This is seen from direct application of binomial coefficients and the rules of sum and product.
– JMoravitz
Jul 16 at 19:39
add a comment |Â
Larger generalized example: Suppose you have $M$ men and $W$ women and you wish to form a committee of size $k$ such that you have at least $m$ men and at least $w$ women. There will be $sumlimits_i=m^k-wbinomMibinomWk-i$ such possibilities. This can simplify further in certain special situations such as needing "at least one man and at least one woman" by noting vandermonde's identity giving a total of $binomM+Wk-binomMk-binomWk$, but it does not otherwise simplify nicely.
– JMoravitz
Jul 16 at 19:39
This is seen from direct application of binomial coefficients and the rules of sum and product.
– JMoravitz
Jul 16 at 19:39
Larger generalized example: Suppose you have $M$ men and $W$ women and you wish to form a committee of size $k$ such that you have at least $m$ men and at least $w$ women. There will be $sumlimits_i=m^k-wbinomMibinomWk-i$ such possibilities. This can simplify further in certain special situations such as needing "at least one man and at least one woman" by noting vandermonde's identity giving a total of $binomM+Wk-binomMk-binomWk$, but it does not otherwise simplify nicely.
– JMoravitz
Jul 16 at 19:39
Larger generalized example: Suppose you have $M$ men and $W$ women and you wish to form a committee of size $k$ such that you have at least $m$ men and at least $w$ women. There will be $sumlimits_i=m^k-wbinomMibinomWk-i$ such possibilities. This can simplify further in certain special situations such as needing "at least one man and at least one woman" by noting vandermonde's identity giving a total of $binomM+Wk-binomMk-binomWk$, but it does not otherwise simplify nicely.
– JMoravitz
Jul 16 at 19:39
This is seen from direct application of binomial coefficients and the rules of sum and product.
– JMoravitz
Jul 16 at 19:39
This is seen from direct application of binomial coefficients and the rules of sum and product.
– JMoravitz
Jul 16 at 19:39
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
0
down vote
As shown in the comment, it is about applying many times simple operations.
I will work a larger example, using species and e.g.f. Suppose there are two sorts, M and W and we have 15 M and 17 W. We have to form a team of 3....5 M and say, 6....9 W.
The species formula is:
$E(M)cdot[E_3(M)+E_4(M)+E_5(M)] cdot [E_6(W)+E_7(W)+E_8(W)+E_9(W)]cdot E(W)$
The first two factors means that our structure is a subset of size 3 or 4 or 5 and the last two factors means that we have a subset of size 6, or 7, or 8, or 9 for the sort W.
Then we write the e.g.f.
$exp(m).(frac m^33! + frac m^44!+ frac m^55!) . (frac w^66! + frac w^77!+ frac w^88! + frac w^99! ) . exp(w) $
I personally use the maple mtaylor function to truncate exp(x) to a suitable size that covers the biggest cardinals that occur.
Now we are interested in the coefficient of $fracm^1515! fracw^1717!$ in the above e.g.f. because it represents the answer.
Caution, working with species and e.g.f. is somehow like tightrope walking - it needs some precautions.
answered Jul 16 at 23:54
nbaxter
45710
add a comment |Â
up vote
0
down vote
You question is probably best considered as two different types of questions.
- If the constraint is a closed range, for example 'between 1 and 3 items from the first set", and
- If the constraint is a half-open range. For example, 'at least 1 item from the first set.
(Suppose in both scenarios, I use the notation that the $k$-th set, $S_k$ has $n_k$ items.)
Type 1. Closed Range constraints. ('between')
The solution to these questions can best be obtained by considering each of the integer options in the range separately. That is, 'between 1 and 3 items from the first set' corresponds to
- exactly 1 set from S_1, and m-1 from S_2, which is $binomn_11binomn_2m-1$, or
exactly 2 items from S_1 and m-2 from S_2, $binomn_12binomn_2m-2$, or
exactly 3 items from S_1 and m-2 from S_2, $binomn_13binomn_2m-3$.
Then the final answer is the combine (sum) of these three components. That is,
$$binomn_11binomn_1m-1 + binomn_12binomn_1m-2 + binomn_13binomn_1m-3$$
You should be able to see how this easily generalises.
Type 2. Half open constraints. ('at least')
The key to solving these questions is to break it up into two stages.
- Find the number of combinations that fulfil the each of the minimum constraint(s), and then
- Select the remaining balls freely.
That is, in your case, suppose the first set has $n_1$ items and the second set has $n_2$, and you need to select a total of $m$ items, where at least $k_1$ items are from the first set.
Then, first select the $k_1$ items from this first set. This can be done in in $binomn_1k_1$ways.
Then select the remaining $m-k_1$ items. These can be selected without restriction and so can be from either set, so the number of combinations is $binomn_1+n_2m-k_1$.
Then combine (multipy) these to get the total number of combinations.
$$ binomn_1k_1 binomn_1+n_2m-k_1 $$
This naturally generalizes to an arbitrary number of sets. For example, suppose you need to select a total of $m$ items, where at least $k_1$ items are from the first set, $k_2$ items are from the second set and $k_3$ items are from the third set.
Then following the same method, the final answer is
$$ binomn_1k_1 binomn_2k_2 binomn_3k_3 binomn_1+n_2+n_3m-k_1-k_2-k_3 $$
answered Jul 17 at 4:53
Martin Roberts
1,189318
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
As shown in the comment, it is about applying many times simple operations.
I will work a larger example, using species and e.g.f. Suppose there are two sorts, M and W and we have 15 M and 17 W. We have to form a team of 3....5 M and say, 6....9 W.
The species formula is:
$E(M)cdot[E_3(M)+E_4(M)+E_5(M)] cdot [E_6(W)+E_7(W)+E_8(W)+E_9(W)]cdot E(W)$
The first two factors means that our structure is a subset of size 3 or 4 or 5 and the last two factors means that we have a subset of size 6, or 7, or 8, or 9 for the sort W.
Then we write the e.g.f.
$exp(m).(frac m^33! + frac m^44!+ frac m^55!) . (frac w^66! + frac w^77!+ frac w^88! + frac w^99! ) . exp(w) $
I personally use the maple mtaylor function to truncate exp(x) to a suitable size that covers the biggest cardinals that occur.
Now we are interested in the coefficient of $fracm^1515! fracw^1717!$ in the above e.g.f. because it represents the answer.
Caution, working with species and e.g.f. is somehow like tightrope walking - it needs some precautions.
answered Jul 16 at 23:54
nbaxter
45710
add a comment |Â
up vote
0
down vote
As shown in the comment, it is about applying many times simple operations.
I will work a larger example, using species and e.g.f. Suppose there are two sorts, M and W and we have 15 M and 17 W. We have to form a team of 3....5 M and say, 6....9 W.
The species formula is:
$E(M)cdot[E_3(M)+E_4(M)+E_5(M)] cdot [E_6(W)+E_7(W)+E_8(W)+E_9(W)]cdot E(W)$
The first two factors means that our structure is a subset of size 3 or 4 or 5 and the last two factors means that we have a subset of size 6, or 7, or 8, or 9 for the sort W.
Then we write the e.g.f.
$exp(m).(frac m^33! + frac m^44!+ frac m^55!) . (frac w^66! + frac w^77!+ frac w^88! + frac w^99! ) . exp(w) $
I personally use the maple mtaylor function to truncate exp(x) to a suitable size that covers the biggest cardinals that occur.
Now we are interested in the coefficient of $fracm^1515! fracw^1717!$ in the above e.g.f. because it represents the answer.
Caution, working with species and e.g.f. is somehow like tightrope walking - it needs some precautions.
answered Jul 16 at 23:54
nbaxter
45710
add a comment |Â
up vote
0
down vote
up vote
0
down vote
As shown in the comment, it is about applying many times simple operations.
I will work a larger example, using species and e.g.f. Suppose there are two sorts, M and W and we have 15 M and 17 W. We have to form a team of 3....5 M and say, 6....9 W.
The species formula is:
$E(M)cdot[E_3(M)+E_4(M)+E_5(M)] cdot [E_6(W)+E_7(W)+E_8(W)+E_9(W)]cdot E(W)$
The first two factors means that our structure is a subset of size 3 or 4 or 5 and the last two factors means that we have a subset of size 6, or 7, or 8, or 9 for the sort W.
Then we write the e.g.f.
$exp(m).(frac m^33! + frac m^44!+ frac m^55!) . (frac w^66! + frac w^77!+ frac w^88! + frac w^99! ) . exp(w) $
I personally use the maple mtaylor function to truncate exp(x) to a suitable size that covers the biggest cardinals that occur.
Now we are interested in the coefficient of $fracm^1515! fracw^1717!$ in the above e.g.f. because it represents the answer.
Caution, working with species and e.g.f. is somehow like tightrope walking - it needs some precautions.
answered Jul 16 at 23:54
nbaxter
45710
As shown in the comment, it is about applying many times simple operations.
I will work a larger example, using species and e.g.f. Suppose there are two sorts, M and W and we have 15 M and 17 W. We have to form a team of 3....5 M and say, 6....9 W.
The species formula is:
$E(M)cdot[E_3(M)+E_4(M)+E_5(M)] cdot [E_6(W)+E_7(W)+E_8(W)+E_9(W)]cdot E(W)$
The first two factors means that our structure is a subset of size 3 or 4 or 5 and the last two factors means that we have a subset of size 6, or 7, or 8, or 9 for the sort W.
Then we write the e.g.f.
$exp(m).(frac m^33! + frac m^44!+ frac m^55!) . (frac w^66! + frac w^77!+ frac w^88! + frac w^99! ) . exp(w) $
I personally use the maple mtaylor function to truncate exp(x) to a suitable size that covers the biggest cardinals that occur.
Now we are interested in the coefficient of $fracm^1515! fracw^1717!$ in the above e.g.f. because it represents the answer.
Caution, working with species and e.g.f. is somehow like tightrope walking - it needs some precautions.
answered Jul 16 at 23:54
nbaxter
45710
answered Jul 16 at 23:54
nbaxter
45710
answered Jul 16 at 23:54
nbaxter
45710
answered Jul 16 at 23:54
nbaxter
45710
45710
add a comment |Â
add a comment |Â
up vote
0
down vote
You question is probably best considered as two different types of questions.
- If the constraint is a closed range, for example 'between 1 and 3 items from the first set", and
- If the constraint is a half-open range. For example, 'at least 1 item from the first set.
(Suppose in both scenarios, I use the notation that the $k$-th set, $S_k$ has $n_k$ items.)
Type 1. Closed Range constraints. ('between')
The solution to these questions can best be obtained by considering each of the integer options in the range separately. That is, 'between 1 and 3 items from the first set' corresponds to
- exactly 1 set from S_1, and m-1 from S_2, which is $binomn_11binomn_2m-1$, or
exactly 2 items from S_1 and m-2 from S_2, $binomn_12binomn_2m-2$, or
exactly 3 items from S_1 and m-2 from S_2, $binomn_13binomn_2m-3$.
Then the final answer is the combine (sum) of these three components. That is,
$$binomn_11binomn_1m-1 + binomn_12binomn_1m-2 + binomn_13binomn_1m-3$$
You should be able to see how this easily generalises.
Type 2. Half open constraints. ('at least')
The key to solving these questions is to break it up into two stages.
- Find the number of combinations that fulfil the each of the minimum constraint(s), and then
- Select the remaining balls freely.
That is, in your case, suppose the first set has $n_1$ items and the second set has $n_2$, and you need to select a total of $m$ items, where at least $k_1$ items are from the first set.
Then, first select the $k_1$ items from this first set. This can be done in in $binomn_1k_1$ways.
Then select the remaining $m-k_1$ items. These can be selected without restriction and so can be from either set, so the number of combinations is $binomn_1+n_2m-k_1$.
Then combine (multipy) these to get the total number of combinations.
$$ binomn_1k_1 binomn_1+n_2m-k_1 $$
This naturally generalizes to an arbitrary number of sets. For example, suppose you need to select a total of $m$ items, where at least $k_1$ items are from the first set, $k_2$ items are from the second set and $k_3$ items are from the third set.
Then following the same method, the final answer is
$$ binomn_1k_1 binomn_2k_2 binomn_3k_3 binomn_1+n_2+n_3m-k_1-k_2-k_3 $$
answered Jul 17 at 4:53
Martin Roberts
1,189318
add a comment |Â
up vote
0
down vote
You question is probably best considered as two different types of questions.
- If the constraint is a closed range, for example 'between 1 and 3 items from the first set", and
- If the constraint is a half-open range. For example, 'at least 1 item from the first set.
(Suppose in both scenarios, I use the notation that the $k$-th set, $S_k$ has $n_k$ items.)
Type 1. Closed Range constraints. ('between')
The solution to these questions can best be obtained by considering each of the integer options in the range separately. That is, 'between 1 and 3 items from the first set' corresponds to
- exactly 1 set from S_1, and m-1 from S_2, which is $binomn_11binomn_2m-1$, or
exactly 2 items from S_1 and m-2 from S_2, $binomn_12binomn_2m-2$, or
exactly 3 items from S_1 and m-2 from S_2, $binomn_13binomn_2m-3$.
Then the final answer is the combine (sum) of these three components. That is,
$$binomn_11binomn_1m-1 + binomn_12binomn_1m-2 + binomn_13binomn_1m-3$$
You should be able to see how this easily generalises.
Type 2. Half open constraints. ('at least')
The key to solving these questions is to break it up into two stages.
- Find the number of combinations that fulfil the each of the minimum constraint(s), and then
- Select the remaining balls freely.
That is, in your case, suppose the first set has $n_1$ items and the second set has $n_2$, and you need to select a total of $m$ items, where at least $k_1$ items are from the first set.
Then, first select the $k_1$ items from this first set. This can be done in in $binomn_1k_1$ways.
Then select the remaining $m-k_1$ items. These can be selected without restriction and so can be from either set, so the number of combinations is $binomn_1+n_2m-k_1$.
Then combine (multipy) these to get the total number of combinations.
$$ binomn_1k_1 binomn_1+n_2m-k_1 $$
This naturally generalizes to an arbitrary number of sets. For example, suppose you need to select a total of $m$ items, where at least $k_1$ items are from the first set, $k_2$ items are from the second set and $k_3$ items are from the third set.
Then following the same method, the final answer is
$$ binomn_1k_1 binomn_2k_2 binomn_3k_3 binomn_1+n_2+n_3m-k_1-k_2-k_3 $$
answered Jul 17 at 4:53
Martin Roberts
1,189318
add a comment |Â
up vote
0
down vote
up vote
0
down vote
You question is probably best considered as two different types of questions.
- If the constraint is a closed range, for example 'between 1 and 3 items from the first set", and
- If the constraint is a half-open range. For example, 'at least 1 item from the first set.
(Suppose in both scenarios, I use the notation that the $k$-th set, $S_k$ has $n_k$ items.)
Type 1. Closed Range constraints. ('between')
The solution to these questions can best be obtained by considering each of the integer options in the range separately. That is, 'between 1 and 3 items from the first set' corresponds to
- exactly 1 set from S_1, and m-1 from S_2, which is $binomn_11binomn_2m-1$, or
exactly 2 items from S_1 and m-2 from S_2, $binomn_12binomn_2m-2$, or
exactly 3 items from S_1 and m-2 from S_2, $binomn_13binomn_2m-3$.
Then the final answer is the combine (sum) of these three components. That is,
$$binomn_11binomn_1m-1 + binomn_12binomn_1m-2 + binomn_13binomn_1m-3$$
You should be able to see how this easily generalises.
Type 2. Half open constraints. ('at least')
The key to solving these questions is to break it up into two stages.
- Find the number of combinations that fulfil the each of the minimum constraint(s), and then
- Select the remaining balls freely.
That is, in your case, suppose the first set has $n_1$ items and the second set has $n_2$, and you need to select a total of $m$ items, where at least $k_1$ items are from the first set.
Then, first select the $k_1$ items from this first set. This can be done in in $binomn_1k_1$ways.
Then select the remaining $m-k_1$ items. These can be selected without restriction and so can be from either set, so the number of combinations is $binomn_1+n_2m-k_1$.
Then combine (multipy) these to get the total number of combinations.
$$ binomn_1k_1 binomn_1+n_2m-k_1 $$
This naturally generalizes to an arbitrary number of sets. For example, suppose you need to select a total of $m$ items, where at least $k_1$ items are from the first set, $k_2$ items are from the second set and $k_3$ items are from the third set.
Then following the same method, the final answer is
$$ binomn_1k_1 binomn_2k_2 binomn_3k_3 binomn_1+n_2+n_3m-k_1-k_2-k_3 $$
answered Jul 17 at 4:53
Martin Roberts
1,189318
You question is probably best considered as two different types of questions.
- If the constraint is a closed range, for example 'between 1 and 3 items from the first set", and
- If the constraint is a half-open range. For example, 'at least 1 item from the first set.
(Suppose in both scenarios, I use the notation that the $k$-th set, $S_k$ has $n_k$ items.)
Type 1. Closed Range constraints. ('between')
The solution to these questions can best be obtained by considering each of the integer options in the range separately. That is, 'between 1 and 3 items from the first set' corresponds to
- exactly 1 set from S_1, and m-1 from S_2, which is $binomn_11binomn_2m-1$, or
exactly 2 items from S_1 and m-2 from S_2, $binomn_12binomn_2m-2$, or
exactly 3 items from S_1 and m-2 from S_2, $binomn_13binomn_2m-3$.
Then the final answer is the combine (sum) of these three components. That is,
$$binomn_11binomn_1m-1 + binomn_12binomn_1m-2 + binomn_13binomn_1m-3$$
You should be able to see how this easily generalises.
Type 2. Half open constraints. ('at least')
The key to solving these questions is to break it up into two stages.
- Find the number of combinations that fulfil the each of the minimum constraint(s), and then
- Select the remaining balls freely.
That is, in your case, suppose the first set has $n_1$ items and the second set has $n_2$, and you need to select a total of $m$ items, where at least $k_1$ items are from the first set.
Then, first select the $k_1$ items from this first set. This can be done in in $binomn_1k_1$ways.
Then select the remaining $m-k_1$ items. These can be selected without restriction and so can be from either set, so the number of combinations is $binomn_1+n_2m-k_1$.
Then combine (multipy) these to get the total number of combinations.
$$ binomn_1k_1 binomn_1+n_2m-k_1 $$
This naturally generalizes to an arbitrary number of sets. For example, suppose you need to select a total of $m$ items, where at least $k_1$ items are from the first set, $k_2$ items are from the second set and $k_3$ items are from the third set.
Then following the same method, the final answer is
$$ binomn_1k_1 binomn_2k_2 binomn_3k_3 binomn_1+n_2+n_3m-k_1-k_2-k_3 $$
answered Jul 17 at 4:53
Martin Roberts
1,189318
answered Jul 17 at 4:53
Martin Roberts
1,189318
answered Jul 17 at 4:53
Martin Roberts
1,189318
answered Jul 17 at 4:53
Martin Roberts
1,189318
1,189318
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853761%2fcombinations-involving-distinct-sets-of-variables%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Larger generalized example: Suppose you have $M$ men and $W$ women and you wish to form a committee of size $k$ such that you have at least $m$ men and at least $w$ women. There will be $sumlimits_i=m^k-wbinomMibinomWk-i$ such possibilities. This can simplify further in certain special situations such as needing "at least one man and at least one woman" by noting vandermonde's identity giving a total of $binomM+Wk-binomMk-binomWk$, but it does not otherwise simplify nicely.
– JMoravitz
Jul 16 at 19:39
This is seen from direct application of binomial coefficients and the rules of sum and product.
– JMoravitz
Jul 16 at 19:39