how many ways can we choose a committee of 6 animals if there must be at least 3 pigs?
Can anyone help me this problem?
In a group of $2$ cats, $3$ dogs, and $10$ pigs, in how many ways can we choose a committee of $6$ animals if there must be at least $3$ pigs? Assume each kind of animal is identical.
combinatorics combinations generating-functions
add a comment |
Can anyone help me this problem?
In a group of $2$ cats, $3$ dogs, and $10$ pigs, in how many ways can we choose a committee of $6$ animals if there must be at least $3$ pigs? Assume each kind of animal is identical.
combinatorics combinations generating-functions
Are each animal of a kind considered identical or do they all have different names and are considered distinct? If considered identical, consider using stars and bars coupled with inclusion-exclusion. If considered distinct, recommend just approaching directly by cases.
– JMoravitz
Mar 2 '17 at 4:06
add a comment |
Can anyone help me this problem?
In a group of $2$ cats, $3$ dogs, and $10$ pigs, in how many ways can we choose a committee of $6$ animals if there must be at least $3$ pigs? Assume each kind of animal is identical.
combinatorics combinations generating-functions
Can anyone help me this problem?
In a group of $2$ cats, $3$ dogs, and $10$ pigs, in how many ways can we choose a committee of $6$ animals if there must be at least $3$ pigs? Assume each kind of animal is identical.
combinatorics combinations generating-functions
combinatorics combinations generating-functions
edited Mar 2 '17 at 4:25
asked Mar 2 '17 at 4:02
learning
9151418
9151418
Are each animal of a kind considered identical or do they all have different names and are considered distinct? If considered identical, consider using stars and bars coupled with inclusion-exclusion. If considered distinct, recommend just approaching directly by cases.
– JMoravitz
Mar 2 '17 at 4:06
add a comment |
Are each animal of a kind considered identical or do they all have different names and are considered distinct? If considered identical, consider using stars and bars coupled with inclusion-exclusion. If considered distinct, recommend just approaching directly by cases.
– JMoravitz
Mar 2 '17 at 4:06
Are each animal of a kind considered identical or do they all have different names and are considered distinct? If considered identical, consider using stars and bars coupled with inclusion-exclusion. If considered distinct, recommend just approaching directly by cases.
– JMoravitz
Mar 2 '17 at 4:06
Are each animal of a kind considered identical or do they all have different names and are considered distinct? If considered identical, consider using stars and bars coupled with inclusion-exclusion. If considered distinct, recommend just approaching directly by cases.
– JMoravitz
Mar 2 '17 at 4:06
add a comment |
2 Answers
2
active
oldest
votes
This is equivalent to the number of integral solutions to the system
$$begin{cases} x_1+x_2+x_3=6\0leq x_1leq 2\ 0leq x_2leq 3\ 3leq x_3color{grey}{leq 10}end{cases}$$
The upper limit on $x_3$ is irrelevant since it is impossible for us to select more pigs than we have in our group of six.
Let $S$ be the set of solutions where we don't care about any of the upper bounds. Let $A_1$ be the set of solutions where (at the very least) the first upperbound condition is violated (and possibly the second one too). Let $A_2$ be the set of solutions where the second upperbound condition is violated.
We wish to count $|Ssetminus (A_1cup A_2)| = |S|-|A_1|-|A_2|+|A_1cap A_2|$
What does it mean for an upper bound condition? Well, $A_1$ is when the condition $x_1leq 2$ is false, i.e. $x_1>2$ i.e. $3leq x_1$. That is to say $|A_1|$ is the number of solutions to
$$begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$$
Remember to continue calculations that the number of solutions to the system
$$begin{cases}x_1+x_2+dots+x_r=n\ 0leq x_i~~forall iend{cases}$$
is seen to be $binom{n+r-1}{r-1}$ via stars and bars.
But how do we calculate $|A_1|, |A_2| $ and $|A_1|cap|A_2|$
– Osheen Sachdev
Mar 2 '17 at 5:48
1
@OsheenSachdev $|A_1|$ and $|A_2|$ are numbers and cannot be intersected. You mean $|A_1cap A_2|$. Put the system into the form I give at the bottom where the lower bound is zero by making a change of variables. E.g. For $A_1$ it was $begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$. Setting $x_1-3=y_1$, $x_2=y_2$ and $x_3-3=y_3$ we have this system is equivalent to $begin{cases}y_1+y_2+y_3=0\ 0leq y_1\ 0leq y_2\ 0leq y_3end{cases}$, now apply the given formula.
– JMoravitz
Mar 2 '17 at 5:51
Okay got it...thank you so much!
– Osheen Sachdev
Mar 2 '17 at 5:52
add a comment |
Three seats on the committee are for pigs only, and the other three are at-large. Let's count the ways to fill the at-large seats, since there's exactly one way to fill the reserved seats. Each way corresponds to a monomial of degree $3$ in this product:
$$ (1 + c + c^2)(1 + d + d^2 + d^3)(1 + p + p^2 + p^3) enspace, $$
where $c^id^jp^k$ represents a committee with $i$ cats, $j$ dogs, and $k$ pigs. There are nine such terms with non-negative exponents and $i leq 2$:
$$ p^3, dp^2, d^2p, d^3, cp^2, cdp, cd^2, c^2p, c^2d enspace. $$
Hence there are nine ways to form the committee.
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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/3.0/"u003ecc by-sa 3.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%2f2168018%2fhow-many-ways-can-we-choose-a-committee-of-6-animals-if-there-must-be-at-least-3%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
This is equivalent to the number of integral solutions to the system
$$begin{cases} x_1+x_2+x_3=6\0leq x_1leq 2\ 0leq x_2leq 3\ 3leq x_3color{grey}{leq 10}end{cases}$$
The upper limit on $x_3$ is irrelevant since it is impossible for us to select more pigs than we have in our group of six.
Let $S$ be the set of solutions where we don't care about any of the upper bounds. Let $A_1$ be the set of solutions where (at the very least) the first upperbound condition is violated (and possibly the second one too). Let $A_2$ be the set of solutions where the second upperbound condition is violated.
We wish to count $|Ssetminus (A_1cup A_2)| = |S|-|A_1|-|A_2|+|A_1cap A_2|$
What does it mean for an upper bound condition? Well, $A_1$ is when the condition $x_1leq 2$ is false, i.e. $x_1>2$ i.e. $3leq x_1$. That is to say $|A_1|$ is the number of solutions to
$$begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$$
Remember to continue calculations that the number of solutions to the system
$$begin{cases}x_1+x_2+dots+x_r=n\ 0leq x_i~~forall iend{cases}$$
is seen to be $binom{n+r-1}{r-1}$ via stars and bars.
But how do we calculate $|A_1|, |A_2| $ and $|A_1|cap|A_2|$
– Osheen Sachdev
Mar 2 '17 at 5:48
1
@OsheenSachdev $|A_1|$ and $|A_2|$ are numbers and cannot be intersected. You mean $|A_1cap A_2|$. Put the system into the form I give at the bottom where the lower bound is zero by making a change of variables. E.g. For $A_1$ it was $begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$. Setting $x_1-3=y_1$, $x_2=y_2$ and $x_3-3=y_3$ we have this system is equivalent to $begin{cases}y_1+y_2+y_3=0\ 0leq y_1\ 0leq y_2\ 0leq y_3end{cases}$, now apply the given formula.
– JMoravitz
Mar 2 '17 at 5:51
Okay got it...thank you so much!
– Osheen Sachdev
Mar 2 '17 at 5:52
add a comment |
This is equivalent to the number of integral solutions to the system
$$begin{cases} x_1+x_2+x_3=6\0leq x_1leq 2\ 0leq x_2leq 3\ 3leq x_3color{grey}{leq 10}end{cases}$$
The upper limit on $x_3$ is irrelevant since it is impossible for us to select more pigs than we have in our group of six.
Let $S$ be the set of solutions where we don't care about any of the upper bounds. Let $A_1$ be the set of solutions where (at the very least) the first upperbound condition is violated (and possibly the second one too). Let $A_2$ be the set of solutions where the second upperbound condition is violated.
We wish to count $|Ssetminus (A_1cup A_2)| = |S|-|A_1|-|A_2|+|A_1cap A_2|$
What does it mean for an upper bound condition? Well, $A_1$ is when the condition $x_1leq 2$ is false, i.e. $x_1>2$ i.e. $3leq x_1$. That is to say $|A_1|$ is the number of solutions to
$$begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$$
Remember to continue calculations that the number of solutions to the system
$$begin{cases}x_1+x_2+dots+x_r=n\ 0leq x_i~~forall iend{cases}$$
is seen to be $binom{n+r-1}{r-1}$ via stars and bars.
But how do we calculate $|A_1|, |A_2| $ and $|A_1|cap|A_2|$
– Osheen Sachdev
Mar 2 '17 at 5:48
1
@OsheenSachdev $|A_1|$ and $|A_2|$ are numbers and cannot be intersected. You mean $|A_1cap A_2|$. Put the system into the form I give at the bottom where the lower bound is zero by making a change of variables. E.g. For $A_1$ it was $begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$. Setting $x_1-3=y_1$, $x_2=y_2$ and $x_3-3=y_3$ we have this system is equivalent to $begin{cases}y_1+y_2+y_3=0\ 0leq y_1\ 0leq y_2\ 0leq y_3end{cases}$, now apply the given formula.
– JMoravitz
Mar 2 '17 at 5:51
Okay got it...thank you so much!
– Osheen Sachdev
Mar 2 '17 at 5:52
add a comment |
This is equivalent to the number of integral solutions to the system
$$begin{cases} x_1+x_2+x_3=6\0leq x_1leq 2\ 0leq x_2leq 3\ 3leq x_3color{grey}{leq 10}end{cases}$$
The upper limit on $x_3$ is irrelevant since it is impossible for us to select more pigs than we have in our group of six.
Let $S$ be the set of solutions where we don't care about any of the upper bounds. Let $A_1$ be the set of solutions where (at the very least) the first upperbound condition is violated (and possibly the second one too). Let $A_2$ be the set of solutions where the second upperbound condition is violated.
We wish to count $|Ssetminus (A_1cup A_2)| = |S|-|A_1|-|A_2|+|A_1cap A_2|$
What does it mean for an upper bound condition? Well, $A_1$ is when the condition $x_1leq 2$ is false, i.e. $x_1>2$ i.e. $3leq x_1$. That is to say $|A_1|$ is the number of solutions to
$$begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$$
Remember to continue calculations that the number of solutions to the system
$$begin{cases}x_1+x_2+dots+x_r=n\ 0leq x_i~~forall iend{cases}$$
is seen to be $binom{n+r-1}{r-1}$ via stars and bars.
This is equivalent to the number of integral solutions to the system
$$begin{cases} x_1+x_2+x_3=6\0leq x_1leq 2\ 0leq x_2leq 3\ 3leq x_3color{grey}{leq 10}end{cases}$$
The upper limit on $x_3$ is irrelevant since it is impossible for us to select more pigs than we have in our group of six.
Let $S$ be the set of solutions where we don't care about any of the upper bounds. Let $A_1$ be the set of solutions where (at the very least) the first upperbound condition is violated (and possibly the second one too). Let $A_2$ be the set of solutions where the second upperbound condition is violated.
We wish to count $|Ssetminus (A_1cup A_2)| = |S|-|A_1|-|A_2|+|A_1cap A_2|$
What does it mean for an upper bound condition? Well, $A_1$ is when the condition $x_1leq 2$ is false, i.e. $x_1>2$ i.e. $3leq x_1$. That is to say $|A_1|$ is the number of solutions to
$$begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$$
Remember to continue calculations that the number of solutions to the system
$$begin{cases}x_1+x_2+dots+x_r=n\ 0leq x_i~~forall iend{cases}$$
is seen to be $binom{n+r-1}{r-1}$ via stars and bars.
answered Mar 2 '17 at 5:26
JMoravitz
46.3k33784
46.3k33784
But how do we calculate $|A_1|, |A_2| $ and $|A_1|cap|A_2|$
– Osheen Sachdev
Mar 2 '17 at 5:48
1
@OsheenSachdev $|A_1|$ and $|A_2|$ are numbers and cannot be intersected. You mean $|A_1cap A_2|$. Put the system into the form I give at the bottom where the lower bound is zero by making a change of variables. E.g. For $A_1$ it was $begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$. Setting $x_1-3=y_1$, $x_2=y_2$ and $x_3-3=y_3$ we have this system is equivalent to $begin{cases}y_1+y_2+y_3=0\ 0leq y_1\ 0leq y_2\ 0leq y_3end{cases}$, now apply the given formula.
– JMoravitz
Mar 2 '17 at 5:51
Okay got it...thank you so much!
– Osheen Sachdev
Mar 2 '17 at 5:52
add a comment |
But how do we calculate $|A_1|, |A_2| $ and $|A_1|cap|A_2|$
– Osheen Sachdev
Mar 2 '17 at 5:48
1
@OsheenSachdev $|A_1|$ and $|A_2|$ are numbers and cannot be intersected. You mean $|A_1cap A_2|$. Put the system into the form I give at the bottom where the lower bound is zero by making a change of variables. E.g. For $A_1$ it was $begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$. Setting $x_1-3=y_1$, $x_2=y_2$ and $x_3-3=y_3$ we have this system is equivalent to $begin{cases}y_1+y_2+y_3=0\ 0leq y_1\ 0leq y_2\ 0leq y_3end{cases}$, now apply the given formula.
– JMoravitz
Mar 2 '17 at 5:51
Okay got it...thank you so much!
– Osheen Sachdev
Mar 2 '17 at 5:52
But how do we calculate $|A_1|, |A_2| $ and $|A_1|cap|A_2|$
– Osheen Sachdev
Mar 2 '17 at 5:48
But how do we calculate $|A_1|, |A_2| $ and $|A_1|cap|A_2|$
– Osheen Sachdev
Mar 2 '17 at 5:48
1
1
@OsheenSachdev $|A_1|$ and $|A_2|$ are numbers and cannot be intersected. You mean $|A_1cap A_2|$. Put the system into the form I give at the bottom where the lower bound is zero by making a change of variables. E.g. For $A_1$ it was $begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$. Setting $x_1-3=y_1$, $x_2=y_2$ and $x_3-3=y_3$ we have this system is equivalent to $begin{cases}y_1+y_2+y_3=0\ 0leq y_1\ 0leq y_2\ 0leq y_3end{cases}$, now apply the given formula.
– JMoravitz
Mar 2 '17 at 5:51
@OsheenSachdev $|A_1|$ and $|A_2|$ are numbers and cannot be intersected. You mean $|A_1cap A_2|$. Put the system into the form I give at the bottom where the lower bound is zero by making a change of variables. E.g. For $A_1$ it was $begin{cases}x_1+x_2+x_3=6\ 3leq x_1\ 0leq x_2\ 3leq x_3end{cases}$. Setting $x_1-3=y_1$, $x_2=y_2$ and $x_3-3=y_3$ we have this system is equivalent to $begin{cases}y_1+y_2+y_3=0\ 0leq y_1\ 0leq y_2\ 0leq y_3end{cases}$, now apply the given formula.
– JMoravitz
Mar 2 '17 at 5:51
Okay got it...thank you so much!
– Osheen Sachdev
Mar 2 '17 at 5:52
Okay got it...thank you so much!
– Osheen Sachdev
Mar 2 '17 at 5:52
add a comment |
Three seats on the committee are for pigs only, and the other three are at-large. Let's count the ways to fill the at-large seats, since there's exactly one way to fill the reserved seats. Each way corresponds to a monomial of degree $3$ in this product:
$$ (1 + c + c^2)(1 + d + d^2 + d^3)(1 + p + p^2 + p^3) enspace, $$
where $c^id^jp^k$ represents a committee with $i$ cats, $j$ dogs, and $k$ pigs. There are nine such terms with non-negative exponents and $i leq 2$:
$$ p^3, dp^2, d^2p, d^3, cp^2, cdp, cd^2, c^2p, c^2d enspace. $$
Hence there are nine ways to form the committee.
add a comment |
Three seats on the committee are for pigs only, and the other three are at-large. Let's count the ways to fill the at-large seats, since there's exactly one way to fill the reserved seats. Each way corresponds to a monomial of degree $3$ in this product:
$$ (1 + c + c^2)(1 + d + d^2 + d^3)(1 + p + p^2 + p^3) enspace, $$
where $c^id^jp^k$ represents a committee with $i$ cats, $j$ dogs, and $k$ pigs. There are nine such terms with non-negative exponents and $i leq 2$:
$$ p^3, dp^2, d^2p, d^3, cp^2, cdp, cd^2, c^2p, c^2d enspace. $$
Hence there are nine ways to form the committee.
add a comment |
Three seats on the committee are for pigs only, and the other three are at-large. Let's count the ways to fill the at-large seats, since there's exactly one way to fill the reserved seats. Each way corresponds to a monomial of degree $3$ in this product:
$$ (1 + c + c^2)(1 + d + d^2 + d^3)(1 + p + p^2 + p^3) enspace, $$
where $c^id^jp^k$ represents a committee with $i$ cats, $j$ dogs, and $k$ pigs. There are nine such terms with non-negative exponents and $i leq 2$:
$$ p^3, dp^2, d^2p, d^3, cp^2, cdp, cd^2, c^2p, c^2d enspace. $$
Hence there are nine ways to form the committee.
Three seats on the committee are for pigs only, and the other three are at-large. Let's count the ways to fill the at-large seats, since there's exactly one way to fill the reserved seats. Each way corresponds to a monomial of degree $3$ in this product:
$$ (1 + c + c^2)(1 + d + d^2 + d^3)(1 + p + p^2 + p^3) enspace, $$
where $c^id^jp^k$ represents a committee with $i$ cats, $j$ dogs, and $k$ pigs. There are nine such terms with non-negative exponents and $i leq 2$:
$$ p^3, dp^2, d^2p, d^3, cp^2, cdp, cd^2, c^2p, c^2d enspace. $$
Hence there are nine ways to form the committee.
answered Mar 2 '17 at 6:19
Fabio Somenzi
6,41221221
6,41221221
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f2168018%2fhow-many-ways-can-we-choose-a-committee-of-6-animals-if-there-must-be-at-least-3%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
Are each animal of a kind considered identical or do they all have different names and are considered distinct? If considered identical, consider using stars and bars coupled with inclusion-exclusion. If considered distinct, recommend just approaching directly by cases.
– JMoravitz
Mar 2 '17 at 4:06