Combinatorics problem, right solution?graph theory /combinatorics committee existenceDifferent Perspectives of Multinomial Theorem & PartitionsCombination with at least two people.Number of committees of size $5$ with at least $2$ women from a society with $10$ men and $12$ womenIs the assumption of the question violates itselfWhat is the correct approach for the following question?Combinatorics: How should we count lists?combinatorics select committee different jobsCombinatorics: Partnerships Problem Overcounting
C4_4 Reflection!
Sum in bash outside while read line
My professor says my digit summing code is flawed. Is he right?
Can a character dodge an attack that beats their Armor Class?
How to remind myself to lock my doors
Glacial, Magnetic and Mossy Lures; what Pokémon do they attract?
First aid scissors confiscated by Dubai airport security
Can the bass be used instead of drums?
'Kukhtarev's model' or 'THE Kukhtarev's model'?
I'm not alive, but I can be lively
Why is coffee provided during big chess events when it contains a banned substance?
Why are Starfleet vessels designed with nacelles so far away from the hull?
Can you take Bowwow out after returning him to MeowMeow?
5v home network
Is it realistic that an advanced species isn't good at war?
Short story about aliens who tried using the common cold as a weapon
Is data science mathematically interesting?
Is it reasonable to ask candidates to create a profile on Google Scholar?
What causes standard door hinges to close up to a certain amount automatically?
Did Feynman cite a fallacy about only circles having the same width in all directions as a reason for the Challenger disaster?
How to respond when insulted by a grad student in a different department?
Why are seats at the rear of a plane sometimes unavailable even though many other seats are available in the plane?
What's the most efficient way to draw this region?
Employer says he needs to delay payment by 3 months due to bureaucracy
Combinatorics problem, right solution?
graph theory /combinatorics committee existenceDifferent Perspectives of Multinomial Theorem & PartitionsCombination with at least two people.Number of committees of size $5$ with at least $2$ women from a society with $10$ men and $12$ womenIs the assumption of the question violates itselfWhat is the correct approach for the following question?Combinatorics: How should we count lists?combinatorics select committee different jobsCombinatorics: Partnerships Problem Overcounting
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;
.everyonelovesstackoverflowposition:absolute;height:1px;width:1px;opacity:0;top:0;left:0;pointer-events:none;
$begingroup$
We have $6$ lawyers, $7$ engineers and $4$ doctors. We plan on making a committee of $5$ people, and we want at least one person of each profession on board. So for the first place I choose an engineer, for the second a doctor and for the third a lawyer, leaving only $5$ laywers, $6$ engineers and $3$ doctors left.
For the remaining two places, I could have $2$ more people of a single profession. This is $binom52+binom62+binom32$ possibilities.
I could also have two people of different professions; a doctor and a laywer, $binom51binom31$; a doctor and an engineer, $binom61binom31$; or an engineer and a laywer $binom61binom51$.
This adds up to $binom52+binom62+binom32+binom51binom31+binom61binom31+binom61binom51=91$ possible committees.
I have two questions regarding my approach to the problem. Question $a)$ is the reasoning right, am I not overcounting? $b)$ Even if it is right, is there a simpler way to do this? You can see that the sum I end up with, though relatively simple, is quite long and tedious.
Thanks in advance!
combinatorics discrete-mathematics order-theory
asked Apr 25 at 15:39
LafinurLafinur
37111 bronze badges
$endgroup$
|
show 1 more comment
$begingroup$
We have $6$ lawyers, $7$ engineers and $4$ doctors. We plan on making a committee of $5$ people, and we want at least one person of each profession on board. So for the first place I choose an engineer, for the second a doctor and for the third a lawyer, leaving only $5$ laywers, $6$ engineers and $3$ doctors left.
For the remaining two places, I could have $2$ more people of a single profession. This is $binom52+binom62+binom32$ possibilities.
I could also have two people of different professions; a doctor and a laywer, $binom51binom31$; a doctor and an engineer, $binom61binom31$; or an engineer and a laywer $binom61binom51$.
This adds up to $binom52+binom62+binom32+binom51binom31+binom61binom31+binom61binom51=91$ possible committees.
I have two questions regarding my approach to the problem. Question $a)$ is the reasoning right, am I not overcounting? $b)$ Even if it is right, is there a simpler way to do this? You can see that the sum I end up with, though relatively simple, is quite long and tedious.
Thanks in advance!
combinatorics discrete-mathematics order-theory
asked Apr 25 at 15:39
LafinurLafinur
37111 bronze badges
$endgroup$
$begingroup$
I corrected it, I apologize. The result is the same though, it was just a typo.
$endgroup$
– Lafinur
Apr 25 at 15:45
1
$begingroup$
That number seems far too small. If you ignore the restriction there are $binom 175=6188$ possible combinations.
$endgroup$
– lulu
Apr 25 at 15:51
2
$begingroup$
When you say, for example, "pick a lawyer and then later possibly pick more lawyers", you're guaranteed to introduce an overcount. You might pick LawyerA first and then LawyerB or you might pick LawyerB first and then LawyerA. These are precisely the same subset of lawyers, but your counting scheme considers them to be different.
$endgroup$
– Austin Mohr
Apr 25 at 17:48
1
$begingroup$
To explain why your answer is so small... "For the first place I choose an engineer" okay, and how many options were there for which engineer takes this spot? How does this affect the total count? Similarly so for the other professions. This would give an answer of $6times 7times 4times 91 = 15288$ which as explained in previous comment is indeed overcounting. This however would be the answer to the question of how many five person teams we can make which have a designated "lead engineer" and "lead lawyer" and "lead doctor" on the team.
$endgroup$
– JMoravitz
Apr 25 at 18:52
$begingroup$
Note also that $binom52+binom62+dots=91$ is simply $binom142$, the number of ways of choosing two more people from the $(6-1)+(7-1)+(4-1)=14$ people remaining after having selected a lead lawyer, lead engineer, and lead doctor to fill out the rest of the team.
$endgroup$
– JMoravitz
Apr 25 at 18:54
|
show 1 more comment
$begingroup$
We have $6$ lawyers, $7$ engineers and $4$ doctors. We plan on making a committee of $5$ people, and we want at least one person of each profession on board. So for the first place I choose an engineer, for the second a doctor and for the third a lawyer, leaving only $5$ laywers, $6$ engineers and $3$ doctors left.
For the remaining two places, I could have $2$ more people of a single profession. This is $binom52+binom62+binom32$ possibilities.
I could also have two people of different professions; a doctor and a laywer, $binom51binom31$; a doctor and an engineer, $binom61binom31$; or an engineer and a laywer $binom61binom51$.
This adds up to $binom52+binom62+binom32+binom51binom31+binom61binom31+binom61binom51=91$ possible committees.
I have two questions regarding my approach to the problem. Question $a)$ is the reasoning right, am I not overcounting? $b)$ Even if it is right, is there a simpler way to do this? You can see that the sum I end up with, though relatively simple, is quite long and tedious.
Thanks in advance!
combinatorics discrete-mathematics order-theory
asked Apr 25 at 15:39
LafinurLafinur
37111 bronze badges
$endgroup$
We have $6$ lawyers, $7$ engineers and $4$ doctors. We plan on making a committee of $5$ people, and we want at least one person of each profession on board. So for the first place I choose an engineer, for the second a doctor and for the third a lawyer, leaving only $5$ laywers, $6$ engineers and $3$ doctors left.
For the remaining two places, I could have $2$ more people of a single profession. This is $binom52+binom62+binom32$ possibilities.
I could also have two people of different professions; a doctor and a laywer, $binom51binom31$; a doctor and an engineer, $binom61binom31$; or an engineer and a laywer $binom61binom51$.
This adds up to $binom52+binom62+binom32+binom51binom31+binom61binom31+binom61binom51=91$ possible committees.
I have two questions regarding my approach to the problem. Question $a)$ is the reasoning right, am I not overcounting? $b)$ Even if it is right, is there a simpler way to do this? You can see that the sum I end up with, though relatively simple, is quite long and tedious.
Thanks in advance!
combinatorics discrete-mathematics order-theory
combinatorics discrete-mathematics order-theory
asked Apr 25 at 15:39
LafinurLafinur
37111 bronze badges
asked Apr 25 at 15:39
LafinurLafinur
37111 bronze badges
edited Apr 25 at 16:05
Lafinur
asked Apr 25 at 15:39
LafinurLafinur
37111 bronze badges
asked Apr 25 at 15:39
LafinurLafinur
37111 bronze badges
asked Apr 25 at 15:39
LafinurLafinur
37111 bronze badges
37111 bronze badges
$begingroup$
I corrected it, I apologize. The result is the same though, it was just a typo.
$endgroup$
– Lafinur
Apr 25 at 15:45
1
$begingroup$
That number seems far too small. If you ignore the restriction there are $binom 175=6188$ possible combinations.
$endgroup$
– lulu
Apr 25 at 15:51
2
$begingroup$
When you say, for example, "pick a lawyer and then later possibly pick more lawyers", you're guaranteed to introduce an overcount. You might pick LawyerA first and then LawyerB or you might pick LawyerB first and then LawyerA. These are precisely the same subset of lawyers, but your counting scheme considers them to be different.
$endgroup$
– Austin Mohr
Apr 25 at 17:48
1
$begingroup$
To explain why your answer is so small... "For the first place I choose an engineer" okay, and how many options were there for which engineer takes this spot? How does this affect the total count? Similarly so for the other professions. This would give an answer of $6times 7times 4times 91 = 15288$ which as explained in previous comment is indeed overcounting. This however would be the answer to the question of how many five person teams we can make which have a designated "lead engineer" and "lead lawyer" and "lead doctor" on the team.
$endgroup$
– JMoravitz
Apr 25 at 18:52
$begingroup$
Note also that $binom52+binom62+dots=91$ is simply $binom142$, the number of ways of choosing two more people from the $(6-1)+(7-1)+(4-1)=14$ people remaining after having selected a lead lawyer, lead engineer, and lead doctor to fill out the rest of the team.
$endgroup$
– JMoravitz
Apr 25 at 18:54
|
show 1 more comment
$begingroup$
I corrected it, I apologize. The result is the same though, it was just a typo.
$endgroup$
– Lafinur
Apr 25 at 15:45
1
$begingroup$
That number seems far too small. If you ignore the restriction there are $binom 175=6188$ possible combinations.
$endgroup$
– lulu
Apr 25 at 15:51
2
$begingroup$
When you say, for example, "pick a lawyer and then later possibly pick more lawyers", you're guaranteed to introduce an overcount. You might pick LawyerA first and then LawyerB or you might pick LawyerB first and then LawyerA. These are precisely the same subset of lawyers, but your counting scheme considers them to be different.
$endgroup$
– Austin Mohr
Apr 25 at 17:48
1
$begingroup$
To explain why your answer is so small... "For the first place I choose an engineer" okay, and how many options were there for which engineer takes this spot? How does this affect the total count? Similarly so for the other professions. This would give an answer of $6times 7times 4times 91 = 15288$ which as explained in previous comment is indeed overcounting. This however would be the answer to the question of how many five person teams we can make which have a designated "lead engineer" and "lead lawyer" and "lead doctor" on the team.
$endgroup$
– JMoravitz
Apr 25 at 18:52
$begingroup$
Note also that $binom52+binom62+dots=91$ is simply $binom142$, the number of ways of choosing two more people from the $(6-1)+(7-1)+(4-1)=14$ people remaining after having selected a lead lawyer, lead engineer, and lead doctor to fill out the rest of the team.
$endgroup$
– JMoravitz
Apr 25 at 18:54
$begingroup$
I corrected it, I apologize. The result is the same though, it was just a typo.
$endgroup$
– Lafinur
Apr 25 at 15:45
$begingroup$
I corrected it, I apologize. The result is the same though, it was just a typo.
$endgroup$
– Lafinur
Apr 25 at 15:45
1
1
$begingroup$
That number seems far too small. If you ignore the restriction there are $binom 175=6188$ possible combinations.
$endgroup$
– lulu
Apr 25 at 15:51
$begingroup$
That number seems far too small. If you ignore the restriction there are $binom 175=6188$ possible combinations.
$endgroup$
– lulu
Apr 25 at 15:51
2
2
$begingroup$
When you say, for example, "pick a lawyer and then later possibly pick more lawyers", you're guaranteed to introduce an overcount. You might pick LawyerA first and then LawyerB or you might pick LawyerB first and then LawyerA. These are precisely the same subset of lawyers, but your counting scheme considers them to be different.
$endgroup$
– Austin Mohr
Apr 25 at 17:48
$begingroup$
When you say, for example, "pick a lawyer and then later possibly pick more lawyers", you're guaranteed to introduce an overcount. You might pick LawyerA first and then LawyerB or you might pick LawyerB first and then LawyerA. These are precisely the same subset of lawyers, but your counting scheme considers them to be different.
$endgroup$
– Austin Mohr
Apr 25 at 17:48
1
1
$begingroup$
To explain why your answer is so small... "For the first place I choose an engineer" okay, and how many options were there for which engineer takes this spot? How does this affect the total count? Similarly so for the other professions. This would give an answer of $6times 7times 4times 91 = 15288$ which as explained in previous comment is indeed overcounting. This however would be the answer to the question of how many five person teams we can make which have a designated "lead engineer" and "lead lawyer" and "lead doctor" on the team.
$endgroup$
– JMoravitz
Apr 25 at 18:52
$begingroup$
To explain why your answer is so small... "For the first place I choose an engineer" okay, and how many options were there for which engineer takes this spot? How does this affect the total count? Similarly so for the other professions. This would give an answer of $6times 7times 4times 91 = 15288$ which as explained in previous comment is indeed overcounting. This however would be the answer to the question of how many five person teams we can make which have a designated "lead engineer" and "lead lawyer" and "lead doctor" on the team.
$endgroup$
– JMoravitz
Apr 25 at 18:52
$begingroup$
Note also that $binom52+binom62+dots=91$ is simply $binom142$, the number of ways of choosing two more people from the $(6-1)+(7-1)+(4-1)=14$ people remaining after having selected a lead lawyer, lead engineer, and lead doctor to fill out the rest of the team.
$endgroup$
– JMoravitz
Apr 25 at 18:54
$begingroup$
Note also that $binom52+binom62+dots=91$ is simply $binom142$, the number of ways of choosing two more people from the $(6-1)+(7-1)+(4-1)=14$ people remaining after having selected a lead lawyer, lead engineer, and lead doctor to fill out the rest of the team.
$endgroup$
– JMoravitz
Apr 25 at 18:54
|
show 1 more comment
5 Answers
5
active
oldest
votes
$begingroup$
I think Inclusion Exclusion is an easier approach.
If we ignore the restriction, there are $binom 175$ ways to choose the group.
We then exclude the choices which miss one specified profession. That's an exclusion of $$binom 115+binom 105+binom 135$$.
We then add back the cases in which all the people come from one profession. Thus we add back $$binom 65+binom 75$$
Thus the answer is $$binom 175-left(binom 115+binom 105+binom 135right)+left(binom 65+binom 75right)=boxed 4214$$
answered Apr 25 at 16:08
lulululu
47.6k3 gold badges53 silver badges87 bronze badges
$endgroup$
add a comment
|
$begingroup$
I think it is easiest to use the principle of inclusion exclusion. Start with all $binom175$ committees, ignoring the condition that each profession must appear. Then, for each profession, subtract the bad committees where that profession does not appear. So, subtract the $binom135$ committees with no doctor, the $binom115$ committees with no lawyer, and the $binom105$ committees with no engineer. But then committees which are missing two particular professions have now been doubly subtracted, so these must be added back in to correct for this. For example, the $binom75$ committees with no doctor or lawyer.
The result is
$$
binom175-binom135-binom115-binom105+ binom75 +binom65
$$
answered Apr 25 at 16:10
Mike EarnestMike Earnest
32k2 gold badges28 silver badges59 bronze badges
$endgroup$
add a comment
|
$begingroup$
Let $A=(l,e,d)in1,2,3,4,5,6times1,2,3,4,5,6,7times1,2,3,4mid l+e+d=5$
Then to be found is $$sum_(l,e,d)in Abinom6lbinom7ebinom4d$$
Under the sketched conditions for equation $5=l+e+d$ we have the following possibilities:
- $5=3+1+1$
- $5=2+2+1$
- $5=2+1+2$
- $5=1+3+1$
- $5=1+2+2$
- $5=1+1+3$
This provides you a view on set $A$ and shows that the summation has $6$ terms.
answered Apr 25 at 16:01
drhabdrhab
115k5 gold badges51 silver badges143 bronze badges
$endgroup$
add a comment
|
$begingroup$
There are 6 types of possible committees:
beginarray
hline
3&1&1 \
hline
1&3&1 \
hline
1&1&3 \
hline
2&2&1 \
hline
2&1&2 \
hline
1&2&2 \
hline
endarray
For each type of committee, it is necessary to calculate the different groups of people that compose it:
beginarray
hline
3&1&1& 6choose37choose14choose1= 20cdot7cdot4 = 560 \
hline
1&3&1& 6choose17choose34choose1= 6cdot35cdot4 = 840 \
hline
1&1&3& 6choose17choose14choose3= 6cdot7cdot4 = 168 \
hline
2&2&1& 6choose27choose24choose1= 15cdot21cdot4 = 1260 \
hline
2&1&2& 6choose27choose14choose2= 15cdot7cdot6 = 630 \
hline
1&2&2& 6choose17choose24choose2= 6cdot21cdot6 = 756 \
hline
endarray
Adding 6 gives a total of different committees:
$$ 560+840+168+1260+630+756 = 4214 $$
answered Apr 25 at 16:30
Angel MorenoAngel Moreno
5722 silver badges5 bronze badges
$endgroup$
add a comment
|
$begingroup$
For groups of $6, 7$, and $4$ distinct types of members, would the counting be easier by counting all possible committees while ignoring the constraint, then subtracting the non-valid committees?
$$binom6 + 7 + 45 - left[ binom6+75+binom7+45+ binom6+45 right]$$
Non-valid committees are those which entirely omit one of the types of members.
(Ah: This doesn't work: The subtracted count is too high, as it duplicates non-valid committees. Trying again ...
$$binom6+7+45-
left[
left[ binom6+75 - left[binom65+binom75right] right] +
left[ binom7+45 - left[binom75+binom45right] right] +
left[ binom6+45 - left[binom65+binom45right] right]
right] -
left[ binom65 + binom75 + binom45 right]$$
The number of committees of five members, minus the number of committees with exactly two types of members, minus the number of committees with exactly one type of member.
For two given types of members, committees with exactly two types of members are all committees of those two types of members, minus committees of only one of the types of members, minus committees of only the other type of members.
To show the complete expression, I've left the terms which evaluate to 0, and haven't simplified.
answered Apr 25 at 18:38
Thomas BitontiThomas Bitonti
1013 bronze badges
$endgroup$
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3202071%2fcombinatorics-problem-right-solution%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I think Inclusion Exclusion is an easier approach.
If we ignore the restriction, there are $binom 175$ ways to choose the group.
We then exclude the choices which miss one specified profession. That's an exclusion of $$binom 115+binom 105+binom 135$$.
We then add back the cases in which all the people come from one profession. Thus we add back $$binom 65+binom 75$$
Thus the answer is $$binom 175-left(binom 115+binom 105+binom 135right)+left(binom 65+binom 75right)=boxed 4214$$
answered Apr 25 at 16:08
lulululu
47.6k3 gold badges53 silver badges87 bronze badges
$endgroup$
add a comment
|
$begingroup$
I think Inclusion Exclusion is an easier approach.
If we ignore the restriction, there are $binom 175$ ways to choose the group.
We then exclude the choices which miss one specified profession. That's an exclusion of $$binom 115+binom 105+binom 135$$.
We then add back the cases in which all the people come from one profession. Thus we add back $$binom 65+binom 75$$
Thus the answer is $$binom 175-left(binom 115+binom 105+binom 135right)+left(binom 65+binom 75right)=boxed 4214$$
answered Apr 25 at 16:08
lulululu
47.6k3 gold badges53 silver badges87 bronze badges
$endgroup$
add a comment
|
$begingroup$
I think Inclusion Exclusion is an easier approach.
If we ignore the restriction, there are $binom 175$ ways to choose the group.
We then exclude the choices which miss one specified profession. That's an exclusion of $$binom 115+binom 105+binom 135$$.
We then add back the cases in which all the people come from one profession. Thus we add back $$binom 65+binom 75$$
Thus the answer is $$binom 175-left(binom 115+binom 105+binom 135right)+left(binom 65+binom 75right)=boxed 4214$$
answered Apr 25 at 16:08
lulululu
47.6k3 gold badges53 silver badges87 bronze badges
$endgroup$
I think Inclusion Exclusion is an easier approach.
If we ignore the restriction, there are $binom 175$ ways to choose the group.
We then exclude the choices which miss one specified profession. That's an exclusion of $$binom 115+binom 105+binom 135$$.
We then add back the cases in which all the people come from one profession. Thus we add back $$binom 65+binom 75$$
Thus the answer is $$binom 175-left(binom 115+binom 105+binom 135right)+left(binom 65+binom 75right)=boxed 4214$$
answered Apr 25 at 16:08
lulululu
47.6k3 gold badges53 silver badges87 bronze badges
answered Apr 25 at 16:08
lulululu
47.6k3 gold badges53 silver badges87 bronze badges
answered Apr 25 at 16:08
lulululu
47.6k3 gold badges53 silver badges87 bronze badges
answered Apr 25 at 16:08
lulululu
47.6k3 gold badges53 silver badges87 bronze badges
47.6k3 gold badges53 silver badges87 bronze badges
add a comment
|
add a comment
|
$begingroup$
I think it is easiest to use the principle of inclusion exclusion. Start with all $binom175$ committees, ignoring the condition that each profession must appear. Then, for each profession, subtract the bad committees where that profession does not appear. So, subtract the $binom135$ committees with no doctor, the $binom115$ committees with no lawyer, and the $binom105$ committees with no engineer. But then committees which are missing two particular professions have now been doubly subtracted, so these must be added back in to correct for this. For example, the $binom75$ committees with no doctor or lawyer.
The result is
$$
binom175-binom135-binom115-binom105+ binom75 +binom65
$$
answered Apr 25 at 16:10
Mike EarnestMike Earnest
32k2 gold badges28 silver badges59 bronze badges
$endgroup$
add a comment
|
$begingroup$
I think it is easiest to use the principle of inclusion exclusion. Start with all $binom175$ committees, ignoring the condition that each profession must appear. Then, for each profession, subtract the bad committees where that profession does not appear. So, subtract the $binom135$ committees with no doctor, the $binom115$ committees with no lawyer, and the $binom105$ committees with no engineer. But then committees which are missing two particular professions have now been doubly subtracted, so these must be added back in to correct for this. For example, the $binom75$ committees with no doctor or lawyer.
The result is
$$
binom175-binom135-binom115-binom105+ binom75 +binom65
$$
answered Apr 25 at 16:10
Mike EarnestMike Earnest
32k2 gold badges28 silver badges59 bronze badges
$endgroup$
add a comment
|
$begingroup$
I think it is easiest to use the principle of inclusion exclusion. Start with all $binom175$ committees, ignoring the condition that each profession must appear. Then, for each profession, subtract the bad committees where that profession does not appear. So, subtract the $binom135$ committees with no doctor, the $binom115$ committees with no lawyer, and the $binom105$ committees with no engineer. But then committees which are missing two particular professions have now been doubly subtracted, so these must be added back in to correct for this. For example, the $binom75$ committees with no doctor or lawyer.
The result is
$$
binom175-binom135-binom115-binom105+ binom75 +binom65
$$
answered Apr 25 at 16:10
Mike EarnestMike Earnest
32k2 gold badges28 silver badges59 bronze badges
$endgroup$
I think it is easiest to use the principle of inclusion exclusion. Start with all $binom175$ committees, ignoring the condition that each profession must appear. Then, for each profession, subtract the bad committees where that profession does not appear. So, subtract the $binom135$ committees with no doctor, the $binom115$ committees with no lawyer, and the $binom105$ committees with no engineer. But then committees which are missing two particular professions have now been doubly subtracted, so these must be added back in to correct for this. For example, the $binom75$ committees with no doctor or lawyer.
The result is
$$
binom175-binom135-binom115-binom105+ binom75 +binom65
$$
answered Apr 25 at 16:10
Mike EarnestMike Earnest
32k2 gold badges28 silver badges59 bronze badges
answered Apr 25 at 16:10
Mike EarnestMike Earnest
32k2 gold badges28 silver badges59 bronze badges
answered Apr 25 at 16:10
Mike EarnestMike Earnest
32k2 gold badges28 silver badges59 bronze badges
answered Apr 25 at 16:10
Mike EarnestMike Earnest
32k2 gold badges28 silver badges59 bronze badges
32k2 gold badges28 silver badges59 bronze badges
add a comment
|
add a comment
|
$begingroup$
Let $A=(l,e,d)in1,2,3,4,5,6times1,2,3,4,5,6,7times1,2,3,4mid l+e+d=5$
Then to be found is $$sum_(l,e,d)in Abinom6lbinom7ebinom4d$$
Under the sketched conditions for equation $5=l+e+d$ we have the following possibilities:
- $5=3+1+1$
- $5=2+2+1$
- $5=2+1+2$
- $5=1+3+1$
- $5=1+2+2$
- $5=1+1+3$
This provides you a view on set $A$ and shows that the summation has $6$ terms.
answered Apr 25 at 16:01
drhabdrhab
115k5 gold badges51 silver badges143 bronze badges
$endgroup$
add a comment
|
$begingroup$
Let $A=(l,e,d)in1,2,3,4,5,6times1,2,3,4,5,6,7times1,2,3,4mid l+e+d=5$
Then to be found is $$sum_(l,e,d)in Abinom6lbinom7ebinom4d$$
Under the sketched conditions for equation $5=l+e+d$ we have the following possibilities:
- $5=3+1+1$
- $5=2+2+1$
- $5=2+1+2$
- $5=1+3+1$
- $5=1+2+2$
- $5=1+1+3$
This provides you a view on set $A$ and shows that the summation has $6$ terms.
answered Apr 25 at 16:01
drhabdrhab
115k5 gold badges51 silver badges143 bronze badges
$endgroup$
add a comment
|
$begingroup$
Let $A=(l,e,d)in1,2,3,4,5,6times1,2,3,4,5,6,7times1,2,3,4mid l+e+d=5$
Then to be found is $$sum_(l,e,d)in Abinom6lbinom7ebinom4d$$
Under the sketched conditions for equation $5=l+e+d$ we have the following possibilities:
- $5=3+1+1$
- $5=2+2+1$
- $5=2+1+2$
- $5=1+3+1$
- $5=1+2+2$
- $5=1+1+3$
This provides you a view on set $A$ and shows that the summation has $6$ terms.
answered Apr 25 at 16:01
drhabdrhab
115k5 gold badges51 silver badges143 bronze badges
$endgroup$
Let $A=(l,e,d)in1,2,3,4,5,6times1,2,3,4,5,6,7times1,2,3,4mid l+e+d=5$
Then to be found is $$sum_(l,e,d)in Abinom6lbinom7ebinom4d$$
Under the sketched conditions for equation $5=l+e+d$ we have the following possibilities:
- $5=3+1+1$
- $5=2+2+1$
- $5=2+1+2$
- $5=1+3+1$
- $5=1+2+2$
- $5=1+1+3$
This provides you a view on set $A$ and shows that the summation has $6$ terms.
answered Apr 25 at 16:01
drhabdrhab
115k5 gold badges51 silver badges143 bronze badges
edited Apr 25 at 16:09
answered Apr 25 at 16:01
drhabdrhab
115k5 gold badges51 silver badges143 bronze badges
answered Apr 25 at 16:01
drhabdrhab
115k5 gold badges51 silver badges143 bronze badges
answered Apr 25 at 16:01
drhabdrhab
115k5 gold badges51 silver badges143 bronze badges
115k5 gold badges51 silver badges143 bronze badges
add a comment
|
add a comment
|
$begingroup$
There are 6 types of possible committees:
beginarray
hline
3&1&1 \
hline
1&3&1 \
hline
1&1&3 \
hline
2&2&1 \
hline
2&1&2 \
hline
1&2&2 \
hline
endarray
For each type of committee, it is necessary to calculate the different groups of people that compose it:
beginarray
hline
3&1&1& 6choose37choose14choose1= 20cdot7cdot4 = 560 \
hline
1&3&1& 6choose17choose34choose1= 6cdot35cdot4 = 840 \
hline
1&1&3& 6choose17choose14choose3= 6cdot7cdot4 = 168 \
hline
2&2&1& 6choose27choose24choose1= 15cdot21cdot4 = 1260 \
hline
2&1&2& 6choose27choose14choose2= 15cdot7cdot6 = 630 \
hline
1&2&2& 6choose17choose24choose2= 6cdot21cdot6 = 756 \
hline
endarray
Adding 6 gives a total of different committees:
$$ 560+840+168+1260+630+756 = 4214 $$
answered Apr 25 at 16:30
Angel MorenoAngel Moreno
5722 silver badges5 bronze badges
$endgroup$
add a comment
|
$begingroup$
There are 6 types of possible committees:
beginarray
hline
3&1&1 \
hline
1&3&1 \
hline
1&1&3 \
hline
2&2&1 \
hline
2&1&2 \
hline
1&2&2 \
hline
endarray
For each type of committee, it is necessary to calculate the different groups of people that compose it:
beginarray
hline
3&1&1& 6choose37choose14choose1= 20cdot7cdot4 = 560 \
hline
1&3&1& 6choose17choose34choose1= 6cdot35cdot4 = 840 \
hline
1&1&3& 6choose17choose14choose3= 6cdot7cdot4 = 168 \
hline
2&2&1& 6choose27choose24choose1= 15cdot21cdot4 = 1260 \
hline
2&1&2& 6choose27choose14choose2= 15cdot7cdot6 = 630 \
hline
1&2&2& 6choose17choose24choose2= 6cdot21cdot6 = 756 \
hline
endarray
Adding 6 gives a total of different committees:
$$ 560+840+168+1260+630+756 = 4214 $$
answered Apr 25 at 16:30
Angel MorenoAngel Moreno
5722 silver badges5 bronze badges
$endgroup$
add a comment
|
$begingroup$
There are 6 types of possible committees:
beginarray
hline
3&1&1 \
hline
1&3&1 \
hline
1&1&3 \
hline
2&2&1 \
hline
2&1&2 \
hline
1&2&2 \
hline
endarray
For each type of committee, it is necessary to calculate the different groups of people that compose it:
beginarray
hline
3&1&1& 6choose37choose14choose1= 20cdot7cdot4 = 560 \
hline
1&3&1& 6choose17choose34choose1= 6cdot35cdot4 = 840 \
hline
1&1&3& 6choose17choose14choose3= 6cdot7cdot4 = 168 \
hline
2&2&1& 6choose27choose24choose1= 15cdot21cdot4 = 1260 \
hline
2&1&2& 6choose27choose14choose2= 15cdot7cdot6 = 630 \
hline
1&2&2& 6choose17choose24choose2= 6cdot21cdot6 = 756 \
hline
endarray
Adding 6 gives a total of different committees:
$$ 560+840+168+1260+630+756 = 4214 $$
answered Apr 25 at 16:30
Angel MorenoAngel Moreno
5722 silver badges5 bronze badges
$endgroup$
There are 6 types of possible committees:
beginarray
hline
3&1&1 \
hline
1&3&1 \
hline
1&1&3 \
hline
2&2&1 \
hline
2&1&2 \
hline
1&2&2 \
hline
endarray
For each type of committee, it is necessary to calculate the different groups of people that compose it:
beginarray
hline
3&1&1& 6choose37choose14choose1= 20cdot7cdot4 = 560 \
hline
1&3&1& 6choose17choose34choose1= 6cdot35cdot4 = 840 \
hline
1&1&3& 6choose17choose14choose3= 6cdot7cdot4 = 168 \
hline
2&2&1& 6choose27choose24choose1= 15cdot21cdot4 = 1260 \
hline
2&1&2& 6choose27choose14choose2= 15cdot7cdot6 = 630 \
hline
1&2&2& 6choose17choose24choose2= 6cdot21cdot6 = 756 \
hline
endarray
Adding 6 gives a total of different committees:
$$ 560+840+168+1260+630+756 = 4214 $$
answered Apr 25 at 16:30
Angel MorenoAngel Moreno
5722 silver badges5 bronze badges
answered Apr 25 at 16:30
Angel MorenoAngel Moreno
5722 silver badges5 bronze badges
answered Apr 25 at 16:30
Angel MorenoAngel Moreno
5722 silver badges5 bronze badges
answered Apr 25 at 16:30
Angel MorenoAngel Moreno
5722 silver badges5 bronze badges
5722 silver badges5 bronze badges
add a comment
|
add a comment
|
$begingroup$
For groups of $6, 7$, and $4$ distinct types of members, would the counting be easier by counting all possible committees while ignoring the constraint, then subtracting the non-valid committees?
$$binom6 + 7 + 45 - left[ binom6+75+binom7+45+ binom6+45 right]$$
Non-valid committees are those which entirely omit one of the types of members.
(Ah: This doesn't work: The subtracted count is too high, as it duplicates non-valid committees. Trying again ...
$$binom6+7+45-
left[
left[ binom6+75 - left[binom65+binom75right] right] +
left[ binom7+45 - left[binom75+binom45right] right] +
left[ binom6+45 - left[binom65+binom45right] right]
right] -
left[ binom65 + binom75 + binom45 right]$$
The number of committees of five members, minus the number of committees with exactly two types of members, minus the number of committees with exactly one type of member.
For two given types of members, committees with exactly two types of members are all committees of those two types of members, minus committees of only one of the types of members, minus committees of only the other type of members.
To show the complete expression, I've left the terms which evaluate to 0, and haven't simplified.
answered Apr 25 at 18:38
Thomas BitontiThomas Bitonti
1013 bronze badges
$endgroup$
add a comment
|
$begingroup$
For groups of $6, 7$, and $4$ distinct types of members, would the counting be easier by counting all possible committees while ignoring the constraint, then subtracting the non-valid committees?
$$binom6 + 7 + 45 - left[ binom6+75+binom7+45+ binom6+45 right]$$
Non-valid committees are those which entirely omit one of the types of members.
(Ah: This doesn't work: The subtracted count is too high, as it duplicates non-valid committees. Trying again ...
$$binom6+7+45-
left[
left[ binom6+75 - left[binom65+binom75right] right] +
left[ binom7+45 - left[binom75+binom45right] right] +
left[ binom6+45 - left[binom65+binom45right] right]
right] -
left[ binom65 + binom75 + binom45 right]$$
The number of committees of five members, minus the number of committees with exactly two types of members, minus the number of committees with exactly one type of member.
For two given types of members, committees with exactly two types of members are all committees of those two types of members, minus committees of only one of the types of members, minus committees of only the other type of members.
To show the complete expression, I've left the terms which evaluate to 0, and haven't simplified.
answered Apr 25 at 18:38
Thomas BitontiThomas Bitonti
1013 bronze badges
$endgroup$
add a comment
|
$begingroup$
For groups of $6, 7$, and $4$ distinct types of members, would the counting be easier by counting all possible committees while ignoring the constraint, then subtracting the non-valid committees?
$$binom6 + 7 + 45 - left[ binom6+75+binom7+45+ binom6+45 right]$$
Non-valid committees are those which entirely omit one of the types of members.
(Ah: This doesn't work: The subtracted count is too high, as it duplicates non-valid committees. Trying again ...
$$binom6+7+45-
left[
left[ binom6+75 - left[binom65+binom75right] right] +
left[ binom7+45 - left[binom75+binom45right] right] +
left[ binom6+45 - left[binom65+binom45right] right]
right] -
left[ binom65 + binom75 + binom45 right]$$
The number of committees of five members, minus the number of committees with exactly two types of members, minus the number of committees with exactly one type of member.
For two given types of members, committees with exactly two types of members are all committees of those two types of members, minus committees of only one of the types of members, minus committees of only the other type of members.
To show the complete expression, I've left the terms which evaluate to 0, and haven't simplified.
answered Apr 25 at 18:38
Thomas BitontiThomas Bitonti
1013 bronze badges
$endgroup$
For groups of $6, 7$, and $4$ distinct types of members, would the counting be easier by counting all possible committees while ignoring the constraint, then subtracting the non-valid committees?
$$binom6 + 7 + 45 - left[ binom6+75+binom7+45+ binom6+45 right]$$
Non-valid committees are those which entirely omit one of the types of members.
(Ah: This doesn't work: The subtracted count is too high, as it duplicates non-valid committees. Trying again ...
$$binom6+7+45-
left[
left[ binom6+75 - left[binom65+binom75right] right] +
left[ binom7+45 - left[binom75+binom45right] right] +
left[ binom6+45 - left[binom65+binom45right] right]
right] -
left[ binom65 + binom75 + binom45 right]$$
The number of committees of five members, minus the number of committees with exactly two types of members, minus the number of committees with exactly one type of member.
For two given types of members, committees with exactly two types of members are all committees of those two types of members, minus committees of only one of the types of members, minus committees of only the other type of members.
To show the complete expression, I've left the terms which evaluate to 0, and haven't simplified.
answered Apr 25 at 18:38
Thomas BitontiThomas Bitonti
1013 bronze badges
edited Apr 25 at 19:05
answered Apr 25 at 18:38
Thomas BitontiThomas Bitonti
1013 bronze badges
answered Apr 25 at 18:38
Thomas BitontiThomas Bitonti
1013 bronze badges
answered Apr 25 at 18:38
Thomas BitontiThomas Bitonti
1013 bronze badges
1013 bronze badges
add a comment
|
add a comment
|
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3202071%2fcombinatorics-problem-right-solution%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I corrected it, I apologize. The result is the same though, it was just a typo.
$endgroup$
– Lafinur
Apr 25 at 15:45
1
$begingroup$
That number seems far too small. If you ignore the restriction there are $binom 175=6188$ possible combinations.
$endgroup$
– lulu
Apr 25 at 15:51
2
$begingroup$
When you say, for example, "pick a lawyer and then later possibly pick more lawyers", you're guaranteed to introduce an overcount. You might pick LawyerA first and then LawyerB or you might pick LawyerB first and then LawyerA. These are precisely the same subset of lawyers, but your counting scheme considers them to be different.
$endgroup$
– Austin Mohr
Apr 25 at 17:48
1
$begingroup$
To explain why your answer is so small... "For the first place I choose an engineer" okay, and how many options were there for which engineer takes this spot? How does this affect the total count? Similarly so for the other professions. This would give an answer of $6times 7times 4times 91 = 15288$ which as explained in previous comment is indeed overcounting. This however would be the answer to the question of how many five person teams we can make which have a designated "lead engineer" and "lead lawyer" and "lead doctor" on the team.
$endgroup$
– JMoravitz
Apr 25 at 18:52
$begingroup$
Note also that $binom52+binom62+dots=91$ is simply $binom142$, the number of ways of choosing two more people from the $(6-1)+(7-1)+(4-1)=14$ people remaining after having selected a lead lawyer, lead engineer, and lead doctor to fill out the rest of the team.
$endgroup$
– JMoravitz
Apr 25 at 18:54