Mixing
How many different binary strings of length n are there that do not contain 3 consecutive 0's and 2...
$begingroup$
Restrictions:
- First and the last digit has to be
1.
- Contain no two consecutive
1'sand
- Contain no three consecutive
0's
From my observation first two and last two digits will be fixed as 10 and 01, because it can't be 11... or ...11. So we got n-4 places left to fill. Apart from the first 2 and last 2 places if we add one more space then that space can only have 1, not 0. If we add one more place then there are two possible way (100101, 101001). So that's what I got
For
n=6 2 ways
n=7 2 ways
n=8 3 ways
n=9 4 ways
I don't know if I am doing it right or not and what's the easy way to find the number of ways for this scenario rather than counting.
I would appreciate some guidance for a general rule of a binary string of length n that do not contain 3 consecutive 0's and 2 consecutive 1's while starting and ending with 1
combinatorics permutations
asked Jan 31 at 17:21
KhanKhan
254
$endgroup$
add a comment |
$begingroup$
Restrictions:
- First and the last digit has to be
1.
- Contain no two consecutive
1'sand
- Contain no three consecutive
0's
From my observation first two and last two digits will be fixed as 10 and 01, because it can't be 11... or ...11. So we got n-4 places left to fill. Apart from the first 2 and last 2 places if we add one more space then that space can only have 1, not 0. If we add one more place then there are two possible way (100101, 101001). So that's what I got
For
n=6 2 ways
n=7 2 ways
n=8 3 ways
n=9 4 ways
I don't know if I am doing it right or not and what's the easy way to find the number of ways for this scenario rather than counting.
I would appreciate some guidance for a general rule of a binary string of length n that do not contain 3 consecutive 0's and 2 consecutive 1's while starting and ending with 1
combinatorics permutations
asked Jan 31 at 17:21
KhanKhan
254
$endgroup$
$begingroup$
The question is not clear. I do not know why the first and last digit must be 1. Even assuming this, I do not know why the first two digits must be 10. It seems to me that 111111 satisfies the title requirements since it does not "contain 3 consecutive 0s and 2 consecutive 1s." So the use of the word and needs clarification (should it really be or?), and all assumptions need to be in the body of the question.
$endgroup$
– Michael
Jan 31 at 17:35
$begingroup$
@Michael will add more detail. Thanks
$endgroup$
– Khan
Jan 31 at 17:45
add a comment |
$begingroup$
Restrictions:
- First and the last digit has to be
1.
- Contain no two consecutive
1'sand
- Contain no three consecutive
0's
From my observation first two and last two digits will be fixed as 10 and 01, because it can't be 11... or ...11. So we got n-4 places left to fill. Apart from the first 2 and last 2 places if we add one more space then that space can only have 1, not 0. If we add one more place then there are two possible way (100101, 101001). So that's what I got
For
n=6 2 ways
n=7 2 ways
n=8 3 ways
n=9 4 ways
I don't know if I am doing it right or not and what's the easy way to find the number of ways for this scenario rather than counting.
I would appreciate some guidance for a general rule of a binary string of length n that do not contain 3 consecutive 0's and 2 consecutive 1's while starting and ending with 1
combinatorics permutations
asked Jan 31 at 17:21
KhanKhan
254
$endgroup$
Restrictions:
- First and the last digit has to be
1.
- Contain no two consecutive
1'sand
- Contain no three consecutive
0's
From my observation first two and last two digits will be fixed as 10 and 01, because it can't be 11... or ...11. So we got n-4 places left to fill. Apart from the first 2 and last 2 places if we add one more space then that space can only have 1, not 0. If we add one more place then there are two possible way (100101, 101001). So that's what I got
For
n=6 2 ways
n=7 2 ways
n=8 3 ways
n=9 4 ways
I don't know if I am doing it right or not and what's the easy way to find the number of ways for this scenario rather than counting.
I would appreciate some guidance for a general rule of a binary string of length n that do not contain 3 consecutive 0's and 2 consecutive 1's while starting and ending with 1
combinatorics permutations
combinatorics permutations
asked Jan 31 at 17:21
KhanKhan
254
asked Jan 31 at 17:21
KhanKhan
254
edited Jan 31 at 17:49
Khan
asked Jan 31 at 17:21
KhanKhan
254
asked Jan 31 at 17:21
KhanKhan
254
asked Jan 31 at 17:21
KhanKhan
254
254
$begingroup$
The question is not clear. I do not know why the first and last digit must be 1. Even assuming this, I do not know why the first two digits must be 10. It seems to me that 111111 satisfies the title requirements since it does not "contain 3 consecutive 0s and 2 consecutive 1s." So the use of the word and needs clarification (should it really be or?), and all assumptions need to be in the body of the question.
$endgroup$
– Michael
Jan 31 at 17:35
$begingroup$
@Michael will add more detail. Thanks
$endgroup$
– Khan
Jan 31 at 17:45
add a comment |
$begingroup$
The question is not clear. I do not know why the first and last digit must be 1. Even assuming this, I do not know why the first two digits must be 10. It seems to me that 111111 satisfies the title requirements since it does not "contain 3 consecutive 0s and 2 consecutive 1s." So the use of the word and needs clarification (should it really be or?), and all assumptions need to be in the body of the question.
$endgroup$
– Michael
Jan 31 at 17:35
$begingroup$
@Michael will add more detail. Thanks
$endgroup$
– Khan
Jan 31 at 17:45
$begingroup$
The question is not clear. I do not know why the first and last digit must be 1. Even assuming this, I do not know why the first two digits must be 10. It seems to me that 111111 satisfies the title requirements since it does not "contain 3 consecutive 0s and 2 consecutive 1s." So the use of the word and needs clarification (should it really be or?), and all assumptions need to be in the body of the question.
$endgroup$
– Michael
Jan 31 at 17:35
$begingroup$
The question is not clear. I do not know why the first and last digit must be 1. Even assuming this, I do not know why the first two digits must be 10. It seems to me that 111111 satisfies the title requirements since it does not "contain 3 consecutive 0s and 2 consecutive 1s." So the use of the word and needs clarification (should it really be or?), and all assumptions need to be in the body of the question.
$endgroup$
– Michael
Jan 31 at 17:35
$begingroup$
@Michael will add more detail. Thanks
$endgroup$
– Khan
Jan 31 at 17:45
$begingroup$
@Michael will add more detail. Thanks
$endgroup$
– Khan
Jan 31 at 17:45
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I can find a recursive formula, but a general formula is tricky.
$f(x) = f(x-2) + f(x-3)$
That is because the pattern must start with 1, then you must have either one or two 0's before the next 1. In other words, 01 or 001.
Thus any sequence of length X is either (a valid sequence of length x-2 + 01) or (a valid sequence of length x-3 + 001)
For a general formula as a function of N, we can assume
$f(x)=sum{n^x}$ for some values of a and then
$n^x=n^{x-2}+n^{x-3}$
Leaves $n$ as a root of the cubic equation $y^3-y-1=0$.
Thus $f(x) = a_1n_1^x + a_2n_2^x + a_3n_3^x$, where $n_1, n_2, n_3$ are the roots of the equation $x^3-x-1=0$. But since two of these roots are imaginary, it is a problem to find a specific formula that is non-messy.
In your case, we have
- f(0) = 0 (trivial case)
- f(1) = 1 (1)
- f(2) = 0 (again trivial to check none work)
- f(3) = 1 (1-01)
- f(4) = 1 (1-001)
- f(5) = 1 (101-01)
- f(6) = 2 (101-001, 1001-01)
- f(7) = 2 (1001-001, 10101-01)
- f(8) = 2+1=3
- f(9) = 2+2=4
So your calculations are right.
Your problem reminds me of an American Invitational Math Exam problem where you had to find the number of sequences of N coin flips with no 2 tails in a row. You could thus have either H or HT to create a list of length N+1, chopping off the starting H.
Then $g(x)=g(x-1)+g(x-2)$ and if we assume $g(x)=sum{a^x}$ for some values of $a$, we get $a^n=a^n-1+a^n-2$, or $a^2=a+1$, making $a$ the golden ratio.
answered Jan 31 at 17:58
aschultzaschultz
2691515
$endgroup$
$begingroup$
Thanks for a simple solution. I have seen some of the questions where the solution was based on the recursive formula. I still haven't understood this method completely. Can you please suggest some resources to learn this method?
$endgroup$
– Khan
Feb 1 at 15:54
$begingroup$
So suppose if the question was can start with 1 or 0 but no 3 0's and no 3 1's can be placed consecutively. Then any sequence which starts with 1 of length X is either a valid sequence of length x-1+0, x-1+1, x-2+01,x-2+10,x-2+11,x-3+001 or x-3+100. So f(x) = 2f(x-1)+3f(x-2)+2f(x-3)? Did I get it right?
$endgroup$
– Khan
Feb 1 at 15:59
add a comment |
$begingroup$
Ignoring the $1$ at the front, any such sequence can be broken into blocks of $01$ and $001$. Let $k$ be the number of blocks of $01$. Then the number of blocks of $001$ will be $(n-1-2k)/3$, which is only possible when this number is an integer. This means there are $(n-1-2k)/3+k=(n+k-1)/3$ blocks total. We must choose $k$ of these blocks to be $01$, which can be done in $binom{(n+k-1)/3}k$ ways. Therefore, the number of sequences is
$$
sum_{substack{k=0}}^{lfloor (n-1)/2rfloor}binom{frac{n+k-1}3}{k}
$$
where the summation only ranges over $k$ for which $n+k-1$ is an integer multiple of $3$.
It is also possible to get a "closed form" by solving the linear recurrence
$$
a_n=a_{n-2}+a_{n-3},\
a_2=0,\
a_1=1,\
a_0=0.
$$
To solve this, see for example:
https://en.wikipedia.org/wiki/Recurrence_relation#Roots_of_the_characteristic_polynomial.
answered Jan 31 at 18:04
Mike EarnestMike Earnest
27.1k22152
$endgroup$
$begingroup$
But the roots of the characteristic equation are ugly.
$endgroup$
– saulspatz
Jan 31 at 18:13
$begingroup$
@saulspatz True. One of the roots $rapprox 1.3247$ is real, and the others are complex with magnitude less than $1$. For large enough $n$, you can therefore find $a_n$ by rounding $r^n$ to the nearest integer, which is a little nicer.
$endgroup$
– Mike Earnest
Jan 31 at 18:16
$begingroup$
Good point. I hadn't considered that.
$endgroup$
– saulspatz
Jan 31 at 18:19
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%2f3095181%2fhow-many-different-binary-strings-of-length-n-are-there-that-do-not-contain-3-co%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 can find a recursive formula, but a general formula is tricky.
$f(x) = f(x-2) + f(x-3)$
That is because the pattern must start with 1, then you must have either one or two 0's before the next 1. In other words, 01 or 001.
Thus any sequence of length X is either (a valid sequence of length x-2 + 01) or (a valid sequence of length x-3 + 001)
For a general formula as a function of N, we can assume
$f(x)=sum{n^x}$ for some values of a and then
$n^x=n^{x-2}+n^{x-3}$
Leaves $n$ as a root of the cubic equation $y^3-y-1=0$.
Thus $f(x) = a_1n_1^x + a_2n_2^x + a_3n_3^x$, where $n_1, n_2, n_3$ are the roots of the equation $x^3-x-1=0$. But since two of these roots are imaginary, it is a problem to find a specific formula that is non-messy.
In your case, we have
- f(0) = 0 (trivial case)
- f(1) = 1 (1)
- f(2) = 0 (again trivial to check none work)
- f(3) = 1 (1-01)
- f(4) = 1 (1-001)
- f(5) = 1 (101-01)
- f(6) = 2 (101-001, 1001-01)
- f(7) = 2 (1001-001, 10101-01)
- f(8) = 2+1=3
- f(9) = 2+2=4
So your calculations are right.
Your problem reminds me of an American Invitational Math Exam problem where you had to find the number of sequences of N coin flips with no 2 tails in a row. You could thus have either H or HT to create a list of length N+1, chopping off the starting H.
Then $g(x)=g(x-1)+g(x-2)$ and if we assume $g(x)=sum{a^x}$ for some values of $a$, we get $a^n=a^n-1+a^n-2$, or $a^2=a+1$, making $a$ the golden ratio.
answered Jan 31 at 17:58
aschultzaschultz
2691515
$endgroup$
$begingroup$
Thanks for a simple solution. I have seen some of the questions where the solution was based on the recursive formula. I still haven't understood this method completely. Can you please suggest some resources to learn this method?
$endgroup$
– Khan
Feb 1 at 15:54
$begingroup$
So suppose if the question was can start with 1 or 0 but no 3 0's and no 3 1's can be placed consecutively. Then any sequence which starts with 1 of length X is either a valid sequence of length x-1+0, x-1+1, x-2+01,x-2+10,x-2+11,x-3+001 or x-3+100. So f(x) = 2f(x-1)+3f(x-2)+2f(x-3)? Did I get it right?
$endgroup$
– Khan
Feb 1 at 15:59
add a comment |
$begingroup$
I can find a recursive formula, but a general formula is tricky.
$f(x) = f(x-2) + f(x-3)$
That is because the pattern must start with 1, then you must have either one or two 0's before the next 1. In other words, 01 or 001.
Thus any sequence of length X is either (a valid sequence of length x-2 + 01) or (a valid sequence of length x-3 + 001)
For a general formula as a function of N, we can assume
$f(x)=sum{n^x}$ for some values of a and then
$n^x=n^{x-2}+n^{x-3}$
Leaves $n$ as a root of the cubic equation $y^3-y-1=0$.
Thus $f(x) = a_1n_1^x + a_2n_2^x + a_3n_3^x$, where $n_1, n_2, n_3$ are the roots of the equation $x^3-x-1=0$. But since two of these roots are imaginary, it is a problem to find a specific formula that is non-messy.
In your case, we have
- f(0) = 0 (trivial case)
- f(1) = 1 (1)
- f(2) = 0 (again trivial to check none work)
- f(3) = 1 (1-01)
- f(4) = 1 (1-001)
- f(5) = 1 (101-01)
- f(6) = 2 (101-001, 1001-01)
- f(7) = 2 (1001-001, 10101-01)
- f(8) = 2+1=3
- f(9) = 2+2=4
So your calculations are right.
Your problem reminds me of an American Invitational Math Exam problem where you had to find the number of sequences of N coin flips with no 2 tails in a row. You could thus have either H or HT to create a list of length N+1, chopping off the starting H.
Then $g(x)=g(x-1)+g(x-2)$ and if we assume $g(x)=sum{a^x}$ for some values of $a$, we get $a^n=a^n-1+a^n-2$, or $a^2=a+1$, making $a$ the golden ratio.
answered Jan 31 at 17:58
aschultzaschultz
2691515
$endgroup$
$begingroup$
Thanks for a simple solution. I have seen some of the questions where the solution was based on the recursive formula. I still haven't understood this method completely. Can you please suggest some resources to learn this method?
$endgroup$
– Khan
Feb 1 at 15:54
$begingroup$
So suppose if the question was can start with 1 or 0 but no 3 0's and no 3 1's can be placed consecutively. Then any sequence which starts with 1 of length X is either a valid sequence of length x-1+0, x-1+1, x-2+01,x-2+10,x-2+11,x-3+001 or x-3+100. So f(x) = 2f(x-1)+3f(x-2)+2f(x-3)? Did I get it right?
$endgroup$
– Khan
Feb 1 at 15:59
add a comment |
$begingroup$
I can find a recursive formula, but a general formula is tricky.
$f(x) = f(x-2) + f(x-3)$
That is because the pattern must start with 1, then you must have either one or two 0's before the next 1. In other words, 01 or 001.
Thus any sequence of length X is either (a valid sequence of length x-2 + 01) or (a valid sequence of length x-3 + 001)
For a general formula as a function of N, we can assume
$f(x)=sum{n^x}$ for some values of a and then
$n^x=n^{x-2}+n^{x-3}$
Leaves $n$ as a root of the cubic equation $y^3-y-1=0$.
Thus $f(x) = a_1n_1^x + a_2n_2^x + a_3n_3^x$, where $n_1, n_2, n_3$ are the roots of the equation $x^3-x-1=0$. But since two of these roots are imaginary, it is a problem to find a specific formula that is non-messy.
In your case, we have
- f(0) = 0 (trivial case)
- f(1) = 1 (1)
- f(2) = 0 (again trivial to check none work)
- f(3) = 1 (1-01)
- f(4) = 1 (1-001)
- f(5) = 1 (101-01)
- f(6) = 2 (101-001, 1001-01)
- f(7) = 2 (1001-001, 10101-01)
- f(8) = 2+1=3
- f(9) = 2+2=4
So your calculations are right.
Your problem reminds me of an American Invitational Math Exam problem where you had to find the number of sequences of N coin flips with no 2 tails in a row. You could thus have either H or HT to create a list of length N+1, chopping off the starting H.
Then $g(x)=g(x-1)+g(x-2)$ and if we assume $g(x)=sum{a^x}$ for some values of $a$, we get $a^n=a^n-1+a^n-2$, or $a^2=a+1$, making $a$ the golden ratio.
answered Jan 31 at 17:58
aschultzaschultz
2691515
$endgroup$
I can find a recursive formula, but a general formula is tricky.
$f(x) = f(x-2) + f(x-3)$
That is because the pattern must start with 1, then you must have either one or two 0's before the next 1. In other words, 01 or 001.
Thus any sequence of length X is either (a valid sequence of length x-2 + 01) or (a valid sequence of length x-3 + 001)
For a general formula as a function of N, we can assume
$f(x)=sum{n^x}$ for some values of a and then
$n^x=n^{x-2}+n^{x-3}$
Leaves $n$ as a root of the cubic equation $y^3-y-1=0$.
Thus $f(x) = a_1n_1^x + a_2n_2^x + a_3n_3^x$, where $n_1, n_2, n_3$ are the roots of the equation $x^3-x-1=0$. But since two of these roots are imaginary, it is a problem to find a specific formula that is non-messy.
In your case, we have
- f(0) = 0 (trivial case)
- f(1) = 1 (1)
- f(2) = 0 (again trivial to check none work)
- f(3) = 1 (1-01)
- f(4) = 1 (1-001)
- f(5) = 1 (101-01)
- f(6) = 2 (101-001, 1001-01)
- f(7) = 2 (1001-001, 10101-01)
- f(8) = 2+1=3
- f(9) = 2+2=4
So your calculations are right.
Your problem reminds me of an American Invitational Math Exam problem where you had to find the number of sequences of N coin flips with no 2 tails in a row. You could thus have either H or HT to create a list of length N+1, chopping off the starting H.
Then $g(x)=g(x-1)+g(x-2)$ and if we assume $g(x)=sum{a^x}$ for some values of $a$, we get $a^n=a^n-1+a^n-2$, or $a^2=a+1$, making $a$ the golden ratio.
answered Jan 31 at 17:58
aschultzaschultz
2691515
edited Jan 31 at 18:06
answered Jan 31 at 17:58
aschultzaschultz
2691515
answered Jan 31 at 17:58
aschultzaschultz
2691515
answered Jan 31 at 17:58
aschultzaschultz
2691515
2691515
$begingroup$
Thanks for a simple solution. I have seen some of the questions where the solution was based on the recursive formula. I still haven't understood this method completely. Can you please suggest some resources to learn this method?
$endgroup$
– Khan
Feb 1 at 15:54
$begingroup$
So suppose if the question was can start with 1 or 0 but no 3 0's and no 3 1's can be placed consecutively. Then any sequence which starts with 1 of length X is either a valid sequence of length x-1+0, x-1+1, x-2+01,x-2+10,x-2+11,x-3+001 or x-3+100. So f(x) = 2f(x-1)+3f(x-2)+2f(x-3)? Did I get it right?
$endgroup$
– Khan
Feb 1 at 15:59
add a comment |
$begingroup$
Thanks for a simple solution. I have seen some of the questions where the solution was based on the recursive formula. I still haven't understood this method completely. Can you please suggest some resources to learn this method?
$endgroup$
– Khan
Feb 1 at 15:54
$begingroup$
So suppose if the question was can start with 1 or 0 but no 3 0's and no 3 1's can be placed consecutively. Then any sequence which starts with 1 of length X is either a valid sequence of length x-1+0, x-1+1, x-2+01,x-2+10,x-2+11,x-3+001 or x-3+100. So f(x) = 2f(x-1)+3f(x-2)+2f(x-3)? Did I get it right?
$endgroup$
– Khan
Feb 1 at 15:59
$begingroup$
Thanks for a simple solution. I have seen some of the questions where the solution was based on the recursive formula. I still haven't understood this method completely. Can you please suggest some resources to learn this method?
$endgroup$
– Khan
Feb 1 at 15:54
$begingroup$
Thanks for a simple solution. I have seen some of the questions where the solution was based on the recursive formula. I still haven't understood this method completely. Can you please suggest some resources to learn this method?
$endgroup$
– Khan
Feb 1 at 15:54
$begingroup$
So suppose if the question was can start with 1 or 0 but no 3 0's and no 3 1's can be placed consecutively. Then any sequence which starts with 1 of length X is either a valid sequence of length x-1+0, x-1+1, x-2+01,x-2+10,x-2+11,x-3+001 or x-3+100. So f(x) = 2f(x-1)+3f(x-2)+2f(x-3)? Did I get it right?
$endgroup$
– Khan
Feb 1 at 15:59
$begingroup$
So suppose if the question was can start with 1 or 0 but no 3 0's and no 3 1's can be placed consecutively. Then any sequence which starts with 1 of length X is either a valid sequence of length x-1+0, x-1+1, x-2+01,x-2+10,x-2+11,x-3+001 or x-3+100. So f(x) = 2f(x-1)+3f(x-2)+2f(x-3)? Did I get it right?
$endgroup$
– Khan
Feb 1 at 15:59
add a comment |
$begingroup$
Ignoring the $1$ at the front, any such sequence can be broken into blocks of $01$ and $001$. Let $k$ be the number of blocks of $01$. Then the number of blocks of $001$ will be $(n-1-2k)/3$, which is only possible when this number is an integer. This means there are $(n-1-2k)/3+k=(n+k-1)/3$ blocks total. We must choose $k$ of these blocks to be $01$, which can be done in $binom{(n+k-1)/3}k$ ways. Therefore, the number of sequences is
$$
sum_{substack{k=0}}^{lfloor (n-1)/2rfloor}binom{frac{n+k-1}3}{k}
$$
where the summation only ranges over $k$ for which $n+k-1$ is an integer multiple of $3$.
It is also possible to get a "closed form" by solving the linear recurrence
$$
a_n=a_{n-2}+a_{n-3},\
a_2=0,\
a_1=1,\
a_0=0.
$$
To solve this, see for example:
https://en.wikipedia.org/wiki/Recurrence_relation#Roots_of_the_characteristic_polynomial.
answered Jan 31 at 18:04
Mike EarnestMike Earnest
27.1k22152
$endgroup$
$begingroup$
But the roots of the characteristic equation are ugly.
$endgroup$
– saulspatz
Jan 31 at 18:13
$begingroup$
@saulspatz True. One of the roots $rapprox 1.3247$ is real, and the others are complex with magnitude less than $1$. For large enough $n$, you can therefore find $a_n$ by rounding $r^n$ to the nearest integer, which is a little nicer.
$endgroup$
– Mike Earnest
Jan 31 at 18:16
$begingroup$
Good point. I hadn't considered that.
$endgroup$
– saulspatz
Jan 31 at 18:19
add a comment |
$begingroup$
Ignoring the $1$ at the front, any such sequence can be broken into blocks of $01$ and $001$. Let $k$ be the number of blocks of $01$. Then the number of blocks of $001$ will be $(n-1-2k)/3$, which is only possible when this number is an integer. This means there are $(n-1-2k)/3+k=(n+k-1)/3$ blocks total. We must choose $k$ of these blocks to be $01$, which can be done in $binom{(n+k-1)/3}k$ ways. Therefore, the number of sequences is
$$
sum_{substack{k=0}}^{lfloor (n-1)/2rfloor}binom{frac{n+k-1}3}{k}
$$
where the summation only ranges over $k$ for which $n+k-1$ is an integer multiple of $3$.
It is also possible to get a "closed form" by solving the linear recurrence
$$
a_n=a_{n-2}+a_{n-3},\
a_2=0,\
a_1=1,\
a_0=0.
$$
To solve this, see for example:
https://en.wikipedia.org/wiki/Recurrence_relation#Roots_of_the_characteristic_polynomial.
answered Jan 31 at 18:04
Mike EarnestMike Earnest
27.1k22152
$endgroup$
$begingroup$
But the roots of the characteristic equation are ugly.
$endgroup$
– saulspatz
Jan 31 at 18:13
$begingroup$
@saulspatz True. One of the roots $rapprox 1.3247$ is real, and the others are complex with magnitude less than $1$. For large enough $n$, you can therefore find $a_n$ by rounding $r^n$ to the nearest integer, which is a little nicer.
$endgroup$
– Mike Earnest
Jan 31 at 18:16
$begingroup$
Good point. I hadn't considered that.
$endgroup$
– saulspatz
Jan 31 at 18:19
add a comment |
$begingroup$
Ignoring the $1$ at the front, any such sequence can be broken into blocks of $01$ and $001$. Let $k$ be the number of blocks of $01$. Then the number of blocks of $001$ will be $(n-1-2k)/3$, which is only possible when this number is an integer. This means there are $(n-1-2k)/3+k=(n+k-1)/3$ blocks total. We must choose $k$ of these blocks to be $01$, which can be done in $binom{(n+k-1)/3}k$ ways. Therefore, the number of sequences is
$$
sum_{substack{k=0}}^{lfloor (n-1)/2rfloor}binom{frac{n+k-1}3}{k}
$$
where the summation only ranges over $k$ for which $n+k-1$ is an integer multiple of $3$.
It is also possible to get a "closed form" by solving the linear recurrence
$$
a_n=a_{n-2}+a_{n-3},\
a_2=0,\
a_1=1,\
a_0=0.
$$
To solve this, see for example:
https://en.wikipedia.org/wiki/Recurrence_relation#Roots_of_the_characteristic_polynomial.
answered Jan 31 at 18:04
Mike EarnestMike Earnest
27.1k22152
$endgroup$
Ignoring the $1$ at the front, any such sequence can be broken into blocks of $01$ and $001$. Let $k$ be the number of blocks of $01$. Then the number of blocks of $001$ will be $(n-1-2k)/3$, which is only possible when this number is an integer. This means there are $(n-1-2k)/3+k=(n+k-1)/3$ blocks total. We must choose $k$ of these blocks to be $01$, which can be done in $binom{(n+k-1)/3}k$ ways. Therefore, the number of sequences is
$$
sum_{substack{k=0}}^{lfloor (n-1)/2rfloor}binom{frac{n+k-1}3}{k}
$$
where the summation only ranges over $k$ for which $n+k-1$ is an integer multiple of $3$.
It is also possible to get a "closed form" by solving the linear recurrence
$$
a_n=a_{n-2}+a_{n-3},\
a_2=0,\
a_1=1,\
a_0=0.
$$
To solve this, see for example:
https://en.wikipedia.org/wiki/Recurrence_relation#Roots_of_the_characteristic_polynomial.
answered Jan 31 at 18:04
Mike EarnestMike Earnest
27.1k22152
answered Jan 31 at 18:04
Mike EarnestMike Earnest
27.1k22152
answered Jan 31 at 18:04
Mike EarnestMike Earnest
27.1k22152
answered Jan 31 at 18:04
Mike EarnestMike Earnest
27.1k22152
27.1k22152
$begingroup$
But the roots of the characteristic equation are ugly.
$endgroup$
– saulspatz
Jan 31 at 18:13
$begingroup$
@saulspatz True. One of the roots $rapprox 1.3247$ is real, and the others are complex with magnitude less than $1$. For large enough $n$, you can therefore find $a_n$ by rounding $r^n$ to the nearest integer, which is a little nicer.
$endgroup$
– Mike Earnest
Jan 31 at 18:16
$begingroup$
Good point. I hadn't considered that.
$endgroup$
– saulspatz
Jan 31 at 18:19
add a comment |
$begingroup$
But the roots of the characteristic equation are ugly.
$endgroup$
– saulspatz
Jan 31 at 18:13
$begingroup$
@saulspatz True. One of the roots $rapprox 1.3247$ is real, and the others are complex with magnitude less than $1$. For large enough $n$, you can therefore find $a_n$ by rounding $r^n$ to the nearest integer, which is a little nicer.
$endgroup$
– Mike Earnest
Jan 31 at 18:16
$begingroup$
Good point. I hadn't considered that.
$endgroup$
– saulspatz
Jan 31 at 18:19
$begingroup$
But the roots of the characteristic equation are ugly.
$endgroup$
– saulspatz
Jan 31 at 18:13
$begingroup$
But the roots of the characteristic equation are ugly.
$endgroup$
– saulspatz
Jan 31 at 18:13
$begingroup$
@saulspatz True. One of the roots $rapprox 1.3247$ is real, and the others are complex with magnitude less than $1$. For large enough $n$, you can therefore find $a_n$ by rounding $r^n$ to the nearest integer, which is a little nicer.
$endgroup$
– Mike Earnest
Jan 31 at 18:16
$begingroup$
@saulspatz True. One of the roots $rapprox 1.3247$ is real, and the others are complex with magnitude less than $1$. For large enough $n$, you can therefore find $a_n$ by rounding $r^n$ to the nearest integer, which is a little nicer.
$endgroup$
– Mike Earnest
Jan 31 at 18:16
$begingroup$
Good point. I hadn't considered that.
$endgroup$
– saulspatz
Jan 31 at 18:19
$begingroup$
Good point. I hadn't considered that.
$endgroup$
– saulspatz
Jan 31 at 18:19
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%2f3095181%2fhow-many-different-binary-strings-of-length-n-are-there-that-do-not-contain-3-co%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
$begingroup$
The question is not clear. I do not know why the first and last digit must be 1. Even assuming this, I do not know why the first two digits must be 10. It seems to me that 111111 satisfies the title requirements since it does not "contain 3 consecutive 0s and 2 consecutive 1s." So the use of the word and needs clarification (should it really be or?), and all assumptions need to be in the body of the question.
$endgroup$
– Michael
Jan 31 at 17:35
$begingroup$
@Michael will add more detail. Thanks
$endgroup$
– Khan
Jan 31 at 17:45