What is the total number of study schedules for a seven day period for four subjects where each subject is...
$begingroup$
A student wants to make up a schedule for a seven-day period during which she will study one subject each day. What is the number of schedules that devote at least one day to each subject?
My attempt at the solution
Since there are $ 7!/3!$ ways to schedule four subjects for four of the seven days, and $ 4^3$ ways to schedule three subjects for three remaining days, total number of ways to schedule the subjects are $ (7!/3!)times4^3 $.
But this is not the correct answer. Please explain what is wrong with this reasoning.
combinatorics discrete-mathematics
$endgroup$
add a comment |
$begingroup$
A student wants to make up a schedule for a seven-day period during which she will study one subject each day. What is the number of schedules that devote at least one day to each subject?
My attempt at the solution
Since there are $ 7!/3!$ ways to schedule four subjects for four of the seven days, and $ 4^3$ ways to schedule three subjects for three remaining days, total number of ways to schedule the subjects are $ (7!/3!)times4^3 $.
But this is not the correct answer. Please explain what is wrong with this reasoning.
combinatorics discrete-mathematics
$endgroup$
add a comment |
$begingroup$
A student wants to make up a schedule for a seven-day period during which she will study one subject each day. What is the number of schedules that devote at least one day to each subject?
My attempt at the solution
Since there are $ 7!/3!$ ways to schedule four subjects for four of the seven days, and $ 4^3$ ways to schedule three subjects for three remaining days, total number of ways to schedule the subjects are $ (7!/3!)times4^3 $.
But this is not the correct answer. Please explain what is wrong with this reasoning.
combinatorics discrete-mathematics
$endgroup$
A student wants to make up a schedule for a seven-day period during which she will study one subject each day. What is the number of schedules that devote at least one day to each subject?
My attempt at the solution
Since there are $ 7!/3!$ ways to schedule four subjects for four of the seven days, and $ 4^3$ ways to schedule three subjects for three remaining days, total number of ways to schedule the subjects are $ (7!/3!)times4^3 $.
But this is not the correct answer. Please explain what is wrong with this reasoning.
combinatorics discrete-mathematics
combinatorics discrete-mathematics
edited Jan 30 at 17:18


