Mixing
Recursion relation: Number of series length n made of (0,1,2)
$begingroup$
Recursion relation: Number of series length $n$ made of {$0,1,2$} so that in each series there are no two consecutive numbers that are the same, and there isn't $0$ in the middle (for an odd number of numbers).
So I divided it in this way:
$a_n$ is the series for strings in length of $2n+2$.
$b_n$ is the series for strings in lenght of $2n+1$.
$c_n$ is the series for strings in lenght of $n$.
So, for $a_n$ if I set $0$ as a first number, I can set $1$ or $2$ as a second number and then run for all the $a_{n-2}$ options. I do the same process with $1$ and $2$ and in total I will get $a_n=6a_{n-2}$.
For $b_n$, I can see what is the number of possibilities in $a_{n-1}$, and examine the possibilities in the middle:
- If it has $01$,$02$,$10$,$20$ I have exactly 1 option to put a number in between them(so it won't be $0$ and won't be the same as it's neighbors).
- If it has $12$ or $21$ I can't count this possibility.
So I can deduct than $b_n=frac{2}{3}a_{n-1}$
So in total, for $2n+2$ numbers I have $6a_{n-2}+frac{2}{3}a_{n-1}$.
First of all I wanted to ask if I'm at the right direction?
Second, I don't sure how return back to $c_n$. Can I just define $c_n=a_{frac{n}{2}-1}$ and just replace the indexes? Is there a way to simplify the equation?
combinatorics recursion
asked Jan 5 at 9:40
IgorIgor
265
$endgroup$
add a comment |
$begingroup$
Recursion relation: Number of series length $n$ made of {$0,1,2$} so that in each series there are no two consecutive numbers that are the same, and there isn't $0$ in the middle (for an odd number of numbers).
So I divided it in this way:
$a_n$ is the series for strings in length of $2n+2$.
$b_n$ is the series for strings in lenght of $2n+1$.
$c_n$ is the series for strings in lenght of $n$.
So, for $a_n$ if I set $0$ as a first number, I can set $1$ or $2$ as a second number and then run for all the $a_{n-2}$ options. I do the same process with $1$ and $2$ and in total I will get $a_n=6a_{n-2}$.
For $b_n$, I can see what is the number of possibilities in $a_{n-1}$, and examine the possibilities in the middle:
- If it has $01$,$02$,$10$,$20$ I have exactly 1 option to put a number in between them(so it won't be $0$ and won't be the same as it's neighbors).
- If it has $12$ or $21$ I can't count this possibility.
So I can deduct than $b_n=frac{2}{3}a_{n-1}$
So in total, for $2n+2$ numbers I have $6a_{n-2}+frac{2}{3}a_{n-1}$.
First of all I wanted to ask if I'm at the right direction?
Second, I don't sure how return back to $c_n$. Can I just define $c_n=a_{frac{n}{2}-1}$ and just replace the indexes? Is there a way to simplify the equation?
combinatorics recursion
asked Jan 5 at 9:40
IgorIgor
265
$endgroup$
add a comment |
$begingroup$
Recursion relation: Number of series length $n$ made of {$0,1,2$} so that in each series there are no two consecutive numbers that are the same, and there isn't $0$ in the middle (for an odd number of numbers).
So I divided it in this way:
$a_n$ is the series for strings in length of $2n+2$.
$b_n$ is the series for strings in lenght of $2n+1$.
$c_n$ is the series for strings in lenght of $n$.
So, for $a_n$ if I set $0$ as a first number, I can set $1$ or $2$ as a second number and then run for all the $a_{n-2}$ options. I do the same process with $1$ and $2$ and in total I will get $a_n=6a_{n-2}$.
For $b_n$, I can see what is the number of possibilities in $a_{n-1}$, and examine the possibilities in the middle:
- If it has $01$,$02$,$10$,$20$ I have exactly 1 option to put a number in between them(so it won't be $0$ and won't be the same as it's neighbors).
- If it has $12$ or $21$ I can't count this possibility.
So I can deduct than $b_n=frac{2}{3}a_{n-1}$
So in total, for $2n+2$ numbers I have $6a_{n-2}+frac{2}{3}a_{n-1}$.
First of all I wanted to ask if I'm at the right direction?
Second, I don't sure how return back to $c_n$. Can I just define $c_n=a_{frac{n}{2}-1}$ and just replace the indexes? Is there a way to simplify the equation?
combinatorics recursion
asked Jan 5 at 9:40
IgorIgor
265
$endgroup$
Recursion relation: Number of series length $n$ made of {$0,1,2$} so that in each series there are no two consecutive numbers that are the same, and there isn't $0$ in the middle (for an odd number of numbers).
So I divided it in this way:
$a_n$ is the series for strings in length of $2n+2$.
$b_n$ is the series for strings in lenght of $2n+1$.
$c_n$ is the series for strings in lenght of $n$.
So, for $a_n$ if I set $0$ as a first number, I can set $1$ or $2$ as a second number and then run for all the $a_{n-2}$ options. I do the same process with $1$ and $2$ and in total I will get $a_n=6a_{n-2}$.
For $b_n$, I can see what is the number of possibilities in $a_{n-1}$, and examine the possibilities in the middle:
- If it has $01$,$02$,$10$,$20$ I have exactly 1 option to put a number in between them(so it won't be $0$ and won't be the same as it's neighbors).
- If it has $12$ or $21$ I can't count this possibility.
So I can deduct than $b_n=frac{2}{3}a_{n-1}$
So in total, for $2n+2$ numbers I have $6a_{n-2}+frac{2}{3}a_{n-1}$.
First of all I wanted to ask if I'm at the right direction?
Second, I don't sure how return back to $c_n$. Can I just define $c_n=a_{frac{n}{2}-1}$ and just replace the indexes? Is there a way to simplify the equation?
combinatorics recursion
combinatorics recursion
asked Jan 5 at 9:40
IgorIgor
265
asked Jan 5 at 9:40
IgorIgor
265
edited Jan 5 at 10:24
Igor
asked Jan 5 at 9:40
IgorIgor
265
asked Jan 5 at 9:40
IgorIgor
265
asked Jan 5 at 9:40
IgorIgor
265
265
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Ignoring the zero clause, this is equivalent to the chromatic polynomial of path graph of length n using 3 colors.
There are three options for the first number, and then two for each subsequent number, since they can’t share the number of their most recent predecessor.
So, if n is even, there are $3 cdot 2^{(n-1)}$ different strings.
If n is odd, there are two possibilities for the middle digit. Again, each neighbor will have two possibilities, meaning that there are $2^n$ different strings.
Hopefully that makes sense. I’d advise looking at chromatic polynomials for a more clear understanding, but I’m also happy to try and provide more explanation myself.
answered Jan 5 at 11:13
Zachary HunterZachary Hunter
56611
$endgroup$
$begingroup$
I know how to solve it in this way, but I was asked to use recursion.
$endgroup$
– Igor
Jan 5 at 11:29
$begingroup$
Mike Earnest's post phrases it recursively.
$endgroup$
– Zachary Hunter
Jan 6 at 18:45
add a comment |
$begingroup$
Strings of even length behave very differently then strings of odd length. Let $e_n$ be the number of strings of length $2n$, and $d_n$ be the number of strings of length $2n+1$. Handle $d_n$ and $e_n$ separately.
For $d_n$, consider what the first and last symbol are. There are $2$ choices for the first, two for the last, and then the middle symbols can be chosen in $d_{n-1}$ ways. Therefore,
$$
d_{n}=2cdot 2cdot d_{n-1},tag{$nge 1$}
$$
with the base case $d_0=2$. Can you get a similar recursion for $e_n$?
answered Jan 5 at 17:56
Mike EarnestMike Earnest
21.4k11951
$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%2f3062561%2frecursion-relation-number-of-series-length-n-made-of-0-1-2%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$
Ignoring the zero clause, this is equivalent to the chromatic polynomial of path graph of length n using 3 colors.
There are three options for the first number, and then two for each subsequent number, since they can’t share the number of their most recent predecessor.
So, if n is even, there are $3 cdot 2^{(n-1)}$ different strings.
If n is odd, there are two possibilities for the middle digit. Again, each neighbor will have two possibilities, meaning that there are $2^n$ different strings.
Hopefully that makes sense. I’d advise looking at chromatic polynomials for a more clear understanding, but I’m also happy to try and provide more explanation myself.
answered Jan 5 at 11:13
Zachary HunterZachary Hunter
56611
$endgroup$
$begingroup$
I know how to solve it in this way, but I was asked to use recursion.
$endgroup$
– Igor
Jan 5 at 11:29
$begingroup$
Mike Earnest's post phrases it recursively.
$endgroup$
– Zachary Hunter
Jan 6 at 18:45
add a comment |
$begingroup$
Ignoring the zero clause, this is equivalent to the chromatic polynomial of path graph of length n using 3 colors.
There are three options for the first number, and then two for each subsequent number, since they can’t share the number of their most recent predecessor.
So, if n is even, there are $3 cdot 2^{(n-1)}$ different strings.
If n is odd, there are two possibilities for the middle digit. Again, each neighbor will have two possibilities, meaning that there are $2^n$ different strings.
Hopefully that makes sense. I’d advise looking at chromatic polynomials for a more clear understanding, but I’m also happy to try and provide more explanation myself.
answered Jan 5 at 11:13
Zachary HunterZachary Hunter
56611
$endgroup$
$begingroup$
I know how to solve it in this way, but I was asked to use recursion.
$endgroup$
– Igor
Jan 5 at 11:29
$begingroup$
Mike Earnest's post phrases it recursively.
$endgroup$
– Zachary Hunter
Jan 6 at 18:45
add a comment |
$begingroup$
Ignoring the zero clause, this is equivalent to the chromatic polynomial of path graph of length n using 3 colors.
There are three options for the first number, and then two for each subsequent number, since they can’t share the number of their most recent predecessor.
So, if n is even, there are $3 cdot 2^{(n-1)}$ different strings.
If n is odd, there are two possibilities for the middle digit. Again, each neighbor will have two possibilities, meaning that there are $2^n$ different strings.
Hopefully that makes sense. I’d advise looking at chromatic polynomials for a more clear understanding, but I’m also happy to try and provide more explanation myself.
answered Jan 5 at 11:13
Zachary HunterZachary Hunter
56611
$endgroup$
Ignoring the zero clause, this is equivalent to the chromatic polynomial of path graph of length n using 3 colors.
There are three options for the first number, and then two for each subsequent number, since they can’t share the number of their most recent predecessor.
So, if n is even, there are $3 cdot 2^{(n-1)}$ different strings.
If n is odd, there are two possibilities for the middle digit. Again, each neighbor will have two possibilities, meaning that there are $2^n$ different strings.
Hopefully that makes sense. I’d advise looking at chromatic polynomials for a more clear understanding, but I’m also happy to try and provide more explanation myself.
answered Jan 5 at 11:13
Zachary HunterZachary Hunter
56611
answered Jan 5 at 11:13
Zachary HunterZachary Hunter
56611
answered Jan 5 at 11:13
Zachary HunterZachary Hunter
56611
answered Jan 5 at 11:13
Zachary HunterZachary Hunter
56611
56611
$begingroup$
I know how to solve it in this way, but I was asked to use recursion.
$endgroup$
– Igor
Jan 5 at 11:29
$begingroup$
Mike Earnest's post phrases it recursively.
$endgroup$
– Zachary Hunter
Jan 6 at 18:45
add a comment |
$begingroup$
I know how to solve it in this way, but I was asked to use recursion.
$endgroup$
– Igor
Jan 5 at 11:29
$begingroup$
Mike Earnest's post phrases it recursively.
$endgroup$
– Zachary Hunter
Jan 6 at 18:45
$begingroup$
I know how to solve it in this way, but I was asked to use recursion.
$endgroup$
– Igor
Jan 5 at 11:29
$begingroup$
I know how to solve it in this way, but I was asked to use recursion.
$endgroup$
– Igor
Jan 5 at 11:29
$begingroup$
Mike Earnest's post phrases it recursively.
$endgroup$
– Zachary Hunter
Jan 6 at 18:45
$begingroup$
Mike Earnest's post phrases it recursively.
$endgroup$
– Zachary Hunter
Jan 6 at 18:45
add a comment |
$begingroup$
Strings of even length behave very differently then strings of odd length. Let $e_n$ be the number of strings of length $2n$, and $d_n$ be the number of strings of length $2n+1$. Handle $d_n$ and $e_n$ separately.
For $d_n$, consider what the first and last symbol are. There are $2$ choices for the first, two for the last, and then the middle symbols can be chosen in $d_{n-1}$ ways. Therefore,
$$
d_{n}=2cdot 2cdot d_{n-1},tag{$nge 1$}
$$
with the base case $d_0=2$. Can you get a similar recursion for $e_n$?
answered Jan 5 at 17:56
Mike EarnestMike Earnest
21.4k11951
$endgroup$
add a comment |
$begingroup$
Strings of even length behave very differently then strings of odd length. Let $e_n$ be the number of strings of length $2n$, and $d_n$ be the number of strings of length $2n+1$. Handle $d_n$ and $e_n$ separately.
For $d_n$, consider what the first and last symbol are. There are $2$ choices for the first, two for the last, and then the middle symbols can be chosen in $d_{n-1}$ ways. Therefore,
$$
d_{n}=2cdot 2cdot d_{n-1},tag{$nge 1$}
$$
with the base case $d_0=2$. Can you get a similar recursion for $e_n$?
answered Jan 5 at 17:56
Mike EarnestMike Earnest
21.4k11951
$endgroup$
add a comment |
$begingroup$
Strings of even length behave very differently then strings of odd length. Let $e_n$ be the number of strings of length $2n$, and $d_n$ be the number of strings of length $2n+1$. Handle $d_n$ and $e_n$ separately.
For $d_n$, consider what the first and last symbol are. There are $2$ choices for the first, two for the last, and then the middle symbols can be chosen in $d_{n-1}$ ways. Therefore,
$$
d_{n}=2cdot 2cdot d_{n-1},tag{$nge 1$}
$$
with the base case $d_0=2$. Can you get a similar recursion for $e_n$?
answered Jan 5 at 17:56
Mike EarnestMike Earnest
21.4k11951
$endgroup$
Strings of even length behave very differently then strings of odd length. Let $e_n$ be the number of strings of length $2n$, and $d_n$ be the number of strings of length $2n+1$. Handle $d_n$ and $e_n$ separately.
For $d_n$, consider what the first and last symbol are. There are $2$ choices for the first, two for the last, and then the middle symbols can be chosen in $d_{n-1}$ ways. Therefore,
$$
d_{n}=2cdot 2cdot d_{n-1},tag{$nge 1$}
$$
with the base case $d_0=2$. Can you get a similar recursion for $e_n$?
answered Jan 5 at 17:56
Mike EarnestMike Earnest
21.4k11951
answered Jan 5 at 17:56
Mike EarnestMike Earnest
21.4k11951
answered Jan 5 at 17:56
Mike EarnestMike Earnest
21.4k11951
answered Jan 5 at 17:56
Mike EarnestMike Earnest
21.4k11951
21.4k11951
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%2f3062561%2frecursion-relation-number-of-series-length-n-made-of-0-1-2%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
