Using Generating Function to calculate number of ways to select committees
$begingroup$
How many ways are there to select three committees from 10 people? The committees serve different purposes, someone has to be in every committee and everyone serves in exactly one committee. (Use the appropriate generating function)
My approach is,
$$ (e^x-1)^3 $$
$$ = {e}^{3x} - 3e^{2x}+3e^x - 1 $$
Is it correct?
discrete-mathematics generating-functions
asked Dec 10 '18 at 4:50
jaykodeveloperjaykodeveloper
1238
$endgroup$
add a comment |
$begingroup$
How many ways are there to select three committees from 10 people? The committees serve different purposes, someone has to be in every committee and everyone serves in exactly one committee. (Use the appropriate generating function)
My approach is,
$$ (e^x-1)^3 $$
$$ = {e}^{3x} - 3e^{2x}+3e^x - 1 $$
Is it correct?
discrete-mathematics generating-functions
asked Dec 10 '18 at 4:50
jaykodeveloperjaykodeveloper
1238
$endgroup$
$begingroup$
You have written down two equalities which are patently false.
$endgroup$
– Lord Shark the Unknown
Dec 10 '18 at 4:53
$begingroup$
@LordSharktheUnknown I edited.
$endgroup$
– jaykodeveloper
Dec 10 '18 at 5:14
add a comment |
$begingroup$
How many ways are there to select three committees from 10 people? The committees serve different purposes, someone has to be in every committee and everyone serves in exactly one committee. (Use the appropriate generating function)
My approach is,
$$ (e^x-1)^3 $$
$$ = {e}^{3x} - 3e^{2x}+3e^x - 1 $$
Is it correct?
discrete-mathematics generating-functions
asked Dec 10 '18 at 4:50
jaykodeveloperjaykodeveloper
1238
$endgroup$
How many ways are there to select three committees from 10 people? The committees serve different purposes, someone has to be in every committee and everyone serves in exactly one committee. (Use the appropriate generating function)
My approach is,
$$ (e^x-1)^3 $$
$$ = {e}^{3x} - 3e^{2x}+3e^x - 1 $$
Is it correct?
discrete-mathematics generating-functions
discrete-mathematics generating-functions
asked Dec 10 '18 at 4:50
jaykodeveloperjaykodeveloper
1238
asked Dec 10 '18 at 4:50
jaykodeveloperjaykodeveloper
1238
edited Dec 10 '18 at 4:55
jaykodeveloper
asked Dec 10 '18 at 4:50
jaykodeveloperjaykodeveloper
1238
asked Dec 10 '18 at 4:50
jaykodeveloperjaykodeveloper
1238
asked Dec 10 '18 at 4:50
jaykodeveloperjaykodeveloper
1238
1238
$begingroup$
You have written down two equalities which are patently false.
$endgroup$
– Lord Shark the Unknown
Dec 10 '18 at 4:53
$begingroup$
@LordSharktheUnknown I edited.
$endgroup$
– jaykodeveloper
Dec 10 '18 at 5:14
add a comment |
$begingroup$
You have written down two equalities which are patently false.
$endgroup$
– Lord Shark the Unknown
Dec 10 '18 at 4:53
$begingroup$
@LordSharktheUnknown I edited.
$endgroup$
– jaykodeveloper
Dec 10 '18 at 5:14
$begingroup$
You have written down two equalities which are patently false.
$endgroup$
– Lord Shark the Unknown
Dec 10 '18 at 4:53
$begingroup$
You have written down two equalities which are patently false.
$endgroup$
– Lord Shark the Unknown
Dec 10 '18 at 4:53
$begingroup$
@LordSharktheUnknown I edited.
$endgroup$
– jaykodeveloper
Dec 10 '18 at 5:14
$begingroup$
@LordSharktheUnknown I edited.
$endgroup$
– jaykodeveloper
Dec 10 '18 at 5:14
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
We can solve the problem first assuming that some committees can be left empty. So, if the exponent of $x$ is the people in the first committee, the exponent of $y$ is the people in the first committee, and the exponent of $z$ is the people in the first committee, then expanding the following expression the coefficient of each term indicates in how many ways you can form committees with the number of people in each committee indicated by the exponents: $(x+y+z)^{10}$. E.g., the coefficient of $x^3 y^5 z^2$ is 2520, hence there are 2520 ways to form committees con 3 people in the first one, 5 in the second one, and 2 in the third one.
Next, if every committee must have someone in it we must eliminate from our generating function the terms in which some exponent is zero. Using the inclusion-exclusion rule we get:
$$
f(x,y,z) = (x+y+z)^{10} - (x+y)^{10} - (x+z)^{10} - (y+z)^{10} + x^{10} + y^{10} + z^{10}
$$
Finally, the sum of all coefficients is $f(1,1,1) = 55980$, and that is the number of committees that can be formed verifying the conditions stated.
answered Dec 10 '18 at 6:21
mlerma54mlerma54
1,177148
$endgroup$
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%2f3033457%2fusing-generating-function-to-calculate-number-of-ways-to-select-committees%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We can solve the problem first assuming that some committees can be left empty. So, if the exponent of $x$ is the people in the first committee, the exponent of $y$ is the people in the first committee, and the exponent of $z$ is the people in the first committee, then expanding the following expression the coefficient of each term indicates in how many ways you can form committees with the number of people in each committee indicated by the exponents: $(x+y+z)^{10}$. E.g., the coefficient of $x^3 y^5 z^2$ is 2520, hence there are 2520 ways to form committees con 3 people in the first one, 5 in the second one, and 2 in the third one.
Next, if every committee must have someone in it we must eliminate from our generating function the terms in which some exponent is zero. Using the inclusion-exclusion rule we get:
$$
f(x,y,z) = (x+y+z)^{10} - (x+y)^{10} - (x+z)^{10} - (y+z)^{10} + x^{10} + y^{10} + z^{10}
$$
Finally, the sum of all coefficients is $f(1,1,1) = 55980$, and that is the number of committees that can be formed verifying the conditions stated.
answered Dec 10 '18 at 6:21
mlerma54mlerma54
1,177148
$endgroup$
add a comment |
$begingroup$
We can solve the problem first assuming that some committees can be left empty. So, if the exponent of $x$ is the people in the first committee, the exponent of $y$ is the people in the first committee, and the exponent of $z$ is the people in the first committee, then expanding the following expression the coefficient of each term indicates in how many ways you can form committees with the number of people in each committee indicated by the exponents: $(x+y+z)^{10}$. E.g., the coefficient of $x^3 y^5 z^2$ is 2520, hence there are 2520 ways to form committees con 3 people in the first one, 5 in the second one, and 2 in the third one.
Next, if every committee must have someone in it we must eliminate from our generating function the terms in which some exponent is zero. Using the inclusion-exclusion rule we get:
$$
f(x,y,z) = (x+y+z)^{10} - (x+y)^{10} - (x+z)^{10} - (y+z)^{10} + x^{10} + y^{10} + z^{10}
$$
Finally, the sum of all coefficients is $f(1,1,1) = 55980$, and that is the number of committees that can be formed verifying the conditions stated.
answered Dec 10 '18 at 6:21
mlerma54mlerma54
1,177148
$endgroup$
add a comment |
$begingroup$
We can solve the problem first assuming that some committees can be left empty. So, if the exponent of $x$ is the people in the first committee, the exponent of $y$ is the people in the first committee, and the exponent of $z$ is the people in the first committee, then expanding the following expression the coefficient of each term indicates in how many ways you can form committees with the number of people in each committee indicated by the exponents: $(x+y+z)^{10}$. E.g., the coefficient of $x^3 y^5 z^2$ is 2520, hence there are 2520 ways to form committees con 3 people in the first one, 5 in the second one, and 2 in the third one.
Next, if every committee must have someone in it we must eliminate from our generating function the terms in which some exponent is zero. Using the inclusion-exclusion rule we get:
$$
f(x,y,z) = (x+y+z)^{10} - (x+y)^{10} - (x+z)^{10} - (y+z)^{10} + x^{10} + y^{10} + z^{10}
$$
Finally, the sum of all coefficients is $f(1,1,1) = 55980$, and that is the number of committees that can be formed verifying the conditions stated.
answered Dec 10 '18 at 6:21
mlerma54mlerma54
1,177148
$endgroup$
We can solve the problem first assuming that some committees can be left empty. So, if the exponent of $x$ is the people in the first committee, the exponent of $y$ is the people in the first committee, and the exponent of $z$ is the people in the first committee, then expanding the following expression the coefficient of each term indicates in how many ways you can form committees with the number of people in each committee indicated by the exponents: $(x+y+z)^{10}$. E.g., the coefficient of $x^3 y^5 z^2$ is 2520, hence there are 2520 ways to form committees con 3 people in the first one, 5 in the second one, and 2 in the third one.
Next, if every committee must have someone in it we must eliminate from our generating function the terms in which some exponent is zero. Using the inclusion-exclusion rule we get:
$$
f(x,y,z) = (x+y+z)^{10} - (x+y)^{10} - (x+z)^{10} - (y+z)^{10} + x^{10} + y^{10} + z^{10}
$$
Finally, the sum of all coefficients is $f(1,1,1) = 55980$, and that is the number of committees that can be formed verifying the conditions stated.
answered Dec 10 '18 at 6:21
mlerma54mlerma54
1,177148
answered Dec 10 '18 at 6:21
mlerma54mlerma54
1,177148
answered Dec 10 '18 at 6:21
mlerma54mlerma54
1,177148
answered Dec 10 '18 at 6:21
mlerma54mlerma54
1,177148
1,177148
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%2f3033457%2fusing-generating-function-to-calculate-number-of-ways-to-select-committees%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$
You have written down two equalities which are patently false.
$endgroup$
– Lord Shark the Unknown
Dec 10 '18 at 4:53
$begingroup$
@LordSharktheUnknown I edited.
$endgroup$
– jaykodeveloper
Dec 10 '18 at 5:14