Maria Mazur
49.6k1361124
49.6k1361124
asked Nov 5 '17 at 17:19
genogeno
284
284
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I'm not quite sure if this is correct. So we could have distributions of type $a)$
$$4,1,1,1$$
or b)
$$3,2,1,1$$
or c)
$$2,2,2,1$$
The number of distribution of type a) is $4times {7choose 4}cdot 3cdot 2 =840$
The number of distribution of type b) is $12times {7choose 3}cdot {4choose 2}cdot{2choose 1}=5040$
The number of distribution of type c) is $4times {7choose 2}cdot {5choose 2}cdot {3choose 2}=2520$
So we have $840+5040+2520 = 8400$ schedules.
$endgroup$
$begingroup$
Thanks for the answer but the correct answer is 8404.
$endgroup$
– geno
Nov 5 '17 at 17:59
$begingroup$
@geno The correct answer is $8400$.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 18:34
add a comment |
$begingroup$
John Watson has provided you with a nice solution. We can obtain the same result using the Inclusion-Exclusion Principle.
For each of the seven days, the student has four choices of subject to study. Therefore, if there were no restrictions, she would have $4^7$ ways to choose her study schedule. From these, we must exclude those options in which she does not study each subject at least once.
She has $binom{4}{k}$ ways to exclude $k$ of the four subjects from her study schedule and $(4 - k)^7$ ways to use the seven days to study the remaining $4 - k$ subjects. By the Inclusion-Exclusion Principle, the number of ways the student can arrange her schedule so that she studies each subject at least once over a period of seven days is
$$sum_{k = 0}^{4} (-1)^kbinom{4}{k}(4 - k)^7 = binom{4}{0}4^7 - binom{4}{1}3^7 + binom{4}{2}2^7 - binom{4}{3}1^7 + binom{4}{4}0^7 = 8400$$
What is wrong with your attempt?
By designating particular days as the ones on which she studies each subject, you count distributions in which she studies a subject more than once multiple times.
Let's use John Watson's solution as a template.
You count schedules in which she studies one subject on four days and the other subjects on one day each four times, once for each way you could have designated one of those four days as the day she studies the subject she studies four times.
You count schedules in which she studies one subject on three days, a second subject on two days, and the other subjects on one day each six times, once for each of the three ways you could designate one of the three days as the day on which she studies the subject she studies three times and once for each of the two ways you could designate one of the two days as the day she studies the subject she studies on two days.
You count schedules in which she studies three subjects on two days each and one subject on one day eight times since each subject she studies on two days is counted twice, once for each of the two ways you could designate a particular day as the day on which she studies a subject she studies on two days.
Notice that
$$binom{7}{4} cdot 4! cdot 4^3 = frac{7!}{3!} cdot 4^3 = 4 cdot binom{4}{1} binom{7}{4} cdot 3! + 6 cdot binom{4}{1}binom{7}{3}binom{3}{1}binom{4}{2}binom{2}{1} + 8 cdot binom{4}{3}binom{7}{2}binom{5}{2}binom{3}{2}$$
$endgroup$
$begingroup$
Thank you but I'm not getting what is wrong with the argument I've used. Please explain.
$endgroup$
– geno
Nov 5 '17 at 18:59
$begingroup$
I have added an explanation of what you did wrong.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 19:02
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%2f2506160%2fwhat-is-the-total-number-of-study-schedules-for-a-seven-day-period-for-four-subj%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
$begingroup$
I'm not quite sure if this is correct. So we could have distributions of type $a)$
$$4,1,1,1$$
or b)
$$3,2,1,1$$
or c)
$$2,2,2,1$$
The number of distribution of type a) is $4times {7choose 4}cdot 3cdot 2 =840$
The number of distribution of type b) is $12times {7choose 3}cdot {4choose 2}cdot{2choose 1}=5040$
The number of distribution of type c) is $4times {7choose 2}cdot {5choose 2}cdot {3choose 2}=2520$
So we have $840+5040+2520 = 8400$ schedules.
$endgroup$
$begingroup$
Thanks for the answer but the correct answer is 8404.
$endgroup$
– geno
Nov 5 '17 at 17:59
$begingroup$
@geno The correct answer is $8400$.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 18:34
add a comment |
$begingroup$
I'm not quite sure if this is correct. So we could have distributions of type $a)$
$$4,1,1,1$$
or b)
$$3,2,1,1$$
or c)
$$2,2,2,1$$
The number of distribution of type a) is $4times {7choose 4}cdot 3cdot 2 =840$
The number of distribution of type b) is $12times {7choose 3}cdot {4choose 2}cdot{2choose 1}=5040$
The number of distribution of type c) is $4times {7choose 2}cdot {5choose 2}cdot {3choose 2}=2520$
So we have $840+5040+2520 = 8400$ schedules.
$endgroup$
$begingroup$
Thanks for the answer but the correct answer is 8404.
$endgroup$
– geno
Nov 5 '17 at 17:59
$begingroup$
@geno The correct answer is $8400$.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 18:34
add a comment |
$begingroup$
I'm not quite sure if this is correct. So we could have distributions of type $a)$
$$4,1,1,1$$
or b)
$$3,2,1,1$$
or c)
$$2,2,2,1$$
The number of distribution of type a) is $4times {7choose 4}cdot 3cdot 2 =840$
The number of distribution of type b) is $12times {7choose 3}cdot {4choose 2}cdot{2choose 1}=5040$
The number of distribution of type c) is $4times {7choose 2}cdot {5choose 2}cdot {3choose 2}=2520$
So we have $840+5040+2520 = 8400$ schedules.
$endgroup$
I'm not quite sure if this is correct. So we could have distributions of type $a)$
$$4,1,1,1$$
or b)
$$3,2,1,1$$
or c)
$$2,2,2,1$$
The number of distribution of type a) is $4times {7choose 4}cdot 3cdot 2 =840$
The number of distribution of type b) is $12times {7choose 3}cdot {4choose 2}cdot{2choose 1}=5040$
The number of distribution of type c) is $4times {7choose 2}cdot {5choose 2}cdot {3choose 2}=2520$
So we have $840+5040+2520 = 8400$ schedules.
answered Nov 5 '17 at 17:42


