Mixing
Binary Combinations Less Repetition
$begingroup$
What would the formula be for finding the number of combinations of $n$ binary elements when no $0$ can follow another but there is no restriction on subsequent $1$s. For example, an allowable sequence is $(1,0,1,1,1,0,1,0,1,1)$ but a disallowed sequence is $(1,0,0,1,1,0,1,0,0,1)$. How many allowable sequences are there for length $n$?
I know if there were no restriction, then the answer would be $2^n$. But I want to know how to subtract the repeated zeros.
combinatorics combinations binary
edited Jan 31 at 10:52
N. F. Taussig
45k103358
asked Jan 31 at 1:49
MichaelMichael
111
$endgroup$
add a comment |
$begingroup$
What would the formula be for finding the number of combinations of $n$ binary elements when no $0$ can follow another but there is no restriction on subsequent $1$s. For example, an allowable sequence is $(1,0,1,1,1,0,1,0,1,1)$ but a disallowed sequence is $(1,0,0,1,1,0,1,0,0,1)$. How many allowable sequences are there for length $n$?
I know if there were no restriction, then the answer would be $2^n$. But I want to know how to subtract the repeated zeros.
combinatorics combinations binary
edited Jan 31 at 10:52
N. F. Taussig
45k103358
asked Jan 31 at 1:49
MichaelMichael
111
$endgroup$
add a comment |
$begingroup$
What would the formula be for finding the number of combinations of $n$ binary elements when no $0$ can follow another but there is no restriction on subsequent $1$s. For example, an allowable sequence is $(1,0,1,1,1,0,1,0,1,1)$ but a disallowed sequence is $(1,0,0,1,1,0,1,0,0,1)$. How many allowable sequences are there for length $n$?
I know if there were no restriction, then the answer would be $2^n$. But I want to know how to subtract the repeated zeros.
combinatorics combinations binary
edited Jan 31 at 10:52
N. F. Taussig
45k103358
asked Jan 31 at 1:49
MichaelMichael
111
$endgroup$
What would the formula be for finding the number of combinations of $n$ binary elements when no $0$ can follow another but there is no restriction on subsequent $1$s. For example, an allowable sequence is $(1,0,1,1,1,0,1,0,1,1)$ but a disallowed sequence is $(1,0,0,1,1,0,1,0,0,1)$. How many allowable sequences are there for length $n$?
I know if there were no restriction, then the answer would be $2^n$. But I want to know how to subtract the repeated zeros.
combinatorics combinations binary
combinatorics combinations binary
edited Jan 31 at 10:52
N. F. Taussig
45k103358
asked Jan 31 at 1:49
MichaelMichael
111
edited Jan 31 at 10:52
N. F. Taussig
45k103358
asked Jan 31 at 1:49
MichaelMichael
111
edited Jan 31 at 10:52
N. F. Taussig
45k103358
edited Jan 31 at 10:52
N. F. Taussig
45k103358
edited Jan 31 at 10:52
N. F. Taussig
45k103358
45k103358
asked Jan 31 at 1:49
MichaelMichael
111
asked Jan 31 at 1:49
MichaelMichael
111
asked Jan 31 at 1:49
MichaelMichael
111
111
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Since this appears to be a self-study problem, I will only offer a hint as to how you might go about re-framing the problem in an alternative way that can lead to solution:
Reframing the problem: Define the substrings $mathbf{A}_0, mathbf{A}_1, mathbf{A}_2, ...$ and $mathbf{B}_1, mathbf{B}_2, mathbf{B}_3, ...$ by:
$$begin{matrix}
mathbf{A}_0 = ( 0 ) \[6pt]
mathbf{A}_1 = ( 1, 0 ) & & & & & mathbf{B}_1 = ( 1 ) \[6pt]
mathbf{A}_2 = ( 1, 1, 0 ) & & & & & mathbf{B}_2 = ( 1, 1 ) \[6pt]
vdots & & & & & vdots \[6pt]
mathbf{A}_n = ( underbrace{1, 1, ..., 1}_{n text{ times}}, 0 )
& & & & &
mathbf{B}_n = ( underbrace{1, 1, ..., 1}_{n text{ times}} ) \[6pt]
vdots & & & & & vdots \[6pt]
end{matrix}$$
Every binary string obeying the constraint specified in your question consists of an ordered set of these substrings, subject to some restrictive conditions. See if you can characterise the required restrictions on these substrings, and then you will have a procedure for producing unique strings that satisfy your constraint. This will reframe your counting problem as one involving orders sets of substrings, subject to some fairly simple conditions. You should then be able to count over those conditions using some applications of the multiplication rule.
answered Jan 31 at 2:53
BenBen
1,900215
$endgroup$
add a comment |
$begingroup$
Let $a_n$ be the number of binary sequences of length $n$ that do not contain two consecutive zeros.
Then $a_1 = 2$ since any binary sequence of length $1$ cannot contain two consecutive zeros and $a_2 = 3$ since the only binary sequence of length $2$ that contains consecutive zeros is $00$.
Observe that an admissible binary sequence of length $n$ must either begin with $1$ or $01$. If it begins with a $1$, then it must be followed by an admissible sequence of length $n - 1$, of which there are $a_{n - 1}$. If it begins with $01$, then it must be followed by an admissible sequence of length $n - 2$, of which there are $a_{n - 2}$. Hence, we have the recursion
$$a_n = a_{n - 1} + a_{n - 2}$$
Therefore, the number of binary sequences that contain no consecutive zeros satisfy the recursive formula
begin{align*}
a_1 & = 2\
a_2 & = 3\
a_n & = a_{n - 1} + a_{n - 2}
end{align*}
A familiar sequence will appear when you write out the first several terms.
answered Jan 31 at 12:10
N. F. TaussigN. F. Taussig
45k103358
$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%2f3094382%2fbinary-combinations-less-repetition%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$
Since this appears to be a self-study problem, I will only offer a hint as to how you might go about re-framing the problem in an alternative way that can lead to solution:
Reframing the problem: Define the substrings $mathbf{A}_0, mathbf{A}_1, mathbf{A}_2, ...$ and $mathbf{B}_1, mathbf{B}_2, mathbf{B}_3, ...$ by:
$$begin{matrix}
mathbf{A}_0 = ( 0 ) \[6pt]
mathbf{A}_1 = ( 1, 0 ) & & & & & mathbf{B}_1 = ( 1 ) \[6pt]
mathbf{A}_2 = ( 1, 1, 0 ) & & & & & mathbf{B}_2 = ( 1, 1 ) \[6pt]
vdots & & & & & vdots \[6pt]
mathbf{A}_n = ( underbrace{1, 1, ..., 1}_{n text{ times}}, 0 )
& & & & &
mathbf{B}_n = ( underbrace{1, 1, ..., 1}_{n text{ times}} ) \[6pt]
vdots & & & & & vdots \[6pt]
end{matrix}$$
Every binary string obeying the constraint specified in your question consists of an ordered set of these substrings, subject to some restrictive conditions. See if you can characterise the required restrictions on these substrings, and then you will have a procedure for producing unique strings that satisfy your constraint. This will reframe your counting problem as one involving orders sets of substrings, subject to some fairly simple conditions. You should then be able to count over those conditions using some applications of the multiplication rule.
answered Jan 31 at 2:53
BenBen
1,900215
$endgroup$
add a comment |
$begingroup$
Since this appears to be a self-study problem, I will only offer a hint as to how you might go about re-framing the problem in an alternative way that can lead to solution:
Reframing the problem: Define the substrings $mathbf{A}_0, mathbf{A}_1, mathbf{A}_2, ...$ and $mathbf{B}_1, mathbf{B}_2, mathbf{B}_3, ...$ by:
$$begin{matrix}
mathbf{A}_0 = ( 0 ) \[6pt]
mathbf{A}_1 = ( 1, 0 ) & & & & & mathbf{B}_1 = ( 1 ) \[6pt]
mathbf{A}_2 = ( 1, 1, 0 ) & & & & & mathbf{B}_2 = ( 1, 1 ) \[6pt]
vdots & & & & & vdots \[6pt]
mathbf{A}_n = ( underbrace{1, 1, ..., 1}_{n text{ times}}, 0 )
& & & & &
mathbf{B}_n = ( underbrace{1, 1, ..., 1}_{n text{ times}} ) \[6pt]
vdots & & & & & vdots \[6pt]
end{matrix}$$
Every binary string obeying the constraint specified in your question consists of an ordered set of these substrings, subject to some restrictive conditions. See if you can characterise the required restrictions on these substrings, and then you will have a procedure for producing unique strings that satisfy your constraint. This will reframe your counting problem as one involving orders sets of substrings, subject to some fairly simple conditions. You should then be able to count over those conditions using some applications of the multiplication rule.
answered Jan 31 at 2:53
BenBen
1,900215
$endgroup$
add a comment |
$begingroup$
Since this appears to be a self-study problem, I will only offer a hint as to how you might go about re-framing the problem in an alternative way that can lead to solution:
Reframing the problem: Define the substrings $mathbf{A}_0, mathbf{A}_1, mathbf{A}_2, ...$ and $mathbf{B}_1, mathbf{B}_2, mathbf{B}_3, ...$ by:
$$begin{matrix}
mathbf{A}_0 = ( 0 ) \[6pt]
mathbf{A}_1 = ( 1, 0 ) & & & & & mathbf{B}_1 = ( 1 ) \[6pt]
mathbf{A}_2 = ( 1, 1, 0 ) & & & & & mathbf{B}_2 = ( 1, 1 ) \[6pt]
vdots & & & & & vdots \[6pt]
mathbf{A}_n = ( underbrace{1, 1, ..., 1}_{n text{ times}}, 0 )
& & & & &
mathbf{B}_n = ( underbrace{1, 1, ..., 1}_{n text{ times}} ) \[6pt]
vdots & & & & & vdots \[6pt]
end{matrix}$$
Every binary string obeying the constraint specified in your question consists of an ordered set of these substrings, subject to some restrictive conditions. See if you can characterise the required restrictions on these substrings, and then you will have a procedure for producing unique strings that satisfy your constraint. This will reframe your counting problem as one involving orders sets of substrings, subject to some fairly simple conditions. You should then be able to count over those conditions using some applications of the multiplication rule.
answered Jan 31 at 2:53
BenBen
1,900215
$endgroup$
Since this appears to be a self-study problem, I will only offer a hint as to how you might go about re-framing the problem in an alternative way that can lead to solution:
Reframing the problem: Define the substrings $mathbf{A}_0, mathbf{A}_1, mathbf{A}_2, ...$ and $mathbf{B}_1, mathbf{B}_2, mathbf{B}_3, ...$ by:
$$begin{matrix}
mathbf{A}_0 = ( 0 ) \[6pt]
mathbf{A}_1 = ( 1, 0 ) & & & & & mathbf{B}_1 = ( 1 ) \[6pt]
mathbf{A}_2 = ( 1, 1, 0 ) & & & & & mathbf{B}_2 = ( 1, 1 ) \[6pt]
vdots & & & & & vdots \[6pt]
mathbf{A}_n = ( underbrace{1, 1, ..., 1}_{n text{ times}}, 0 )
& & & & &
mathbf{B}_n = ( underbrace{1, 1, ..., 1}_{n text{ times}} ) \[6pt]
vdots & & & & & vdots \[6pt]
end{matrix}$$
Every binary string obeying the constraint specified in your question consists of an ordered set of these substrings, subject to some restrictive conditions. See if you can characterise the required restrictions on these substrings, and then you will have a procedure for producing unique strings that satisfy your constraint. This will reframe your counting problem as one involving orders sets of substrings, subject to some fairly simple conditions. You should then be able to count over those conditions using some applications of the multiplication rule.
answered Jan 31 at 2:53
BenBen
1,900215
answered Jan 31 at 2:53
BenBen
1,900215
answered Jan 31 at 2:53
BenBen
1,900215
answered Jan 31 at 2:53
BenBen
1,900215
1,900215
add a comment |
add a comment |
$begingroup$
Let $a_n$ be the number of binary sequences of length $n$ that do not contain two consecutive zeros.
Then $a_1 = 2$ since any binary sequence of length $1$ cannot contain two consecutive zeros and $a_2 = 3$ since the only binary sequence of length $2$ that contains consecutive zeros is $00$.
Observe that an admissible binary sequence of length $n$ must either begin with $1$ or $01$. If it begins with a $1$, then it must be followed by an admissible sequence of length $n - 1$, of which there are $a_{n - 1}$. If it begins with $01$, then it must be followed by an admissible sequence of length $n - 2$, of which there are $a_{n - 2}$. Hence, we have the recursion
$$a_n = a_{n - 1} + a_{n - 2}$$
Therefore, the number of binary sequences that contain no consecutive zeros satisfy the recursive formula
begin{align*}
a_1 & = 2\
a_2 & = 3\
a_n & = a_{n - 1} + a_{n - 2}
end{align*}
A familiar sequence will appear when you write out the first several terms.
answered Jan 31 at 12:10
N. F. TaussigN. F. Taussig
45k103358
$endgroup$
add a comment |
$begingroup$
Let $a_n$ be the number of binary sequences of length $n$ that do not contain two consecutive zeros.
Then $a_1 = 2$ since any binary sequence of length $1$ cannot contain two consecutive zeros and $a_2 = 3$ since the only binary sequence of length $2$ that contains consecutive zeros is $00$.
Observe that an admissible binary sequence of length $n$ must either begin with $1$ or $01$. If it begins with a $1$, then it must be followed by an admissible sequence of length $n - 1$, of which there are $a_{n - 1}$. If it begins with $01$, then it must be followed by an admissible sequence of length $n - 2$, of which there are $a_{n - 2}$. Hence, we have the recursion
$$a_n = a_{n - 1} + a_{n - 2}$$
Therefore, the number of binary sequences that contain no consecutive zeros satisfy the recursive formula
begin{align*}
a_1 & = 2\
a_2 & = 3\
a_n & = a_{n - 1} + a_{n - 2}
end{align*}
A familiar sequence will appear when you write out the first several terms.
answered Jan 31 at 12:10
N. F. TaussigN. F. Taussig
45k103358
$endgroup$
add a comment |
$begingroup$
Let $a_n$ be the number of binary sequences of length $n$ that do not contain two consecutive zeros.
Then $a_1 = 2$ since any binary sequence of length $1$ cannot contain two consecutive zeros and $a_2 = 3$ since the only binary sequence of length $2$ that contains consecutive zeros is $00$.
Observe that an admissible binary sequence of length $n$ must either begin with $1$ or $01$. If it begins with a $1$, then it must be followed by an admissible sequence of length $n - 1$, of which there are $a_{n - 1}$. If it begins with $01$, then it must be followed by an admissible sequence of length $n - 2$, of which there are $a_{n - 2}$. Hence, we have the recursion
$$a_n = a_{n - 1} + a_{n - 2}$$
Therefore, the number of binary sequences that contain no consecutive zeros satisfy the recursive formula
begin{align*}
a_1 & = 2\
a_2 & = 3\
a_n & = a_{n - 1} + a_{n - 2}
end{align*}
A familiar sequence will appear when you write out the first several terms.
answered Jan 31 at 12:10
N. F. TaussigN. F. Taussig
45k103358
$endgroup$
Let $a_n$ be the number of binary sequences of length $n$ that do not contain two consecutive zeros.
Then $a_1 = 2$ since any binary sequence of length $1$ cannot contain two consecutive zeros and $a_2 = 3$ since the only binary sequence of length $2$ that contains consecutive zeros is $00$.
Observe that an admissible binary sequence of length $n$ must either begin with $1$ or $01$. If it begins with a $1$, then it must be followed by an admissible sequence of length $n - 1$, of which there are $a_{n - 1}$. If it begins with $01$, then it must be followed by an admissible sequence of length $n - 2$, of which there are $a_{n - 2}$. Hence, we have the recursion
$$a_n = a_{n - 1} + a_{n - 2}$$
Therefore, the number of binary sequences that contain no consecutive zeros satisfy the recursive formula
begin{align*}
a_1 & = 2\
a_2 & = 3\
a_n & = a_{n - 1} + a_{n - 2}
end{align*}
A familiar sequence will appear when you write out the first several terms.
answered Jan 31 at 12:10
N. F. TaussigN. F. Taussig
45k103358
answered Jan 31 at 12:10
N. F. TaussigN. F. Taussig
45k103358
answered Jan 31 at 12:10
N. F. TaussigN. F. Taussig
45k103358
answered Jan 31 at 12:10
N. F. TaussigN. F. Taussig
45k103358
45k103358
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%2f3094382%2fbinary-combinations-less-repetition%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
