Mixing
Recurrence relation in a Student Attendance problem
I'm having trouble understanding the solution to a coding contest problem.
Student Attendance Problem
Suppose a student's attendance is recorded as a string, e.g.
PPAPPPPLPPPLPPLLAPPPP
where the letters represent Present, Late, and Absent. A reward is given to the student who satisfies the following criteria,
- No more than one absence.
- No triple consecutive lateness, e.g.
LLL.
Given an attendance record of length $n$, then, how many rewardable records exist?
For example, for $n=2$, only AA fails to be rewarded, of $3^2$ possible strings, so the answer is $8$.
Official Solution
The official solution attempts to build a recurrence relation, starting with this diagram:
It explains: Let $f[n]$ represent the number of rewardable cases for a string of length $n$. Let's divide into two cases,
- Strings ending with
L. - Strings ending with
P. (I don't know why it saysNin the diagram; typo, I think.)
It's easy to see that the second case is rewardable as long as the piece preceding the P, $f[n-1]$, is rewardable.
However, the L case must be split into four pieces, as shown. There, the author claims that the only troublesome piece is the last, ending the string in LLL. His exact words are,
Out of the four combinations possible at the end, the fourth combination, ending with a $LL$ at the end leads to an unrewardable string. But, since we've considered only rewardable strings of length $n-3$, for the last string to be rewardable at length $n-3$ and unawardable at length $n-1$, it must be preceded by a $PP$ before the $LL$.
Thus, accounting for the first string [left branch] again, all the rewardable strings of length $n-1$, except the strings of length $n−4$ followed by $PLL$, can contribute to a rewardable string of length $n$. Thus, this string accounts for a factor of $f[n-1] - f[n-4]$ to $f[n]$.
Thus, the recurring relation becomes:
$$f[n] = 2f[n-1] - f[n-4]$$
I was hoping someone could put this explanation in their own words, because I don't understand this author's. And he has made several typos in his explanation already, so I'm not sure I trust this explanation.
Another thing I don't understand is why the first of the four cases isn't also problematic, since if the $n-5$th and $n-4$th characters were L, then we'd also have an unrewardable string.
Any hints as to untangling the author's explanation would be appreciated. Thank you.
P.S. The author is intentionally ignoring A at this stage, to be considered separately.
combinatorics recurrence-relations
asked Apr 24 '17 at 22:28
Andrew Cheong
1,20421119
add a comment |
I'm having trouble understanding the solution to a coding contest problem.
Student Attendance Problem
Suppose a student's attendance is recorded as a string, e.g.
PPAPPPPLPPPLPPLLAPPPP
where the letters represent Present, Late, and Absent. A reward is given to the student who satisfies the following criteria,
- No more than one absence.
- No triple consecutive lateness, e.g.
LLL.
Given an attendance record of length $n$, then, how many rewardable records exist?
For example, for $n=2$, only AA fails to be rewarded, of $3^2$ possible strings, so the answer is $8$.
Official Solution
The official solution attempts to build a recurrence relation, starting with this diagram:
It explains: Let $f[n]$ represent the number of rewardable cases for a string of length $n$. Let's divide into two cases,
- Strings ending with
L. - Strings ending with
P. (I don't know why it saysNin the diagram; typo, I think.)
It's easy to see that the second case is rewardable as long as the piece preceding the P, $f[n-1]$, is rewardable.
However, the L case must be split into four pieces, as shown. There, the author claims that the only troublesome piece is the last, ending the string in LLL. His exact words are,
Out of the four combinations possible at the end, the fourth combination, ending with a $LL$ at the end leads to an unrewardable string. But, since we've considered only rewardable strings of length $n-3$, for the last string to be rewardable at length $n-3$ and unawardable at length $n-1$, it must be preceded by a $PP$ before the $LL$.
Thus, accounting for the first string [left branch] again, all the rewardable strings of length $n-1$, except the strings of length $n−4$ followed by $PLL$, can contribute to a rewardable string of length $n$. Thus, this string accounts for a factor of $f[n-1] - f[n-4]$ to $f[n]$.
Thus, the recurring relation becomes:
$$f[n] = 2f[n-1] - f[n-4]$$
I was hoping someone could put this explanation in their own words, because I don't understand this author's. And he has made several typos in his explanation already, so I'm not sure I trust this explanation.
Another thing I don't understand is why the first of the four cases isn't also problematic, since if the $n-5$th and $n-4$th characters were L, then we'd also have an unrewardable string.
Any hints as to untangling the author's explanation would be appreciated. Thank you.
P.S. The author is intentionally ignoring A at this stage, to be considered separately.
combinatorics recurrence-relations
asked Apr 24 '17 at 22:28
Andrew Cheong
1,20421119
2
I think you might mean $8$ for $n=2$ since there are $3^n$ possible records for $n$ days, and thus $9$ records for $n=1$, and with $1$ unacceptable record, there would be $8$ acceptable ones.
– Frpzzd
Apr 24 '17 at 22:55
Yes, that's correct, thanks!
– Andrew Cheong
Apr 25 '17 at 4:44
1
In the cold light of day I am still unable to make sense of this author's method. It may be that it does make sense but because of the lack of clarity, it looks possible that some "fudgery" may have been employed to match the desired answer. I know I'm biased, but I've done a few of these types of recurrences and I feel that my method is, by far, the easiest to understand so I'd stick with that for now if I were you. With a few more different examples you may be able to make sense of our author here but it looks a bit of a mess to me.
– N. Shales
Apr 25 '17 at 12:56
1
Thank you very much, I'll contact the author from here to try to find out what he meant to convey.
– Andrew Cheong
Apr 26 '17 at 8:11
FYI this is equivalent to problem 191 in project Euler. (there the role of L and A are swapped.) projecteuler.net/problem=191 If you bother to write the code to solve that problem numerically, then you can access their forum to see lots more DIFFERENT recurrences people used to solve this. however IMHO the accepted answer has one of the cleanest explanations.
– antkam
Nov 20 '18 at 14:09
add a comment |
I'm having trouble understanding the solution to a coding contest problem.
Student Attendance Problem
Suppose a student's attendance is recorded as a string, e.g.
PPAPPPPLPPPLPPLLAPPPP
where the letters represent Present, Late, and Absent. A reward is given to the student who satisfies the following criteria,
- No more than one absence.
- No triple consecutive lateness, e.g.
LLL.
Given an attendance record of length $n$, then, how many rewardable records exist?
For example, for $n=2$, only AA fails to be rewarded, of $3^2$ possible strings, so the answer is $8$.
Official Solution
The official solution attempts to build a recurrence relation, starting with this diagram:
It explains: Let $f[n]$ represent the number of rewardable cases for a string of length $n$. Let's divide into two cases,
- Strings ending with
L. - Strings ending with
P. (I don't know why it saysNin the diagram; typo, I think.)
It's easy to see that the second case is rewardable as long as the piece preceding the P, $f[n-1]$, is rewardable.
However, the L case must be split into four pieces, as shown. There, the author claims that the only troublesome piece is the last, ending the string in LLL. His exact words are,
Out of the four combinations possible at the end, the fourth combination, ending with a $LL$ at the end leads to an unrewardable string. But, since we've considered only rewardable strings of length $n-3$, for the last string to be rewardable at length $n-3$ and unawardable at length $n-1$, it must be preceded by a $PP$ before the $LL$.
Thus, accounting for the first string [left branch] again, all the rewardable strings of length $n-1$, except the strings of length $n−4$ followed by $PLL$, can contribute to a rewardable string of length $n$. Thus, this string accounts for a factor of $f[n-1] - f[n-4]$ to $f[n]$.
Thus, the recurring relation becomes:
$$f[n] = 2f[n-1] - f[n-4]$$
I was hoping someone could put this explanation in their own words, because I don't understand this author's. And he has made several typos in his explanation already, so I'm not sure I trust this explanation.
Another thing I don't understand is why the first of the four cases isn't also problematic, since if the $n-5$th and $n-4$th characters were L, then we'd also have an unrewardable string.
Any hints as to untangling the author's explanation would be appreciated. Thank you.
P.S. The author is intentionally ignoring A at this stage, to be considered separately.
combinatorics recurrence-relations
asked Apr 24 '17 at 22:28
Andrew Cheong
1,20421119
I'm having trouble understanding the solution to a coding contest problem.
Student Attendance Problem
Suppose a student's attendance is recorded as a string, e.g.
PPAPPPPLPPPLPPLLAPPPP
where the letters represent Present, Late, and Absent. A reward is given to the student who satisfies the following criteria,
- No more than one absence.
- No triple consecutive lateness, e.g.
LLL.
Given an attendance record of length $n$, then, how many rewardable records exist?
For example, for $n=2$, only AA fails to be rewarded, of $3^2$ possible strings, so the answer is $8$.
Official Solution
The official solution attempts to build a recurrence relation, starting with this diagram:
It explains: Let $f[n]$ represent the number of rewardable cases for a string of length $n$. Let's divide into two cases,
- Strings ending with
L. - Strings ending with
P. (I don't know why it saysNin the diagram; typo, I think.)
It's easy to see that the second case is rewardable as long as the piece preceding the P, $f[n-1]$, is rewardable.
However, the L case must be split into four pieces, as shown. There, the author claims that the only troublesome piece is the last, ending the string in LLL. His exact words are,
Out of the four combinations possible at the end, the fourth combination, ending with a $LL$ at the end leads to an unrewardable string. But, since we've considered only rewardable strings of length $n-3$, for the last string to be rewardable at length $n-3$ and unawardable at length $n-1$, it must be preceded by a $PP$ before the $LL$.
Thus, accounting for the first string [left branch] again, all the rewardable strings of length $n-1$, except the strings of length $n−4$ followed by $PLL$, can contribute to a rewardable string of length $n$. Thus, this string accounts for a factor of $f[n-1] - f[n-4]$ to $f[n]$.
Thus, the recurring relation becomes:
$$f[n] = 2f[n-1] - f[n-4]$$
I was hoping someone could put this explanation in their own words, because I don't understand this author's. And he has made several typos in his explanation already, so I'm not sure I trust this explanation.
Another thing I don't understand is why the first of the four cases isn't also problematic, since if the $n-5$th and $n-4$th characters were L, then we'd also have an unrewardable string.
Any hints as to untangling the author's explanation would be appreciated. Thank you.
P.S. The author is intentionally ignoring A at this stage, to be considered separately.
combinatorics recurrence-relations
combinatorics recurrence-relations
asked Apr 24 '17 at 22:28
Andrew Cheong
1,20421119
asked Apr 24 '17 at 22:28
Andrew Cheong
1,20421119
edited Nov 20 '18 at 12:19
asked Apr 24 '17 at 22:28
Andrew Cheong
1,20421119
asked Apr 24 '17 at 22:28
Andrew Cheong
1,20421119
asked Apr 24 '17 at 22:28
Andrew Cheong
1,20421119
1,20421119
2
I think you might mean $8$ for $n=2$ since there are $3^n$ possible records for $n$ days, and thus $9$ records for $n=1$, and with $1$ unacceptable record, there would be $8$ acceptable ones.
– Frpzzd
Apr 24 '17 at 22:55
Yes, that's correct, thanks!
– Andrew Cheong
Apr 25 '17 at 4:44
1
In the cold light of day I am still unable to make sense of this author's method. It may be that it does make sense but because of the lack of clarity, it looks possible that some "fudgery" may have been employed to match the desired answer. I know I'm biased, but I've done a few of these types of recurrences and I feel that my method is, by far, the easiest to understand so I'd stick with that for now if I were you. With a few more different examples you may be able to make sense of our author here but it looks a bit of a mess to me.
– N. Shales
Apr 25 '17 at 12:56
1
Thank you very much, I'll contact the author from here to try to find out what he meant to convey.
– Andrew Cheong
Apr 26 '17 at 8:11
FYI this is equivalent to problem 191 in project Euler. (there the role of L and A are swapped.) projecteuler.net/problem=191 If you bother to write the code to solve that problem numerically, then you can access their forum to see lots more DIFFERENT recurrences people used to solve this. however IMHO the accepted answer has one of the cleanest explanations.
– antkam
Nov 20 '18 at 14:09
add a comment |
2
I think you might mean $8$ for $n=2$ since there are $3^n$ possible records for $n$ days, and thus $9$ records for $n=1$, and with $1$ unacceptable record, there would be $8$ acceptable ones.
– Frpzzd
Apr 24 '17 at 22:55
Yes, that's correct, thanks!
– Andrew Cheong
Apr 25 '17 at 4:44
1
In the cold light of day I am still unable to make sense of this author's method. It may be that it does make sense but because of the lack of clarity, it looks possible that some "fudgery" may have been employed to match the desired answer. I know I'm biased, but I've done a few of these types of recurrences and I feel that my method is, by far, the easiest to understand so I'd stick with that for now if I were you. With a few more different examples you may be able to make sense of our author here but it looks a bit of a mess to me.
– N. Shales
Apr 25 '17 at 12:56
1
Thank you very much, I'll contact the author from here to try to find out what he meant to convey.
– Andrew Cheong
Apr 26 '17 at 8:11
FYI this is equivalent to problem 191 in project Euler. (there the role of L and A are swapped.) projecteuler.net/problem=191 If you bother to write the code to solve that problem numerically, then you can access their forum to see lots more DIFFERENT recurrences people used to solve this. however IMHO the accepted answer has one of the cleanest explanations.
– antkam
Nov 20 '18 at 14:09
2
2
I think you might mean $8$ for $n=2$ since there are $3^n$ possible records for $n$ days, and thus $9$ records for $n=1$, and with $1$ unacceptable record, there would be $8$ acceptable ones.
– Frpzzd
Apr 24 '17 at 22:55
I think you might mean $8$ for $n=2$ since there are $3^n$ possible records for $n$ days, and thus $9$ records for $n=1$, and with $1$ unacceptable record, there would be $8$ acceptable ones.
– Frpzzd
Apr 24 '17 at 22:55
Yes, that's correct, thanks!
– Andrew Cheong
Apr 25 '17 at 4:44
Yes, that's correct, thanks!
– Andrew Cheong
Apr 25 '17 at 4:44
1
1
In the cold light of day I am still unable to make sense of this author's method. It may be that it does make sense but because of the lack of clarity, it looks possible that some "fudgery" may have been employed to match the desired answer. I know I'm biased, but I've done a few of these types of recurrences and I feel that my method is, by far, the easiest to understand so I'd stick with that for now if I were you. With a few more different examples you may be able to make sense of our author here but it looks a bit of a mess to me.
– N. Shales
Apr 25 '17 at 12:56
In the cold light of day I am still unable to make sense of this author's method. It may be that it does make sense but because of the lack of clarity, it looks possible that some "fudgery" may have been employed to match the desired answer. I know I'm biased, but I've done a few of these types of recurrences and I feel that my method is, by far, the easiest to understand so I'd stick with that for now if I were you. With a few more different examples you may be able to make sense of our author here but it looks a bit of a mess to me.
– N. Shales
Apr 25 '17 at 12:56
1
1
Thank you very much, I'll contact the author from here to try to find out what he meant to convey.
– Andrew Cheong
Apr 26 '17 at 8:11
Thank you very much, I'll contact the author from here to try to find out what he meant to convey.
– Andrew Cheong
Apr 26 '17 at 8:11
FYI this is equivalent to problem 191 in project Euler. (there the role of L and A are swapped.) projecteuler.net/problem=191 If you bother to write the code to solve that problem numerically, then you can access their forum to see lots more DIFFERENT recurrences people used to solve this. however IMHO the accepted answer has one of the cleanest explanations.
– antkam
Nov 20 '18 at 14:09
FYI this is equivalent to problem 191 in project Euler. (there the role of L and A are swapped.) projecteuler.net/problem=191 If you bother to write the code to solve that problem numerically, then you can access their forum to see lots more DIFFERENT recurrences people used to solve this. however IMHO the accepted answer has one of the cleanest explanations.
– antkam
Nov 20 '18 at 14:09
add a comment |
1 Answer
1
active
oldest
votes
It really is a lot easier than the author makes out.
You have $3$ possible mutually exclusive and exhaustive endings to valid sequences of length $n$
$$(text{valid sequence length $n-1$}), text{P}$$
$$(text{valid sequence length $n-2$}), text{PL}$$
$$(text{valid sequence length $n-3$}), text{PLL}$$
or, in other words
$$f[n]=f[n-1]+f[n-2]+f[n-3]tag{Answer 1}$$
with $f[0]=1,, f[1]=2,, f[2]=2^2=4$.
But since
$$f[n-1]=f[n-2]+f[n-3]+f[n-4]$$
we have
$$f[n]=2f[n-1]-f[n-4]tag{Answer 2}$$
with the extra initial value $f[3]=2^2+2+1=7$.
The overall answer (including the possibility of an absence) will be
$$f[n]+sum_{k=1}^{n}f[k-1]f[n-k]$$
because there are $f[n]$ valid sequences with no absence and $sum_{k=1}^{n}f[k-1]f[n-k]$ sequences with $1$ absence (the absence A can be in positions $k=1ldots n$ with a valid sequence of Ps and Ls either side of the A).
answered Apr 25 '17 at 1:47
N. Shales
3,2431816
Great, thank you. This explanation was perfectly clear and the final answer matches the working solution. Still, were you able to see whether the author's explanation was indeed correct as well? I ask because, I began to suspect it was wrong, and the author was simply trying to fit his own explanation for the Answer 2 formula he actually copied from somewhere else. I don't see how his approach is correct.
– Andrew Cheong
Apr 25 '17 at 4:07
@AndrewCheong, I have to admit that I only scanned the author's method but it looked a bit over-complicated to me. Still the answer given agrees with mine so it must be right ;) On closer inspection though I'm still not sure, it looks like he did something similar to me but ... hmmm ... no can't see it. Perhaps I'll take another look tomorrow...
– N. Shales
Apr 25 '17 at 4:24
Thank you again for taking an extra look. Where can I find more information on why it's proper to setf[0] = 1? Is this typical (or a rule) in recurrence relations? Perhaps related to exponents never resulting in 0?
– Andrew Cheong
Apr 28 '17 at 14:49
1
@AndrewCheong. It is convention to have an empty sequence (unless your conditions state explicitly that, say the sequences must be a certain length $gt 0$). By setting $f[0]=1$ we can calculate $f[3]$ from the recurrence $f[3]=f[2]+f[1]+f[0]$. The $f[0]$ term accounts for the sequence $(text{valid sequence of length $0$}) text{PLL}$ or just $text{PLL}$. If we start with $f[1]$ then we need to state $f[1]$, $f[2]$ and $f[3]$ as initial conditions. But calculating $f[3]$ requires us to use the recurrence anyway by adding the single case of $text{PLL}$ to $f[1]+f[2]$.
– N. Shales
Apr 28 '17 at 15:46
1
very clear answer +1 much better than the official answer :) or most alternatives in projecteuler.net/problem=191 (an equivalent problem)
– antkam
Nov 20 '18 at 14:05
|
show 1 more 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%2f2250558%2frecurrence-relation-in-a-student-attendance-problem%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
It really is a lot easier than the author makes out.
You have $3$ possible mutually exclusive and exhaustive endings to valid sequences of length $n$
$$(text{valid sequence length $n-1$}), text{P}$$
$$(text{valid sequence length $n-2$}), text{PL}$$
$$(text{valid sequence length $n-3$}), text{PLL}$$
or, in other words
$$f[n]=f[n-1]+f[n-2]+f[n-3]tag{Answer 1}$$
with $f[0]=1,, f[1]=2,, f[2]=2^2=4$.
But since
$$f[n-1]=f[n-2]+f[n-3]+f[n-4]$$
we have
$$f[n]=2f[n-1]-f[n-4]tag{Answer 2}$$
with the extra initial value $f[3]=2^2+2+1=7$.
The overall answer (including the possibility of an absence) will be
$$f[n]+sum_{k=1}^{n}f[k-1]f[n-k]$$
because there are $f[n]$ valid sequences with no absence and $sum_{k=1}^{n}f[k-1]f[n-k]$ sequences with $1$ absence (the absence A can be in positions $k=1ldots n$ with a valid sequence of Ps and Ls either side of the A).
answered Apr 25 '17 at 1:47
N. Shales
3,2431816
Great, thank you. This explanation was perfectly clear and the final answer matches the working solution. Still, were you able to see whether the author's explanation was indeed correct as well? I ask because, I began to suspect it was wrong, and the author was simply trying to fit his own explanation for the Answer 2 formula he actually copied from somewhere else. I don't see how his approach is correct.
– Andrew Cheong
Apr 25 '17 at 4:07
@AndrewCheong, I have to admit that I only scanned the author's method but it looked a bit over-complicated to me. Still the answer given agrees with mine so it must be right ;) On closer inspection though I'm still not sure, it looks like he did something similar to me but ... hmmm ... no can't see it. Perhaps I'll take another look tomorrow...
– N. Shales
Apr 25 '17 at 4:24
Thank you again for taking an extra look. Where can I find more information on why it's proper to setf[0] = 1? Is this typical (or a rule) in recurrence relations? Perhaps related to exponents never resulting in 0?
– Andrew Cheong
Apr 28 '17 at 14:49
1
@AndrewCheong. It is convention to have an empty sequence (unless your conditions state explicitly that, say the sequences must be a certain length $gt 0$). By setting $f[0]=1$ we can calculate $f[3]$ from the recurrence $f[3]=f[2]+f[1]+f[0]$. The $f[0]$ term accounts for the sequence $(text{valid sequence of length $0$}) text{PLL}$ or just $text{PLL}$. If we start with $f[1]$ then we need to state $f[1]$, $f[2]$ and $f[3]$ as initial conditions. But calculating $f[3]$ requires us to use the recurrence anyway by adding the single case of $text{PLL}$ to $f[1]+f[2]$.
– N. Shales
Apr 28 '17 at 15:46
1
very clear answer +1 much better than the official answer :) or most alternatives in projecteuler.net/problem=191 (an equivalent problem)
– antkam
Nov 20 '18 at 14:05
|
show 1 more comment
It really is a lot easier than the author makes out.
You have $3$ possible mutually exclusive and exhaustive endings to valid sequences of length $n$
$$(text{valid sequence length $n-1$}), text{P}$$
$$(text{valid sequence length $n-2$}), text{PL}$$
$$(text{valid sequence length $n-3$}), text{PLL}$$
or, in other words
$$f[n]=f[n-1]+f[n-2]+f[n-3]tag{Answer 1}$$
with $f[0]=1,, f[1]=2,, f[2]=2^2=4$.
But since
$$f[n-1]=f[n-2]+f[n-3]+f[n-4]$$
we have
$$f[n]=2f[n-1]-f[n-4]tag{Answer 2}$$
with the extra initial value $f[3]=2^2+2+1=7$.
The overall answer (including the possibility of an absence) will be
$$f[n]+sum_{k=1}^{n}f[k-1]f[n-k]$$
because there are $f[n]$ valid sequences with no absence and $sum_{k=1}^{n}f[k-1]f[n-k]$ sequences with $1$ absence (the absence A can be in positions $k=1ldots n$ with a valid sequence of Ps and Ls either side of the A).
answered Apr 25 '17 at 1:47
N. Shales
3,2431816
Great, thank you. This explanation was perfectly clear and the final answer matches the working solution. Still, were you able to see whether the author's explanation was indeed correct as well? I ask because, I began to suspect it was wrong, and the author was simply trying to fit his own explanation for the Answer 2 formula he actually copied from somewhere else. I don't see how his approach is correct.
– Andrew Cheong
Apr 25 '17 at 4:07
@AndrewCheong, I have to admit that I only scanned the author's method but it looked a bit over-complicated to me. Still the answer given agrees with mine so it must be right ;) On closer inspection though I'm still not sure, it looks like he did something similar to me but ... hmmm ... no can't see it. Perhaps I'll take another look tomorrow...
– N. Shales
Apr 25 '17 at 4:24
Thank you again for taking an extra look. Where can I find more information on why it's proper to setf[0] = 1? Is this typical (or a rule) in recurrence relations? Perhaps related to exponents never resulting in 0?
– Andrew Cheong
Apr 28 '17 at 14:49
1
@AndrewCheong. It is convention to have an empty sequence (unless your conditions state explicitly that, say the sequences must be a certain length $gt 0$). By setting $f[0]=1$ we can calculate $f[3]$ from the recurrence $f[3]=f[2]+f[1]+f[0]$. The $f[0]$ term accounts for the sequence $(text{valid sequence of length $0$}) text{PLL}$ or just $text{PLL}$. If we start with $f[1]$ then we need to state $f[1]$, $f[2]$ and $f[3]$ as initial conditions. But calculating $f[3]$ requires us to use the recurrence anyway by adding the single case of $text{PLL}$ to $f[1]+f[2]$.
– N. Shales
Apr 28 '17 at 15:46
1
very clear answer +1 much better than the official answer :) or most alternatives in projecteuler.net/problem=191 (an equivalent problem)
– antkam
Nov 20 '18 at 14:05
|
show 1 more comment
It really is a lot easier than the author makes out.
You have $3$ possible mutually exclusive and exhaustive endings to valid sequences of length $n$
$$(text{valid sequence length $n-1$}), text{P}$$
$$(text{valid sequence length $n-2$}), text{PL}$$
$$(text{valid sequence length $n-3$}), text{PLL}$$
or, in other words
$$f[n]=f[n-1]+f[n-2]+f[n-3]tag{Answer 1}$$
with $f[0]=1,, f[1]=2,, f[2]=2^2=4$.
But since
$$f[n-1]=f[n-2]+f[n-3]+f[n-4]$$
we have
$$f[n]=2f[n-1]-f[n-4]tag{Answer 2}$$
with the extra initial value $f[3]=2^2+2+1=7$.
The overall answer (including the possibility of an absence) will be
$$f[n]+sum_{k=1}^{n}f[k-1]f[n-k]$$
because there are $f[n]$ valid sequences with no absence and $sum_{k=1}^{n}f[k-1]f[n-k]$ sequences with $1$ absence (the absence A can be in positions $k=1ldots n$ with a valid sequence of Ps and Ls either side of the A).
answered Apr 25 '17 at 1:47
N. Shales
3,2431816
It really is a lot easier than the author makes out.
You have $3$ possible mutually exclusive and exhaustive endings to valid sequences of length $n$
$$(text{valid sequence length $n-1$}), text{P}$$
$$(text{valid sequence length $n-2$}), text{PL}$$
$$(text{valid sequence length $n-3$}), text{PLL}$$
or, in other words
$$f[n]=f[n-1]+f[n-2]+f[n-3]tag{Answer 1}$$
with $f[0]=1,, f[1]=2,, f[2]=2^2=4$.
But since
$$f[n-1]=f[n-2]+f[n-3]+f[n-4]$$
we have
$$f[n]=2f[n-1]-f[n-4]tag{Answer 2}$$
with the extra initial value $f[3]=2^2+2+1=7$.
The overall answer (including the possibility of an absence) will be
$$f[n]+sum_{k=1}^{n}f[k-1]f[n-k]$$
because there are $f[n]$ valid sequences with no absence and $sum_{k=1}^{n}f[k-1]f[n-k]$ sequences with $1$ absence (the absence A can be in positions $k=1ldots n$ with a valid sequence of Ps and Ls either side of the A).
answered Apr 25 '17 at 1:47
N. Shales
3,2431816
answered Apr 25 '17 at 1:47
N. Shales
3,2431816
answered Apr 25 '17 at 1:47
N. Shales
3,2431816
answered Apr 25 '17 at 1:47
N. Shales
3,2431816
3,2431816
Great, thank you. This explanation was perfectly clear and the final answer matches the working solution. Still, were you able to see whether the author's explanation was indeed correct as well? I ask because, I began to suspect it was wrong, and the author was simply trying to fit his own explanation for the Answer 2 formula he actually copied from somewhere else. I don't see how his approach is correct.
– Andrew Cheong
Apr 25 '17 at 4:07
@AndrewCheong, I have to admit that I only scanned the author's method but it looked a bit over-complicated to me. Still the answer given agrees with mine so it must be right ;) On closer inspection though I'm still not sure, it looks like he did something similar to me but ... hmmm ... no can't see it. Perhaps I'll take another look tomorrow...
– N. Shales
Apr 25 '17 at 4:24
Thank you again for taking an extra look. Where can I find more information on why it's proper to setf[0] = 1? Is this typical (or a rule) in recurrence relations? Perhaps related to exponents never resulting in 0?
– Andrew Cheong
Apr 28 '17 at 14:49
1
@AndrewCheong. It is convention to have an empty sequence (unless your conditions state explicitly that, say the sequences must be a certain length $gt 0$). By setting $f[0]=1$ we can calculate $f[3]$ from the recurrence $f[3]=f[2]+f[1]+f[0]$. The $f[0]$ term accounts for the sequence $(text{valid sequence of length $0$}) text{PLL}$ or just $text{PLL}$. If we start with $f[1]$ then we need to state $f[1]$, $f[2]$ and $f[3]$ as initial conditions. But calculating $f[3]$ requires us to use the recurrence anyway by adding the single case of $text{PLL}$ to $f[1]+f[2]$.
– N. Shales
Apr 28 '17 at 15:46
1
very clear answer +1 much better than the official answer :) or most alternatives in projecteuler.net/problem=191 (an equivalent problem)
– antkam
Nov 20 '18 at 14:05
|
show 1 more comment
Great, thank you. This explanation was perfectly clear and the final answer matches the working solution. Still, were you able to see whether the author's explanation was indeed correct as well? I ask because, I began to suspect it was wrong, and the author was simply trying to fit his own explanation for the Answer 2 formula he actually copied from somewhere else. I don't see how his approach is correct.
– Andrew Cheong
Apr 25 '17 at 4:07
@AndrewCheong, I have to admit that I only scanned the author's method but it looked a bit over-complicated to me. Still the answer given agrees with mine so it must be right ;) On closer inspection though I'm still not sure, it looks like he did something similar to me but ... hmmm ... no can't see it. Perhaps I'll take another look tomorrow...
– N. Shales
Apr 25 '17 at 4:24
Thank you again for taking an extra look. Where can I find more information on why it's proper to setf[0] = 1? Is this typical (or a rule) in recurrence relations? Perhaps related to exponents never resulting in 0?
– Andrew Cheong
Apr 28 '17 at 14:49
1
@AndrewCheong. It is convention to have an empty sequence (unless your conditions state explicitly that, say the sequences must be a certain length $gt 0$). By setting $f[0]=1$ we can calculate $f[3]$ from the recurrence $f[3]=f[2]+f[1]+f[0]$. The $f[0]$ term accounts for the sequence $(text{valid sequence of length $0$}) text{PLL}$ or just $text{PLL}$. If we start with $f[1]$ then we need to state $f[1]$, $f[2]$ and $f[3]$ as initial conditions. But calculating $f[3]$ requires us to use the recurrence anyway by adding the single case of $text{PLL}$ to $f[1]+f[2]$.
– N. Shales
Apr 28 '17 at 15:46
1
very clear answer +1 much better than the official answer :) or most alternatives in projecteuler.net/problem=191 (an equivalent problem)
– antkam
Nov 20 '18 at 14:05
Great, thank you. This explanation was perfectly clear and the final answer matches the working solution. Still, were you able to see whether the author's explanation was indeed correct as well? I ask because, I began to suspect it was wrong, and the author was simply trying to fit his own explanation for the Answer 2 formula he actually copied from somewhere else. I don't see how his approach is correct.
– Andrew Cheong
Apr 25 '17 at 4:07
Great, thank you. This explanation was perfectly clear and the final answer matches the working solution. Still, were you able to see whether the author's explanation was indeed correct as well? I ask because, I began to suspect it was wrong, and the author was simply trying to fit his own explanation for the Answer 2 formula he actually copied from somewhere else. I don't see how his approach is correct.
– Andrew Cheong
Apr 25 '17 at 4:07
@AndrewCheong, I have to admit that I only scanned the author's method but it looked a bit over-complicated to me. Still the answer given agrees with mine so it must be right ;) On closer inspection though I'm still not sure, it looks like he did something similar to me but ... hmmm ... no can't see it. Perhaps I'll take another look tomorrow...
– N. Shales
Apr 25 '17 at 4:24
@AndrewCheong, I have to admit that I only scanned the author's method but it looked a bit over-complicated to me. Still the answer given agrees with mine so it must be right ;) On closer inspection though I'm still not sure, it looks like he did something similar to me but ... hmmm ... no can't see it. Perhaps I'll take another look tomorrow...
– N. Shales
Apr 25 '17 at 4:24
Thank you again for taking an extra look. Where can I find more information on why it's proper to set
f[0] = 1? Is this typical (or a rule) in recurrence relations? Perhaps related to exponents never resulting in 0?– Andrew Cheong
Apr 28 '17 at 14:49
Thank you again for taking an extra look. Where can I find more information on why it's proper to set
f[0] = 1? Is this typical (or a rule) in recurrence relations? Perhaps related to exponents never resulting in 0?– Andrew Cheong
Apr 28 '17 at 14:49
1
1
@AndrewCheong. It is convention to have an empty sequence (unless your conditions state explicitly that, say the sequences must be a certain length $gt 0$). By setting $f[0]=1$ we can calculate $f[3]$ from the recurrence $f[3]=f[2]+f[1]+f[0]$. The $f[0]$ term accounts for the sequence $(text{valid sequence of length $0$}) text{PLL}$ or just $text{PLL}$. If we start with $f[1]$ then we need to state $f[1]$, $f[2]$ and $f[3]$ as initial conditions. But calculating $f[3]$ requires us to use the recurrence anyway by adding the single case of $text{PLL}$ to $f[1]+f[2]$.
– N. Shales
Apr 28 '17 at 15:46
@AndrewCheong. It is convention to have an empty sequence (unless your conditions state explicitly that, say the sequences must be a certain length $gt 0$). By setting $f[0]=1$ we can calculate $f[3]$ from the recurrence $f[3]=f[2]+f[1]+f[0]$. The $f[0]$ term accounts for the sequence $(text{valid sequence of length $0$}) text{PLL}$ or just $text{PLL}$. If we start with $f[1]$ then we need to state $f[1]$, $f[2]$ and $f[3]$ as initial conditions. But calculating $f[3]$ requires us to use the recurrence anyway by adding the single case of $text{PLL}$ to $f[1]+f[2]$.
– N. Shales
Apr 28 '17 at 15:46
1
1
very clear answer +1 much better than the official answer :) or most alternatives in projecteuler.net/problem=191 (an equivalent problem)
– antkam
Nov 20 '18 at 14:05
very clear answer +1 much better than the official answer :) or most alternatives in projecteuler.net/problem=191 (an equivalent problem)
– antkam
Nov 20 '18 at 14:05
|
show 1 more 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%2f2250558%2frecurrence-relation-in-a-student-attendance-problem%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
2
I think you might mean $8$ for $n=2$ since there are $3^n$ possible records for $n$ days, and thus $9$ records for $n=1$, and with $1$ unacceptable record, there would be $8$ acceptable ones.
– Frpzzd
Apr 24 '17 at 22:55
Yes, that's correct, thanks!
– Andrew Cheong
Apr 25 '17 at 4:44
1
In the cold light of day I am still unable to make sense of this author's method. It may be that it does make sense but because of the lack of clarity, it looks possible that some "fudgery" may have been employed to match the desired answer. I know I'm biased, but I've done a few of these types of recurrences and I feel that my method is, by far, the easiest to understand so I'd stick with that for now if I were you. With a few more different examples you may be able to make sense of our author here but it looks a bit of a mess to me.
– N. Shales
Apr 25 '17 at 12:56
1
Thank you very much, I'll contact the author from here to try to find out what he meant to convey.
– Andrew Cheong
Apr 26 '17 at 8:11
FYI this is equivalent to problem 191 in project Euler. (there the role of L and A are swapped.) projecteuler.net/problem=191 If you bother to write the code to solve that problem numerically, then you can access their forum to see lots more DIFFERENT recurrences people used to solve this. however IMHO the accepted answer has one of the cleanest explanations.
– antkam
Nov 20 '18 at 14:09