Mixing
How many binary strings of length 11 contain five consecutive 0s or five consecutive 1s？
$begingroup$
The answer is 502 but why?
I use $$(^7C_1cdot2^6-^6C_1cdot2^5)cdot2-2$$
$C(7,1)*2^6$ count 11111 and 00000 as one number
$-C(6,1)*2^5$ more than 6 consecutive 111111 or 000000 count twice(1111111 three times etc.)
11111011111 and 00000100000 count twice
combinatorics discrete-mathematics
edited Jan 19 at 7:40
Kyky
472314
asked Jan 19 at 6:21
NoobananaaNoobananaa
62
$endgroup$
add a comment |
$begingroup$
The answer is 502 but why?
I use $$(^7C_1cdot2^6-^6C_1cdot2^5)cdot2-2$$
$C(7,1)*2^6$ count 11111 and 00000 as one number
$-C(6,1)*2^5$ more than 6 consecutive 111111 or 000000 count twice(1111111 three times etc.)
11111011111 and 00000100000 count twice
combinatorics discrete-mathematics
edited Jan 19 at 7:40
Kyky
472314
asked Jan 19 at 6:21
NoobananaaNoobananaa
62
$endgroup$
$begingroup$
Welcome to MSE. Here's a MathJax tutorial :)
$endgroup$
– Thomas Shelby
Jan 19 at 6:46
add a comment |
$begingroup$
The answer is 502 but why?
I use $$(^7C_1cdot2^6-^6C_1cdot2^5)cdot2-2$$
$C(7,1)*2^6$ count 11111 and 00000 as one number
$-C(6,1)*2^5$ more than 6 consecutive 111111 or 000000 count twice(1111111 three times etc.)
11111011111 and 00000100000 count twice
combinatorics discrete-mathematics
edited Jan 19 at 7:40
Kyky
472314
asked Jan 19 at 6:21
NoobananaaNoobananaa
62
$endgroup$
The answer is 502 but why?
I use $$(^7C_1cdot2^6-^6C_1cdot2^5)cdot2-2$$
$C(7,1)*2^6$ count 11111 and 00000 as one number
$-C(6,1)*2^5$ more than 6 consecutive 111111 or 000000 count twice(1111111 three times etc.)
11111011111 and 00000100000 count twice
combinatorics discrete-mathematics
combinatorics discrete-mathematics
edited Jan 19 at 7:40
Kyky
472314
asked Jan 19 at 6:21
NoobananaaNoobananaa
62
edited Jan 19 at 7:40
Kyky
472314
asked Jan 19 at 6:21
NoobananaaNoobananaa
62
edited Jan 19 at 7:40
Kyky
472314
edited Jan 19 at 7:40
Kyky
472314
edited Jan 19 at 7:40
Kyky
472314
472314
asked Jan 19 at 6:21
NoobananaaNoobananaa
62
asked Jan 19 at 6:21
NoobananaaNoobananaa
62
asked Jan 19 at 6:21
NoobananaaNoobananaa
62
62
$begingroup$
Welcome to MSE. Here's a MathJax tutorial :)
$endgroup$
– Thomas Shelby
Jan 19 at 6:46
add a comment |
$begingroup$
Welcome to MSE. Here's a MathJax tutorial :)
$endgroup$
– Thomas Shelby
Jan 19 at 6:46
$begingroup$
Welcome to MSE. Here's a MathJax tutorial :)
$endgroup$
– Thomas Shelby
Jan 19 at 6:46
$begingroup$
Welcome to MSE. Here's a MathJax tutorial :)
$endgroup$
– Thomas Shelby
Jan 19 at 6:46
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let's start with this: a sequence of bits has a $5$-bit streak starting at the $k$th bit if bits $k$ through $k+4$ are all the same and bit $k-1$ either doesn't exist or is different.
So, for an 11-bit number: $2*2^6$ of them will have a streak starting at the $0$th bit, because there are six free bits after the streak; and $6*2*2^5$ of them will have a streak starting at the 1st through 6th bits because committed both before and after there are $5$ free bits. This gives $512$ ways to do it, but there are a few duplicates, which we'll need to find.
It is possible for two streaks to exist if they start 6 or more bits apart and use the same value, or 5 or more bits apart and use different values. This gives 0th and 5th with different streaks, 0th and 6th with same or different streaks, and 1st and 6th with different streaks.
00000111110
00000111111
11111000000
11111000001
00000100000
00000011111
11111011111
11111100000
10000011111
01111100000
There are ten of these and each has been counted twice, so we must subtract $10$ from our initial count, for a total of $502$.
answered Jan 19 at 7:30
Dan UznanskiDan Uznanski
6,90021528
$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%2f3079065%2fhow-many-binary-strings-of-length-11-contain-five-consecutive-0s-or-five-consecu%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
$begingroup$
Let's start with this: a sequence of bits has a $5$-bit streak starting at the $k$th bit if bits $k$ through $k+4$ are all the same and bit $k-1$ either doesn't exist or is different.
So, for an 11-bit number: $2*2^6$ of them will have a streak starting at the $0$th bit, because there are six free bits after the streak; and $6*2*2^5$ of them will have a streak starting at the 1st through 6th bits because committed both before and after there are $5$ free bits. This gives $512$ ways to do it, but there are a few duplicates, which we'll need to find.
It is possible for two streaks to exist if they start 6 or more bits apart and use the same value, or 5 or more bits apart and use different values. This gives 0th and 5th with different streaks, 0th and 6th with same or different streaks, and 1st and 6th with different streaks.
00000111110
00000111111
11111000000
11111000001
00000100000
00000011111
11111011111
11111100000
10000011111
01111100000
There are ten of these and each has been counted twice, so we must subtract $10$ from our initial count, for a total of $502$.
answered Jan 19 at 7:30
Dan UznanskiDan Uznanski
6,90021528
$endgroup$
add a comment |
$begingroup$
Let's start with this: a sequence of bits has a $5$-bit streak starting at the $k$th bit if bits $k$ through $k+4$ are all the same and bit $k-1$ either doesn't exist or is different.
So, for an 11-bit number: $2*2^6$ of them will have a streak starting at the $0$th bit, because there are six free bits after the streak; and $6*2*2^5$ of them will have a streak starting at the 1st through 6th bits because committed both before and after there are $5$ free bits. This gives $512$ ways to do it, but there are a few duplicates, which we'll need to find.
It is possible for two streaks to exist if they start 6 or more bits apart and use the same value, or 5 or more bits apart and use different values. This gives 0th and 5th with different streaks, 0th and 6th with same or different streaks, and 1st and 6th with different streaks.
00000111110
00000111111
11111000000
11111000001
00000100000
00000011111
11111011111
11111100000
10000011111
01111100000
There are ten of these and each has been counted twice, so we must subtract $10$ from our initial count, for a total of $502$.
answered Jan 19 at 7:30
Dan UznanskiDan Uznanski
6,90021528
$endgroup$
add a comment |
$begingroup$
Let's start with this: a sequence of bits has a $5$-bit streak starting at the $k$th bit if bits $k$ through $k+4$ are all the same and bit $k-1$ either doesn't exist or is different.
So, for an 11-bit number: $2*2^6$ of them will have a streak starting at the $0$th bit, because there are six free bits after the streak; and $6*2*2^5$ of them will have a streak starting at the 1st through 6th bits because committed both before and after there are $5$ free bits. This gives $512$ ways to do it, but there are a few duplicates, which we'll need to find.
It is possible for two streaks to exist if they start 6 or more bits apart and use the same value, or 5 or more bits apart and use different values. This gives 0th and 5th with different streaks, 0th and 6th with same or different streaks, and 1st and 6th with different streaks.
00000111110
00000111111
11111000000
11111000001
00000100000
00000011111
11111011111
11111100000
10000011111
01111100000
There are ten of these and each has been counted twice, so we must subtract $10$ from our initial count, for a total of $502$.
answered Jan 19 at 7:30
Dan UznanskiDan Uznanski
6,90021528
$endgroup$
Let's start with this: a sequence of bits has a $5$-bit streak starting at the $k$th bit if bits $k$ through $k+4$ are all the same and bit $k-1$ either doesn't exist or is different.
So, for an 11-bit number: $2*2^6$ of them will have a streak starting at the $0$th bit, because there are six free bits after the streak; and $6*2*2^5$ of them will have a streak starting at the 1st through 6th bits because committed both before and after there are $5$ free bits. This gives $512$ ways to do it, but there are a few duplicates, which we'll need to find.
It is possible for two streaks to exist if they start 6 or more bits apart and use the same value, or 5 or more bits apart and use different values. This gives 0th and 5th with different streaks, 0th and 6th with same or different streaks, and 1st and 6th with different streaks.
00000111110
00000111111
11111000000
11111000001
00000100000
00000011111
11111011111
11111100000
10000011111
01111100000
There are ten of these and each has been counted twice, so we must subtract $10$ from our initial count, for a total of $502$.
answered Jan 19 at 7:30
Dan UznanskiDan Uznanski
6,90021528
answered Jan 19 at 7:30
Dan UznanskiDan Uznanski
6,90021528
answered Jan 19 at 7:30
Dan UznanskiDan Uznanski
6,90021528
answered Jan 19 at 7:30
Dan UznanskiDan Uznanski
6,90021528
6,90021528
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%2f3079065%2fhow-many-binary-strings-of-length-11-contain-five-consecutive-0s-or-five-consecu%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$
Welcome to MSE. Here's a MathJax tutorial :)
$endgroup$
– Thomas Shelby
Jan 19 at 6:46