Mixing
Discrete Math - Recursion
When I read this question, I have no idea how to approach it. Can someone break down the steps to solving this question?
Let $Σ = {a, b, c}$. Find a recurrence for the number of length $n$ strings in $Σ^∗$ that do not contain any two consecutive $a$’s, $b$’s, nor c’s (i.e. none of $aa$, $bb$, nor $cc$ are in the string).
So this is what I have done so far:
My Work
I have completed the problem and here is the solution:
My Solution
THANK YOU to everyone who helped, or even looked at this post. Special kudos to @JMoravitz for his kind help!
discrete-mathematics recurrence-relations
asked Nov 20 '18 at 2:48
Bob.C
112
|
show 9 more comments
When I read this question, I have no idea how to approach it. Can someone break down the steps to solving this question?
Let $Σ = {a, b, c}$. Find a recurrence for the number of length $n$ strings in $Σ^∗$ that do not contain any two consecutive $a$’s, $b$’s, nor c’s (i.e. none of $aa$, $bb$, nor $cc$ are in the string).
So this is what I have done so far:
My Work
I have completed the problem and here is the solution:
My Solution
THANK YOU to everyone who helped, or even looked at this post. Special kudos to @JMoravitz for his kind help!
discrete-mathematics recurrence-relations
asked Nov 20 '18 at 2:48
Bob.C
112
Tianlalu, what was the edit?
– Bob.C
Nov 20 '18 at 2:52
It is Mathjax.
– Tianlalu
Nov 20 '18 at 2:56
1
Notice... There are three length $1$ strings (and one length $0$ string). The final character of any string of length greater than $1$ must be different than the character just before it. Worded differently, given a string of a particular length, if you want to extend it to be one character longer, you can append either of the two available characters to the end.
– JMoravitz
Nov 20 '18 at 2:58
@JMoravitz I completely understand what you mean. So in that case we can just keep adding a different character and make a new string. Therefore, we could keep going to infinity. But how would I go about this specific problem.
– Bob.C
Nov 20 '18 at 3:06
1
If you have $f(n)$ number of strings of length $n$... can you come up with a relationship between $f(n)$ and $f(n+1)$? If you have... say... $12$ strings of length $3$... how many strings would there be of length $4$ knowing this and knowing that any string of length $3$ may be turned into a string of length $4$ in two different ways by tacking on an extra character at the end?
– JMoravitz
Nov 20 '18 at 3:17
|
show 9 more comments
When I read this question, I have no idea how to approach it. Can someone break down the steps to solving this question?
Let $Σ = {a, b, c}$. Find a recurrence for the number of length $n$ strings in $Σ^∗$ that do not contain any two consecutive $a$’s, $b$’s, nor c’s (i.e. none of $aa$, $bb$, nor $cc$ are in the string).
So this is what I have done so far:
My Work
I have completed the problem and here is the solution:
My Solution
THANK YOU to everyone who helped, or even looked at this post. Special kudos to @JMoravitz for his kind help!
discrete-mathematics recurrence-relations
asked Nov 20 '18 at 2:48
Bob.C
112
When I read this question, I have no idea how to approach it. Can someone break down the steps to solving this question?
Let $Σ = {a, b, c}$. Find a recurrence for the number of length $n$ strings in $Σ^∗$ that do not contain any two consecutive $a$’s, $b$’s, nor c’s (i.e. none of $aa$, $bb$, nor $cc$ are in the string).
So this is what I have done so far:
My Work
I have completed the problem and here is the solution:
My Solution
THANK YOU to everyone who helped, or even looked at this post. Special kudos to @JMoravitz for his kind help!
discrete-mathematics recurrence-relations
discrete-mathematics recurrence-relations
asked Nov 20 '18 at 2:48
Bob.C
112
asked Nov 20 '18 at 2:48
Bob.C
112
edited Nov 20 '18 at 4:20
asked Nov 20 '18 at 2:48
Bob.C
112
asked Nov 20 '18 at 2:48
Bob.C
112
asked Nov 20 '18 at 2:48
Bob.C
112
112
Tianlalu, what was the edit?
– Bob.C
Nov 20 '18 at 2:52
It is Mathjax.
– Tianlalu
Nov 20 '18 at 2:56
1
Notice... There are three length $1$ strings (and one length $0$ string). The final character of any string of length greater than $1$ must be different than the character just before it. Worded differently, given a string of a particular length, if you want to extend it to be one character longer, you can append either of the two available characters to the end.
– JMoravitz
Nov 20 '18 at 2:58
@JMoravitz I completely understand what you mean. So in that case we can just keep adding a different character and make a new string. Therefore, we could keep going to infinity. But how would I go about this specific problem.
– Bob.C
Nov 20 '18 at 3:06
1
If you have $f(n)$ number of strings of length $n$... can you come up with a relationship between $f(n)$ and $f(n+1)$? If you have... say... $12$ strings of length $3$... how many strings would there be of length $4$ knowing this and knowing that any string of length $3$ may be turned into a string of length $4$ in two different ways by tacking on an extra character at the end?
– JMoravitz
Nov 20 '18 at 3:17
|
show 9 more comments
Tianlalu, what was the edit?
– Bob.C
Nov 20 '18 at 2:52
It is Mathjax.
– Tianlalu
Nov 20 '18 at 2:56
1
Notice... There are three length $1$ strings (and one length $0$ string). The final character of any string of length greater than $1$ must be different than the character just before it. Worded differently, given a string of a particular length, if you want to extend it to be one character longer, you can append either of the two available characters to the end.
– JMoravitz
Nov 20 '18 at 2:58
@JMoravitz I completely understand what you mean. So in that case we can just keep adding a different character and make a new string. Therefore, we could keep going to infinity. But how would I go about this specific problem.
– Bob.C
Nov 20 '18 at 3:06
1
If you have $f(n)$ number of strings of length $n$... can you come up with a relationship between $f(n)$ and $f(n+1)$? If you have... say... $12$ strings of length $3$... how many strings would there be of length $4$ knowing this and knowing that any string of length $3$ may be turned into a string of length $4$ in two different ways by tacking on an extra character at the end?
– JMoravitz
Nov 20 '18 at 3:17
Tianlalu, what was the edit?
– Bob.C
Nov 20 '18 at 2:52
Tianlalu, what was the edit?
– Bob.C
Nov 20 '18 at 2:52
It is Mathjax.
– Tianlalu
Nov 20 '18 at 2:56
It is Mathjax.
– Tianlalu
Nov 20 '18 at 2:56
1
1
Notice... There are three length $1$ strings (and one length $0$ string). The final character of any string of length greater than $1$ must be different than the character just before it. Worded differently, given a string of a particular length, if you want to extend it to be one character longer, you can append either of the two available characters to the end.
– JMoravitz
Nov 20 '18 at 2:58
Notice... There are three length $1$ strings (and one length $0$ string). The final character of any string of length greater than $1$ must be different than the character just before it. Worded differently, given a string of a particular length, if you want to extend it to be one character longer, you can append either of the two available characters to the end.
– JMoravitz
Nov 20 '18 at 2:58
@JMoravitz I completely understand what you mean. So in that case we can just keep adding a different character and make a new string. Therefore, we could keep going to infinity. But how would I go about this specific problem.
– Bob.C
Nov 20 '18 at 3:06
@JMoravitz I completely understand what you mean. So in that case we can just keep adding a different character and make a new string. Therefore, we could keep going to infinity. But how would I go about this specific problem.
– Bob.C
Nov 20 '18 at 3:06
1
1
If you have $f(n)$ number of strings of length $n$... can you come up with a relationship between $f(n)$ and $f(n+1)$? If you have... say... $12$ strings of length $3$... how many strings would there be of length $4$ knowing this and knowing that any string of length $3$ may be turned into a string of length $4$ in two different ways by tacking on an extra character at the end?
– JMoravitz
Nov 20 '18 at 3:17
If you have $f(n)$ number of strings of length $n$... can you come up with a relationship between $f(n)$ and $f(n+1)$? If you have... say... $12$ strings of length $3$... how many strings would there be of length $4$ knowing this and knowing that any string of length $3$ may be turned into a string of length $4$ in two different ways by tacking on an extra character at the end?
– JMoravitz
Nov 20 '18 at 3:17
|
show 9 more comments
1 Answer
1
active
oldest
votes
You have three valid strings of length $1$. They are namely $a,b,c$. For each of these, there are two possible ways to continue them into a length $2$ string:
$$a mapsto begin{cases} ab\acend{cases}$$
$$bmapsto begin{cases} ba\bcend{cases}$$
$$cmapsto begin{cases} ca\cbend{cases}$$
Now... for each of these six length two strings there are two ways to continue each into a length three string:
$$abmapstobegin{cases}aba\abcend{cases}$$
$$acmapstobegin{cases}aca\acbend{cases}$$
$$bamapstobegin{cases}bab\bacend{cases}$$
$$vdots$$
Notice, in the above process, there are no repeats. Convince yourself of this.
In general, given a valid length $n$ string, we may extend it in two ways to make a valid length $n+1$ string.
Convince yourself that every valid length $n+1$ string is uniquely comprised of a prefix made of a length $n$ string followed by suffix made of a single character which is different than the final character of the prefix.
Convince yourself then that supposing we know the number of valid length $n$ strings is $f(n)$, we can use this information and this information alone to calculate $f(n+1)$.
(There is one valid length $0$ string). There are three length $1$ strings. There are six length $2$ strings. There are twelve length $3$ strings, etc...
$~$
You are tasked with coming up with an equation for $f(n+1)$ which depends only on the value of $f(n)$ (or in some later problems it could also depend on $f(n-1),f(n-2),dots$) and possibly some constants. Additionally, if you are tasked with it, you might be further asked to find a closed form for the function which avoids the necessity of referring to earlier values.
answered Nov 20 '18 at 3:40
JMoravitz
46.4k33785
This makes so much sense! Thank you!
– Bob.C
Nov 20 '18 at 3:46
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%2f3005872%2fdiscrete-math-recursion%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
You have three valid strings of length $1$. They are namely $a,b,c$. For each of these, there are two possible ways to continue them into a length $2$ string:
$$a mapsto begin{cases} ab\acend{cases}$$
$$bmapsto begin{cases} ba\bcend{cases}$$
$$cmapsto begin{cases} ca\cbend{cases}$$
Now... for each of these six length two strings there are two ways to continue each into a length three string:
$$abmapstobegin{cases}aba\abcend{cases}$$
$$acmapstobegin{cases}aca\acbend{cases}$$
$$bamapstobegin{cases}bab\bacend{cases}$$
$$vdots$$
Notice, in the above process, there are no repeats. Convince yourself of this.
In general, given a valid length $n$ string, we may extend it in two ways to make a valid length $n+1$ string.
Convince yourself that every valid length $n+1$ string is uniquely comprised of a prefix made of a length $n$ string followed by suffix made of a single character which is different than the final character of the prefix.
Convince yourself then that supposing we know the number of valid length $n$ strings is $f(n)$, we can use this information and this information alone to calculate $f(n+1)$.
(There is one valid length $0$ string). There are three length $1$ strings. There are six length $2$ strings. There are twelve length $3$ strings, etc...
$~$
You are tasked with coming up with an equation for $f(n+1)$ which depends only on the value of $f(n)$ (or in some later problems it could also depend on $f(n-1),f(n-2),dots$) and possibly some constants. Additionally, if you are tasked with it, you might be further asked to find a closed form for the function which avoids the necessity of referring to earlier values.
answered Nov 20 '18 at 3:40
JMoravitz
46.4k33785
This makes so much sense! Thank you!
– Bob.C
Nov 20 '18 at 3:46
add a comment |
You have three valid strings of length $1$. They are namely $a,b,c$. For each of these, there are two possible ways to continue them into a length $2$ string:
$$a mapsto begin{cases} ab\acend{cases}$$
$$bmapsto begin{cases} ba\bcend{cases}$$
$$cmapsto begin{cases} ca\cbend{cases}$$
Now... for each of these six length two strings there are two ways to continue each into a length three string:
$$abmapstobegin{cases}aba\abcend{cases}$$
$$acmapstobegin{cases}aca\acbend{cases}$$
$$bamapstobegin{cases}bab\bacend{cases}$$
$$vdots$$
Notice, in the above process, there are no repeats. Convince yourself of this.
In general, given a valid length $n$ string, we may extend it in two ways to make a valid length $n+1$ string.
Convince yourself that every valid length $n+1$ string is uniquely comprised of a prefix made of a length $n$ string followed by suffix made of a single character which is different than the final character of the prefix.
Convince yourself then that supposing we know the number of valid length $n$ strings is $f(n)$, we can use this information and this information alone to calculate $f(n+1)$.
(There is one valid length $0$ string). There are three length $1$ strings. There are six length $2$ strings. There are twelve length $3$ strings, etc...
$~$
You are tasked with coming up with an equation for $f(n+1)$ which depends only on the value of $f(n)$ (or in some later problems it could also depend on $f(n-1),f(n-2),dots$) and possibly some constants. Additionally, if you are tasked with it, you might be further asked to find a closed form for the function which avoids the necessity of referring to earlier values.
answered Nov 20 '18 at 3:40
JMoravitz
46.4k33785
This makes so much sense! Thank you!
– Bob.C
Nov 20 '18 at 3:46
add a comment |
You have three valid strings of length $1$. They are namely $a,b,c$. For each of these, there are two possible ways to continue them into a length $2$ string:
$$a mapsto begin{cases} ab\acend{cases}$$
$$bmapsto begin{cases} ba\bcend{cases}$$
$$cmapsto begin{cases} ca\cbend{cases}$$
Now... for each of these six length two strings there are two ways to continue each into a length three string:
$$abmapstobegin{cases}aba\abcend{cases}$$
$$acmapstobegin{cases}aca\acbend{cases}$$
$$bamapstobegin{cases}bab\bacend{cases}$$
$$vdots$$
Notice, in the above process, there are no repeats. Convince yourself of this.
In general, given a valid length $n$ string, we may extend it in two ways to make a valid length $n+1$ string.
Convince yourself that every valid length $n+1$ string is uniquely comprised of a prefix made of a length $n$ string followed by suffix made of a single character which is different than the final character of the prefix.
Convince yourself then that supposing we know the number of valid length $n$ strings is $f(n)$, we can use this information and this information alone to calculate $f(n+1)$.
(There is one valid length $0$ string). There are three length $1$ strings. There are six length $2$ strings. There are twelve length $3$ strings, etc...
$~$
You are tasked with coming up with an equation for $f(n+1)$ which depends only on the value of $f(n)$ (or in some later problems it could also depend on $f(n-1),f(n-2),dots$) and possibly some constants. Additionally, if you are tasked with it, you might be further asked to find a closed form for the function which avoids the necessity of referring to earlier values.
answered Nov 20 '18 at 3:40
JMoravitz
46.4k33785
You have three valid strings of length $1$. They are namely $a,b,c$. For each of these, there are two possible ways to continue them into a length $2$ string:
$$a mapsto begin{cases} ab\acend{cases}$$
$$bmapsto begin{cases} ba\bcend{cases}$$
$$cmapsto begin{cases} ca\cbend{cases}$$
Now... for each of these six length two strings there are two ways to continue each into a length three string:
$$abmapstobegin{cases}aba\abcend{cases}$$
$$acmapstobegin{cases}aca\acbend{cases}$$
$$bamapstobegin{cases}bab\bacend{cases}$$
$$vdots$$
Notice, in the above process, there are no repeats. Convince yourself of this.
In general, given a valid length $n$ string, we may extend it in two ways to make a valid length $n+1$ string.
Convince yourself that every valid length $n+1$ string is uniquely comprised of a prefix made of a length $n$ string followed by suffix made of a single character which is different than the final character of the prefix.
Convince yourself then that supposing we know the number of valid length $n$ strings is $f(n)$, we can use this information and this information alone to calculate $f(n+1)$.
(There is one valid length $0$ string). There are three length $1$ strings. There are six length $2$ strings. There are twelve length $3$ strings, etc...
$~$
You are tasked with coming up with an equation for $f(n+1)$ which depends only on the value of $f(n)$ (or in some later problems it could also depend on $f(n-1),f(n-2),dots$) and possibly some constants. Additionally, if you are tasked with it, you might be further asked to find a closed form for the function which avoids the necessity of referring to earlier values.
answered Nov 20 '18 at 3:40
JMoravitz
46.4k33785
answered Nov 20 '18 at 3:40
JMoravitz
46.4k33785
answered Nov 20 '18 at 3:40
JMoravitz
46.4k33785
answered Nov 20 '18 at 3:40
JMoravitz
46.4k33785
46.4k33785
This makes so much sense! Thank you!
– Bob.C
Nov 20 '18 at 3:46
add a comment |
This makes so much sense! Thank you!
– Bob.C
Nov 20 '18 at 3:46
This makes so much sense! Thank you!
– Bob.C
Nov 20 '18 at 3:46
This makes so much sense! Thank you!
– Bob.C
Nov 20 '18 at 3:46
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005872%2fdiscrete-math-recursion%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
Tianlalu, what was the edit?
– Bob.C
Nov 20 '18 at 2:52
It is Mathjax.
– Tianlalu
Nov 20 '18 at 2:56
1
Notice... There are three length $1$ strings (and one length $0$ string). The final character of any string of length greater than $1$ must be different than the character just before it. Worded differently, given a string of a particular length, if you want to extend it to be one character longer, you can append either of the two available characters to the end.
– JMoravitz
Nov 20 '18 at 2:58
@JMoravitz I completely understand what you mean. So in that case we can just keep adding a different character and make a new string. Therefore, we could keep going to infinity. But how would I go about this specific problem.
– Bob.C
Nov 20 '18 at 3:06
1
If you have $f(n)$ number of strings of length $n$... can you come up with a relationship between $f(n)$ and $f(n+1)$? If you have... say... $12$ strings of length $3$... how many strings would there be of length $4$ knowing this and knowing that any string of length $3$ may be turned into a string of length $4$ in two different ways by tacking on an extra character at the end?
– JMoravitz
Nov 20 '18 at 3:17