Can someone walk me through this combination/counting problem (number of possible class schedules)?
$begingroup$
I am completely confused by the following problem.
I understand the basic formula for combinations: $frac{n!}{k!(n-k)!}$. For example, if the equation was asking about only one quarter with no prerequisites, there would be 45 combinations.
However, with the perquisites and 5 quarters, I am completely lost. I tried making a tree-diagram with the various options (the first quarter is 6 choose 2, after that, it breaks off into 5 choose 2 (if 351 is taken) or 4 choose 2 (if is isn't)... and so on. I multiplied each branch and added them together, but it gave me a ridiculously high number (1944000), which is why I think I'm doing it incorrectly. Can someone walk me through step by step so that I can understand the process here?
combinatorics discrete-mathematics permutations combinations
asked Jan 13 at 21:06
digiHarmoniousdigiHarmonious
303
$endgroup$
add a comment |
$begingroup$
I am completely confused by the following problem.
I understand the basic formula for combinations: $frac{n!}{k!(n-k)!}$. For example, if the equation was asking about only one quarter with no prerequisites, there would be 45 combinations.
However, with the perquisites and 5 quarters, I am completely lost. I tried making a tree-diagram with the various options (the first quarter is 6 choose 2, after that, it breaks off into 5 choose 2 (if 351 is taken) or 4 choose 2 (if is isn't)... and so on. I multiplied each branch and added them together, but it gave me a ridiculously high number (1944000), which is why I think I'm doing it incorrectly. Can someone walk me through step by step so that I can understand the process here?
combinatorics discrete-mathematics permutations combinations
asked Jan 13 at 21:06
digiHarmoniousdigiHarmonious
303
$endgroup$
add a comment |
$begingroup$
I am completely confused by the following problem.
I understand the basic formula for combinations: $frac{n!}{k!(n-k)!}$. For example, if the equation was asking about only one quarter with no prerequisites, there would be 45 combinations.
However, with the perquisites and 5 quarters, I am completely lost. I tried making a tree-diagram with the various options (the first quarter is 6 choose 2, after that, it breaks off into 5 choose 2 (if 351 is taken) or 4 choose 2 (if is isn't)... and so on. I multiplied each branch and added them together, but it gave me a ridiculously high number (1944000), which is why I think I'm doing it incorrectly. Can someone walk me through step by step so that I can understand the process here?
combinatorics discrete-mathematics permutations combinations
asked Jan 13 at 21:06
digiHarmoniousdigiHarmonious
303
$endgroup$
I am completely confused by the following problem.
I understand the basic formula for combinations: $frac{n!}{k!(n-k)!}$. For example, if the equation was asking about only one quarter with no prerequisites, there would be 45 combinations.
However, with the perquisites and 5 quarters, I am completely lost. I tried making a tree-diagram with the various options (the first quarter is 6 choose 2, after that, it breaks off into 5 choose 2 (if 351 is taken) or 4 choose 2 (if is isn't)... and so on. I multiplied each branch and added them together, but it gave me a ridiculously high number (1944000), which is why I think I'm doing it incorrectly. Can someone walk me through step by step so that I can understand the process here?
combinatorics discrete-mathematics permutations combinations
combinatorics discrete-mathematics permutations combinations
asked Jan 13 at 21:06
digiHarmoniousdigiHarmonious
303
asked Jan 13 at 21:06
digiHarmoniousdigiHarmonious
303
asked Jan 13 at 21:06
digiHarmoniousdigiHarmonious
303
asked Jan 13 at 21:06
digiHarmoniousdigiHarmonious
303
asked Jan 13 at 21:06
digiHarmoniousdigiHarmonious
303
303
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I don't see any nice general strategy here, because the problem is very arbitrary. So let us try to solve this problem while trying to keep the amount of considered cases as low as possible.
For convenience, let the courses be named $A,B,C,D,E,F_1,..,F_5$ where we have the dependencies $A$ before $B$, $B$ before $C$ and $D$, and $D$ before $E$. To simplify, the courses $A,B,D$ and $E$ must be followed in that order, and $C$ must be followed after $B$. We consider two cases.
Case 1: Courses $A,B,C,D$ and $E$ are all followed on different days. Their order has to be $ABCDE$, $ABDCE$ or $ABDEC$. With their order fixed, their quarters are also fixed. We then just have to arrange the remaining $5$ courses, which leaves us with $5!$ options per order, so $3cdot5!=360$ options in total.
Case 2: Course $C$ is followed on the same quarter as either $D$ or $E$. There will be exactly one quarter where none of the courses $A,B,C,D$ and $E$ are followed, for which there are $5$ options. We then choose whether $C$ is followed on the same quarter as $D$ or $E$, which gives $2$ options. Then for each option, we only need to arrange the remaining $5$ courses, which leaves us with $5!/2$ options per order, so $5cdot2cdot5!/2=600$ options in total. The divide by two comes from the fact that two of the remaining courses fall on the same day, so their respective order does not matter.
In conclusion, the answer is $360+600=960$.
answered Jan 13 at 21:29
SmileyCraftSmileyCraft
3,749519
$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%2f3072519%2fcan-someone-walk-me-through-this-combination-counting-problem-number-of-possibl%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$
I don't see any nice general strategy here, because the problem is very arbitrary. So let us try to solve this problem while trying to keep the amount of considered cases as low as possible.
For convenience, let the courses be named $A,B,C,D,E,F_1,..,F_5$ where we have the dependencies $A$ before $B$, $B$ before $C$ and $D$, and $D$ before $E$. To simplify, the courses $A,B,D$ and $E$ must be followed in that order, and $C$ must be followed after $B$. We consider two cases.
Case 1: Courses $A,B,C,D$ and $E$ are all followed on different days. Their order has to be $ABCDE$, $ABDCE$ or $ABDEC$. With their order fixed, their quarters are also fixed. We then just have to arrange the remaining $5$ courses, which leaves us with $5!$ options per order, so $3cdot5!=360$ options in total.
Case 2: Course $C$ is followed on the same quarter as either $D$ or $E$. There will be exactly one quarter where none of the courses $A,B,C,D$ and $E$ are followed, for which there are $5$ options. We then choose whether $C$ is followed on the same quarter as $D$ or $E$, which gives $2$ options. Then for each option, we only need to arrange the remaining $5$ courses, which leaves us with $5!/2$ options per order, so $5cdot2cdot5!/2=600$ options in total. The divide by two comes from the fact that two of the remaining courses fall on the same day, so their respective order does not matter.
In conclusion, the answer is $360+600=960$.
answered Jan 13 at 21:29
SmileyCraftSmileyCraft
3,749519
$endgroup$
add a comment |
$begingroup$
I don't see any nice general strategy here, because the problem is very arbitrary. So let us try to solve this problem while trying to keep the amount of considered cases as low as possible.
For convenience, let the courses be named $A,B,C,D,E,F_1,..,F_5$ where we have the dependencies $A$ before $B$, $B$ before $C$ and $D$, and $D$ before $E$. To simplify, the courses $A,B,D$ and $E$ must be followed in that order, and $C$ must be followed after $B$. We consider two cases.
Case 1: Courses $A,B,C,D$ and $E$ are all followed on different days. Their order has to be $ABCDE$, $ABDCE$ or $ABDEC$. With their order fixed, their quarters are also fixed. We then just have to arrange the remaining $5$ courses, which leaves us with $5!$ options per order, so $3cdot5!=360$ options in total.
Case 2: Course $C$ is followed on the same quarter as either $D$ or $E$. There will be exactly one quarter where none of the courses $A,B,C,D$ and $E$ are followed, for which there are $5$ options. We then choose whether $C$ is followed on the same quarter as $D$ or $E$, which gives $2$ options. Then for each option, we only need to arrange the remaining $5$ courses, which leaves us with $5!/2$ options per order, so $5cdot2cdot5!/2=600$ options in total. The divide by two comes from the fact that two of the remaining courses fall on the same day, so their respective order does not matter.
In conclusion, the answer is $360+600=960$.
answered Jan 13 at 21:29
SmileyCraftSmileyCraft
3,749519
$endgroup$
add a comment |
$begingroup$
I don't see any nice general strategy here, because the problem is very arbitrary. So let us try to solve this problem while trying to keep the amount of considered cases as low as possible.
For convenience, let the courses be named $A,B,C,D,E,F_1,..,F_5$ where we have the dependencies $A$ before $B$, $B$ before $C$ and $D$, and $D$ before $E$. To simplify, the courses $A,B,D$ and $E$ must be followed in that order, and $C$ must be followed after $B$. We consider two cases.
Case 1: Courses $A,B,C,D$ and $E$ are all followed on different days. Their order has to be $ABCDE$, $ABDCE$ or $ABDEC$. With their order fixed, their quarters are also fixed. We then just have to arrange the remaining $5$ courses, which leaves us with $5!$ options per order, so $3cdot5!=360$ options in total.
Case 2: Course $C$ is followed on the same quarter as either $D$ or $E$. There will be exactly one quarter where none of the courses $A,B,C,D$ and $E$ are followed, for which there are $5$ options. We then choose whether $C$ is followed on the same quarter as $D$ or $E$, which gives $2$ options. Then for each option, we only need to arrange the remaining $5$ courses, which leaves us with $5!/2$ options per order, so $5cdot2cdot5!/2=600$ options in total. The divide by two comes from the fact that two of the remaining courses fall on the same day, so their respective order does not matter.
In conclusion, the answer is $360+600=960$.
answered Jan 13 at 21:29
SmileyCraftSmileyCraft
3,749519
$endgroup$
I don't see any nice general strategy here, because the problem is very arbitrary. So let us try to solve this problem while trying to keep the amount of considered cases as low as possible.
For convenience, let the courses be named $A,B,C,D,E,F_1,..,F_5$ where we have the dependencies $A$ before $B$, $B$ before $C$ and $D$, and $D$ before $E$. To simplify, the courses $A,B,D$ and $E$ must be followed in that order, and $C$ must be followed after $B$. We consider two cases.
Case 1: Courses $A,B,C,D$ and $E$ are all followed on different days. Their order has to be $ABCDE$, $ABDCE$ or $ABDEC$. With their order fixed, their quarters are also fixed. We then just have to arrange the remaining $5$ courses, which leaves us with $5!$ options per order, so $3cdot5!=360$ options in total.
Case 2: Course $C$ is followed on the same quarter as either $D$ or $E$. There will be exactly one quarter where none of the courses $A,B,C,D$ and $E$ are followed, for which there are $5$ options. We then choose whether $C$ is followed on the same quarter as $D$ or $E$, which gives $2$ options. Then for each option, we only need to arrange the remaining $5$ courses, which leaves us with $5!/2$ options per order, so $5cdot2cdot5!/2=600$ options in total. The divide by two comes from the fact that two of the remaining courses fall on the same day, so their respective order does not matter.
In conclusion, the answer is $360+600=960$.
answered Jan 13 at 21:29
SmileyCraftSmileyCraft
3,749519
answered Jan 13 at 21:29
SmileyCraftSmileyCraft
3,749519
answered Jan 13 at 21:29
SmileyCraftSmileyCraft
3,749519
answered Jan 13 at 21:29
SmileyCraftSmileyCraft
3,749519
3,749519
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%2f3072519%2fcan-someone-walk-me-through-this-combination-counting-problem-number-of-possibl%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