Maria MazurMaria Mazur
49.6k1361124
49.6k1361124
$begingroup$
Thanks for the answer but the correct answer is 8404.
$endgroup$
– geno
Nov 5 '17 at 17:59
$begingroup$
@geno The correct answer is $8400$.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 18:34
add a comment |
$begingroup$
Thanks for the answer but the correct answer is 8404.
$endgroup$
– geno
Nov 5 '17 at 17:59
$begingroup$
@geno The correct answer is $8400$.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 18:34
$begingroup$
Thanks for the answer but the correct answer is 8404.
$endgroup$
– geno
Nov 5 '17 at 17:59
$begingroup$
Thanks for the answer but the correct answer is 8404.
$endgroup$
– geno
Nov 5 '17 at 17:59
$begingroup$
@geno The correct answer is $8400$.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 18:34
$begingroup$
@geno The correct answer is $8400$.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 18:34
add a comment |
$begingroup$
John Watson has provided you with a nice solution. We can obtain the same result using the Inclusion-Exclusion Principle.
For each of the seven days, the student has four choices of subject to study. Therefore, if there were no restrictions, she would have $4^7$ ways to choose her study schedule. From these, we must exclude those options in which she does not study each subject at least once.
She has $binom{4}{k}$ ways to exclude $k$ of the four subjects from her study schedule and $(4 - k)^7$ ways to use the seven days to study the remaining $4 - k$ subjects. By the Inclusion-Exclusion Principle, the number of ways the student can arrange her schedule so that she studies each subject at least once over a period of seven days is
$$sum_{k = 0}^{4} (-1)^kbinom{4}{k}(4 - k)^7 = binom{4}{0}4^7 - binom{4}{1}3^7 + binom{4}{2}2^7 - binom{4}{3}1^7 + binom{4}{4}0^7 = 8400$$
What is wrong with your attempt?
By designating particular days as the ones on which she studies each subject, you count distributions in which she studies a subject more than once multiple times.
Let's use John Watson's solution as a template.
You count schedules in which she studies one subject on four days and the other subjects on one day each four times, once for each way you could have designated one of those four days as the day she studies the subject she studies four times.
You count schedules in which she studies one subject on three days, a second subject on two days, and the other subjects on one day each six times, once for each of the three ways you could designate one of the three days as the day on which she studies the subject she studies three times and once for each of the two ways you could designate one of the two days as the day she studies the subject she studies on two days.
You count schedules in which she studies three subjects on two days each and one subject on one day eight times since each subject she studies on two days is counted twice, once for each of the two ways you could designate a particular day as the day on which she studies a subject she studies on two days.
Notice that
$$binom{7}{4} cdot 4! cdot 4^3 = frac{7!}{3!} cdot 4^3 = 4 cdot binom{4}{1} binom{7}{4} cdot 3! + 6 cdot binom{4}{1}binom{7}{3}binom{3}{1}binom{4}{2}binom{2}{1} + 8 cdot binom{4}{3}binom{7}{2}binom{5}{2}binom{3}{2}$$
$endgroup$
$begingroup$
Thank you but I'm not getting what is wrong with the argument I've used. Please explain.
$endgroup$
– geno
Nov 5 '17 at 18:59
$begingroup$
I have added an explanation of what you did wrong.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 19:02
add a comment |
$begingroup$
John Watson has provided you with a nice solution. We can obtain the same result using the Inclusion-Exclusion Principle.
For each of the seven days, the student has four choices of subject to study. Therefore, if there were no restrictions, she would have $4^7$ ways to choose her study schedule. From these, we must exclude those options in which she does not study each subject at least once.
She has $binom{4}{k}$ ways to exclude $k$ of the four subjects from her study schedule and $(4 - k)^7$ ways to use the seven days to study the remaining $4 - k$ subjects. By the Inclusion-Exclusion Principle, the number of ways the student can arrange her schedule so that she studies each subject at least once over a period of seven days is
$$sum_{k = 0}^{4} (-1)^kbinom{4}{k}(4 - k)^7 = binom{4}{0}4^7 - binom{4}{1}3^7 + binom{4}{2}2^7 - binom{4}{3}1^7 + binom{4}{4}0^7 = 8400$$
What is wrong with your attempt?
By designating particular days as the ones on which she studies each subject, you count distributions in which she studies a subject more than once multiple times.
Let's use John Watson's solution as a template.
You count schedules in which she studies one subject on four days and the other subjects on one day each four times, once for each way you could have designated one of those four days as the day she studies the subject she studies four times.
You count schedules in which she studies one subject on three days, a second subject on two days, and the other subjects on one day each six times, once for each of the three ways you could designate one of the three days as the day on which she studies the subject she studies three times and once for each of the two ways you could designate one of the two days as the day she studies the subject she studies on two days.
You count schedules in which she studies three subjects on two days each and one subject on one day eight times since each subject she studies on two days is counted twice, once for each of the two ways you could designate a particular day as the day on which she studies a subject she studies on two days.
Notice that
$$binom{7}{4} cdot 4! cdot 4^3 = frac{7!}{3!} cdot 4^3 = 4 cdot binom{4}{1} binom{7}{4} cdot 3! + 6 cdot binom{4}{1}binom{7}{3}binom{3}{1}binom{4}{2}binom{2}{1} + 8 cdot binom{4}{3}binom{7}{2}binom{5}{2}binom{3}{2}$$
$endgroup$
$begingroup$
Thank you but I'm not getting what is wrong with the argument I've used. Please explain.
$endgroup$
– geno
Nov 5 '17 at 18:59
$begingroup$
I have added an explanation of what you did wrong.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 19:02
add a comment |
$begingroup$
John Watson has provided you with a nice solution. We can obtain the same result using the Inclusion-Exclusion Principle.
For each of the seven days, the student has four choices of subject to study. Therefore, if there were no restrictions, she would have $4^7$ ways to choose her study schedule. From these, we must exclude those options in which she does not study each subject at least once.
She has $binom{4}{k}$ ways to exclude $k$ of the four subjects from her study schedule and $(4 - k)^7$ ways to use the seven days to study the remaining $4 - k$ subjects. By the Inclusion-Exclusion Principle, the number of ways the student can arrange her schedule so that she studies each subject at least once over a period of seven days is
$$sum_{k = 0}^{4} (-1)^kbinom{4}{k}(4 - k)^7 = binom{4}{0}4^7 - binom{4}{1}3^7 + binom{4}{2}2^7 - binom{4}{3}1^7 + binom{4}{4}0^7 = 8400$$
What is wrong with your attempt?
By designating particular days as the ones on which she studies each subject, you count distributions in which she studies a subject more than once multiple times.
Let's use John Watson's solution as a template.
You count schedules in which she studies one subject on four days and the other subjects on one day each four times, once for each way you could have designated one of those four days as the day she studies the subject she studies four times.
You count schedules in which she studies one subject on three days, a second subject on two days, and the other subjects on one day each six times, once for each of the three ways you could designate one of the three days as the day on which she studies the subject she studies three times and once for each of the two ways you could designate one of the two days as the day she studies the subject she studies on two days.
You count schedules in which she studies three subjects on two days each and one subject on one day eight times since each subject she studies on two days is counted twice, once for each of the two ways you could designate a particular day as the day on which she studies a subject she studies on two days.
Notice that
$$binom{7}{4} cdot 4! cdot 4^3 = frac{7!}{3!} cdot 4^3 = 4 cdot binom{4}{1} binom{7}{4} cdot 3! + 6 cdot binom{4}{1}binom{7}{3}binom{3}{1}binom{4}{2}binom{2}{1} + 8 cdot binom{4}{3}binom{7}{2}binom{5}{2}binom{3}{2}$$
$endgroup$
John Watson has provided you with a nice solution. We can obtain the same result using the Inclusion-Exclusion Principle.
For each of the seven days, the student has four choices of subject to study. Therefore, if there were no restrictions, she would have $4^7$ ways to choose her study schedule. From these, we must exclude those options in which she does not study each subject at least once.
She has $binom{4}{k}$ ways to exclude $k$ of the four subjects from her study schedule and $(4 - k)^7$ ways to use the seven days to study the remaining $4 - k$ subjects. By the Inclusion-Exclusion Principle, the number of ways the student can arrange her schedule so that she studies each subject at least once over a period of seven days is
$$sum_{k = 0}^{4} (-1)^kbinom{4}{k}(4 - k)^7 = binom{4}{0}4^7 - binom{4}{1}3^7 + binom{4}{2}2^7 - binom{4}{3}1^7 + binom{4}{4}0^7 = 8400$$
What is wrong with your attempt?
By designating particular days as the ones on which she studies each subject, you count distributions in which she studies a subject more than once multiple times.
Let's use John Watson's solution as a template.
You count schedules in which she studies one subject on four days and the other subjects on one day each four times, once for each way you could have designated one of those four days as the day she studies the subject she studies four times.
You count schedules in which she studies one subject on three days, a second subject on two days, and the other subjects on one day each six times, once for each of the three ways you could designate one of the three days as the day on which she studies the subject she studies three times and once for each of the two ways you could designate one of the two days as the day she studies the subject she studies on two days.
You count schedules in which she studies three subjects on two days each and one subject on one day eight times since each subject she studies on two days is counted twice, once for each of the two ways you could designate a particular day as the day on which she studies a subject she studies on two days.
Notice that
$$binom{7}{4} cdot 4! cdot 4^3 = frac{7!}{3!} cdot 4^3 = 4 cdot binom{4}{1} binom{7}{4} cdot 3! + 6 cdot binom{4}{1}binom{7}{3}binom{3}{1}binom{4}{2}binom{2}{1} + 8 cdot binom{4}{3}binom{7}{2}binom{5}{2}binom{3}{2}$$
edited Nov 6 '17 at 9:32
answered Nov 5 '17 at 18:42
N. F. TaussigN. F. Taussig
45k103358
45k103358
$begingroup$
Thank you but I'm not getting what is wrong with the argument I've used. Please explain.
$endgroup$
– geno
Nov 5 '17 at 18:59
$begingroup$
I have added an explanation of what you did wrong.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 19:02
add a comment |
$begingroup$
Thank you but I'm not getting what is wrong with the argument I've used. Please explain.
$endgroup$
– geno
Nov 5 '17 at 18:59
$begingroup$
I have added an explanation of what you did wrong.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 19:02
$begingroup$
Thank you but I'm not getting what is wrong with the argument I've used. Please explain.
$endgroup$
– geno
Nov 5 '17 at 18:59
$begingroup$
Thank you but I'm not getting what is wrong with the argument I've used. Please explain.
$endgroup$
– geno
Nov 5 '17 at 18:59
$begingroup$
I have added an explanation of what you did wrong.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 19:02
$begingroup$
I have added an explanation of what you did wrong.
$endgroup$
– N. F. Taussig
Nov 5 '17 at 19:02
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%2f2506160%2fwhat-is-the-total-number-of-study-schedules-for-a-seven-day-period-for-four-subj%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