Counting: How do I get the number of bit strings of length n without always having to type all of them out?
$begingroup$
Take these 2 questions as scenarios where I struggle to think logically on how to calculate these the non-tedious way.
For Q7)
I took n=6:
-X- -0- -X- -0- -X- -0- Here 0 is at even position fixed
Then I took the long approach of checking out each scenario where 101 doesn't occur, I got:
000000, 100010, 001000, 100000, 000010 = 5 strings
I did the same for, S0, S1, S2, S5, S4 and then got final answer D.
For Question 8)
I literally type out all 16 scenarios and get 0000, 0001, 1000 for n=4, same thing with n=3 and n=2. Then after all that I get the answer to be B. But again, there has to be an easier method that I just am not aware of or haven't thought of.
There has to be an easier way to count these? It takes way too much time to hand write this but I don't know what this method is.
Please can someone help me figure out a way to solve these types of problems the easier/ faster more logical way
combinatorics discrete-mathematics permutations
asked Dec 18 '18 at 2:45
TobyToby
1577
$endgroup$
add a comment |
$begingroup$
Take these 2 questions as scenarios where I struggle to think logically on how to calculate these the non-tedious way.
For Q7)
I took n=6:
-X- -0- -X- -0- -X- -0- Here 0 is at even position fixed
Then I took the long approach of checking out each scenario where 101 doesn't occur, I got:
000000, 100010, 001000, 100000, 000010 = 5 strings
I did the same for, S0, S1, S2, S5, S4 and then got final answer D.
For Question 8)
I literally type out all 16 scenarios and get 0000, 0001, 1000 for n=4, same thing with n=3 and n=2. Then after all that I get the answer to be B. But again, there has to be an easier method that I just am not aware of or haven't thought of.
There has to be an easier way to count these? It takes way too much time to hand write this but I don't know what this method is.
Please can someone help me figure out a way to solve these types of problems the easier/ faster more logical way
combinatorics discrete-mathematics permutations
asked Dec 18 '18 at 2:45
TobyToby
1577
$endgroup$
3
$begingroup$
From a test taking perspective, you can solve 7 by noting that $S_n$ is only defined for even $n$ and choices $a,b,c$ involve odd indices so it must be $d$.
$endgroup$
– Ross Millikan
Dec 18 '18 at 2:53
$begingroup$
Without the tricks of multiple choice, the idea is to think recursively. For 7, if the first two bits are 00 then..., if the first two bits are 10 then the next cannot be 1 so we must have the first 4 bits being 1000 and...
$endgroup$
– Michael
Dec 18 '18 at 3:14
add a comment |
$begingroup$
Take these 2 questions as scenarios where I struggle to think logically on how to calculate these the non-tedious way.
For Q7)
I took n=6:
-X- -0- -X- -0- -X- -0- Here 0 is at even position fixed
Then I took the long approach of checking out each scenario where 101 doesn't occur, I got:
000000, 100010, 001000, 100000, 000010 = 5 strings
I did the same for, S0, S1, S2, S5, S4 and then got final answer D.
For Question 8)
I literally type out all 16 scenarios and get 0000, 0001, 1000 for n=4, same thing with n=3 and n=2. Then after all that I get the answer to be B. But again, there has to be an easier method that I just am not aware of or haven't thought of.
There has to be an easier way to count these? It takes way too much time to hand write this but I don't know what this method is.
Please can someone help me figure out a way to solve these types of problems the easier/ faster more logical way
combinatorics discrete-mathematics permutations
asked Dec 18 '18 at 2:45
TobyToby
1577
$endgroup$
Take these 2 questions as scenarios where I struggle to think logically on how to calculate these the non-tedious way.
For Q7)
I took n=6:
-X- -0- -X- -0- -X- -0- Here 0 is at even position fixed
Then I took the long approach of checking out each scenario where 101 doesn't occur, I got:
000000, 100010, 001000, 100000, 000010 = 5 strings
I did the same for, S0, S1, S2, S5, S4 and then got final answer D.
For Question 8)
I literally type out all 16 scenarios and get 0000, 0001, 1000 for n=4, same thing with n=3 and n=2. Then after all that I get the answer to be B. But again, there has to be an easier method that I just am not aware of or haven't thought of.
There has to be an easier way to count these? It takes way too much time to hand write this but I don't know what this method is.
Please can someone help me figure out a way to solve these types of problems the easier/ faster more logical way
combinatorics discrete-mathematics permutations
combinatorics discrete-mathematics permutations
asked Dec 18 '18 at 2:45
TobyToby
1577
asked Dec 18 '18 at 2:45
TobyToby
1577
asked Dec 18 '18 at 2:45
TobyToby
1577
asked Dec 18 '18 at 2:45
TobyToby
1577
asked Dec 18 '18 at 2:45
TobyToby
1577
1577
3
$begingroup$
From a test taking perspective, you can solve 7 by noting that $S_n$ is only defined for even $n$ and choices $a,b,c$ involve odd indices so it must be $d$.
$endgroup$
– Ross Millikan
Dec 18 '18 at 2:53
$begingroup$
Without the tricks of multiple choice, the idea is to think recursively. For 7, if the first two bits are 00 then..., if the first two bits are 10 then the next cannot be 1 so we must have the first 4 bits being 1000 and...
$endgroup$
– Michael
Dec 18 '18 at 3:14
add a comment |
3
$begingroup$
From a test taking perspective, you can solve 7 by noting that $S_n$ is only defined for even $n$ and choices $a,b,c$ involve odd indices so it must be $d$.
$endgroup$
– Ross Millikan
Dec 18 '18 at 2:53
$begingroup$
Without the tricks of multiple choice, the idea is to think recursively. For 7, if the first two bits are 00 then..., if the first two bits are 10 then the next cannot be 1 so we must have the first 4 bits being 1000 and...
$endgroup$
– Michael
Dec 18 '18 at 3:14
3
3
$begingroup$
From a test taking perspective, you can solve 7 by noting that $S_n$ is only defined for even $n$ and choices $a,b,c$ involve odd indices so it must be $d$.
$endgroup$
– Ross Millikan
Dec 18 '18 at 2:53
$begingroup$
From a test taking perspective, you can solve 7 by noting that $S_n$ is only defined for even $n$ and choices $a,b,c$ involve odd indices so it must be $d$.
$endgroup$
– Ross Millikan
Dec 18 '18 at 2:53
$begingroup$
Without the tricks of multiple choice, the idea is to think recursively. For 7, if the first two bits are 00 then..., if the first two bits are 10 then the next cannot be 1 so we must have the first 4 bits being 1000 and...
$endgroup$
– Michael
Dec 18 '18 at 3:14
$begingroup$
Without the tricks of multiple choice, the idea is to think recursively. For 7, if the first two bits are 00 then..., if the first two bits are 10 then the next cannot be 1 so we must have the first 4 bits being 1000 and...
$endgroup$
– Michael
Dec 18 '18 at 3:14
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The idea is to think of how you make a string of length $n$ by starting with a shorter string and adding more characters. The challenge is to find a way that you can generate every string of length $n$ once and only once.
For 7 we can ignore all the zeros in even positions and ask the number of strings of length $frac n2$ that do not contain $11$. That is asked and answered several times on this site and the answer is the Fibonacci sequence. If we want a string of length $n$ that does not include $11$, we can start with a string of length $n-1$ and append a $0$, which gets all the $n$ bit strings that end in $0$, or we can start with a string of length $n-2$ and append $01$, which gets all the legal $n$ bit strings that end in $1$. If $A(n)$ is the number of $n$ bit strings without $11$ we get $A(n)=A(n-1)+A(n-2)$, which is the Fibonacci recursion. Putting back in the zeros in your problem we have $S_n=S_{n-2}+S_{n-4}$.
For 8 to get an $n$ bit string you can start with $1$ and append an acceptable $n-1$ bit string, with $01$ and append an acceptable $n-2$ bit string, with $001$ and append an acceptable $n-3$ bit string, or with $000$ and append any $n-3$ bit string. I think the exponent on the $2$ should be $n-3$. That is supported by $S_3=1$ and $S_4=3$.
answered Dec 18 '18 at 3:14
Ross MillikanRoss Millikan
299k24200374
$endgroup$
$begingroup$
I am trying to analyze your method and I'm getting confused quite a bit..For 8) do you just arbitrarily start with a bitstring of length n and start appending random bitstrings? Like, I don't understand the "acceptable bitstring" nor do I get why you are choosing 01, then 001 and then 000. I also dont get your conclusion of the exponent 2 ^ n-3. I'm so lost
$endgroup$
– Toby
Dec 18 '18 at 3:55
$begingroup$
No, I am trying to create a bitstring of length $n$ by taking a shorter one and adding bits. An acceptable string for this problem is one that already includes $000$. The point is that prepending $1,01$ or $001$ cannot create a $000$ so it must have been there already. If I start with $000$ I don't care if the rest of the string has $000$ or not because I already have one. The challenge is to not think of just starting with $0$, because you don't have a clear picture of what strings can be appended to it. $0$ can make $000$ with strings that start with $00$. You have to avoid dblcounting
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:02
$begingroup$
OK I still don't see it but I'm going to try. The question ask for at least one 000 occurence. So, I can start with a 000. And prepend 1, 01, 001 to it? What about 101, 111, or 011? And where is this exponential coming from? Is there a step by step way for this that I can follow, I just can't see it
$endgroup$
– Toby
Dec 18 '18 at 4:14
$begingroup$
The 000 can come at any position in the string. For an $n$ bit string you can start with $000$ and append any $n-3$ bit string to it. There are $2^{n-3}$ of those, which is where the exponential comes from. Otherwise, you need to take a shorter string that already includes $000$ somewhere and prepend something to make it $n$ bits long. That is where all the $S$ terms come from. I can see you are not getting the idea of constructing strings from shorter ones, but I don't know how to explain it better.
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:27
$begingroup$
For a question where 110 is not allowed, n>=4, how will the approach work? Do I start with n-1 here?
$endgroup$
– Toby
Dec 18 '18 at 4:39
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%2f3044723%2fcounting-how-do-i-get-the-number-of-bit-strings-of-length-n-without-always-havi%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$
The idea is to think of how you make a string of length $n$ by starting with a shorter string and adding more characters. The challenge is to find a way that you can generate every string of length $n$ once and only once.
For 7 we can ignore all the zeros in even positions and ask the number of strings of length $frac n2$ that do not contain $11$. That is asked and answered several times on this site and the answer is the Fibonacci sequence. If we want a string of length $n$ that does not include $11$, we can start with a string of length $n-1$ and append a $0$, which gets all the $n$ bit strings that end in $0$, or we can start with a string of length $n-2$ and append $01$, which gets all the legal $n$ bit strings that end in $1$. If $A(n)$ is the number of $n$ bit strings without $11$ we get $A(n)=A(n-1)+A(n-2)$, which is the Fibonacci recursion. Putting back in the zeros in your problem we have $S_n=S_{n-2}+S_{n-4}$.
For 8 to get an $n$ bit string you can start with $1$ and append an acceptable $n-1$ bit string, with $01$ and append an acceptable $n-2$ bit string, with $001$ and append an acceptable $n-3$ bit string, or with $000$ and append any $n-3$ bit string. I think the exponent on the $2$ should be $n-3$. That is supported by $S_3=1$ and $S_4=3$.
answered Dec 18 '18 at 3:14
Ross MillikanRoss Millikan
299k24200374
$endgroup$
$begingroup$
I am trying to analyze your method and I'm getting confused quite a bit..For 8) do you just arbitrarily start with a bitstring of length n and start appending random bitstrings? Like, I don't understand the "acceptable bitstring" nor do I get why you are choosing 01, then 001 and then 000. I also dont get your conclusion of the exponent 2 ^ n-3. I'm so lost
$endgroup$
– Toby
Dec 18 '18 at 3:55
$begingroup$
No, I am trying to create a bitstring of length $n$ by taking a shorter one and adding bits. An acceptable string for this problem is one that already includes $000$. The point is that prepending $1,01$ or $001$ cannot create a $000$ so it must have been there already. If I start with $000$ I don't care if the rest of the string has $000$ or not because I already have one. The challenge is to not think of just starting with $0$, because you don't have a clear picture of what strings can be appended to it. $0$ can make $000$ with strings that start with $00$. You have to avoid dblcounting
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:02
$begingroup$
OK I still don't see it but I'm going to try. The question ask for at least one 000 occurence. So, I can start with a 000. And prepend 1, 01, 001 to it? What about 101, 111, or 011? And where is this exponential coming from? Is there a step by step way for this that I can follow, I just can't see it
$endgroup$
– Toby
Dec 18 '18 at 4:14
$begingroup$
The 000 can come at any position in the string. For an $n$ bit string you can start with $000$ and append any $n-3$ bit string to it. There are $2^{n-3}$ of those, which is where the exponential comes from. Otherwise, you need to take a shorter string that already includes $000$ somewhere and prepend something to make it $n$ bits long. That is where all the $S$ terms come from. I can see you are not getting the idea of constructing strings from shorter ones, but I don't know how to explain it better.
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:27
$begingroup$
For a question where 110 is not allowed, n>=4, how will the approach work? Do I start with n-1 here?
$endgroup$
– Toby
Dec 18 '18 at 4:39
add a comment |
$begingroup$
The idea is to think of how you make a string of length $n$ by starting with a shorter string and adding more characters. The challenge is to find a way that you can generate every string of length $n$ once and only once.
For 7 we can ignore all the zeros in even positions and ask the number of strings of length $frac n2$ that do not contain $11$. That is asked and answered several times on this site and the answer is the Fibonacci sequence. If we want a string of length $n$ that does not include $11$, we can start with a string of length $n-1$ and append a $0$, which gets all the $n$ bit strings that end in $0$, or we can start with a string of length $n-2$ and append $01$, which gets all the legal $n$ bit strings that end in $1$. If $A(n)$ is the number of $n$ bit strings without $11$ we get $A(n)=A(n-1)+A(n-2)$, which is the Fibonacci recursion. Putting back in the zeros in your problem we have $S_n=S_{n-2}+S_{n-4}$.
For 8 to get an $n$ bit string you can start with $1$ and append an acceptable $n-1$ bit string, with $01$ and append an acceptable $n-2$ bit string, with $001$ and append an acceptable $n-3$ bit string, or with $000$ and append any $n-3$ bit string. I think the exponent on the $2$ should be $n-3$. That is supported by $S_3=1$ and $S_4=3$.
answered Dec 18 '18 at 3:14
Ross MillikanRoss Millikan
299k24200374
$endgroup$
$begingroup$
I am trying to analyze your method and I'm getting confused quite a bit..For 8) do you just arbitrarily start with a bitstring of length n and start appending random bitstrings? Like, I don't understand the "acceptable bitstring" nor do I get why you are choosing 01, then 001 and then 000. I also dont get your conclusion of the exponent 2 ^ n-3. I'm so lost
$endgroup$
– Toby
Dec 18 '18 at 3:55
$begingroup$
No, I am trying to create a bitstring of length $n$ by taking a shorter one and adding bits. An acceptable string for this problem is one that already includes $000$. The point is that prepending $1,01$ or $001$ cannot create a $000$ so it must have been there already. If I start with $000$ I don't care if the rest of the string has $000$ or not because I already have one. The challenge is to not think of just starting with $0$, because you don't have a clear picture of what strings can be appended to it. $0$ can make $000$ with strings that start with $00$. You have to avoid dblcounting
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:02
$begingroup$
OK I still don't see it but I'm going to try. The question ask for at least one 000 occurence. So, I can start with a 000. And prepend 1, 01, 001 to it? What about 101, 111, or 011? And where is this exponential coming from? Is there a step by step way for this that I can follow, I just can't see it
$endgroup$
– Toby
Dec 18 '18 at 4:14
$begingroup$
The 000 can come at any position in the string. For an $n$ bit string you can start with $000$ and append any $n-3$ bit string to it. There are $2^{n-3}$ of those, which is where the exponential comes from. Otherwise, you need to take a shorter string that already includes $000$ somewhere and prepend something to make it $n$ bits long. That is where all the $S$ terms come from. I can see you are not getting the idea of constructing strings from shorter ones, but I don't know how to explain it better.
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:27
$begingroup$
For a question where 110 is not allowed, n>=4, how will the approach work? Do I start with n-1 here?
$endgroup$
– Toby
Dec 18 '18 at 4:39
add a comment |
$begingroup$
The idea is to think of how you make a string of length $n$ by starting with a shorter string and adding more characters. The challenge is to find a way that you can generate every string of length $n$ once and only once.
For 7 we can ignore all the zeros in even positions and ask the number of strings of length $frac n2$ that do not contain $11$. That is asked and answered several times on this site and the answer is the Fibonacci sequence. If we want a string of length $n$ that does not include $11$, we can start with a string of length $n-1$ and append a $0$, which gets all the $n$ bit strings that end in $0$, or we can start with a string of length $n-2$ and append $01$, which gets all the legal $n$ bit strings that end in $1$. If $A(n)$ is the number of $n$ bit strings without $11$ we get $A(n)=A(n-1)+A(n-2)$, which is the Fibonacci recursion. Putting back in the zeros in your problem we have $S_n=S_{n-2}+S_{n-4}$.
For 8 to get an $n$ bit string you can start with $1$ and append an acceptable $n-1$ bit string, with $01$ and append an acceptable $n-2$ bit string, with $001$ and append an acceptable $n-3$ bit string, or with $000$ and append any $n-3$ bit string. I think the exponent on the $2$ should be $n-3$. That is supported by $S_3=1$ and $S_4=3$.
answered Dec 18 '18 at 3:14
Ross MillikanRoss Millikan
299k24200374
$endgroup$
The idea is to think of how you make a string of length $n$ by starting with a shorter string and adding more characters. The challenge is to find a way that you can generate every string of length $n$ once and only once.
For 7 we can ignore all the zeros in even positions and ask the number of strings of length $frac n2$ that do not contain $11$. That is asked and answered several times on this site and the answer is the Fibonacci sequence. If we want a string of length $n$ that does not include $11$, we can start with a string of length $n-1$ and append a $0$, which gets all the $n$ bit strings that end in $0$, or we can start with a string of length $n-2$ and append $01$, which gets all the legal $n$ bit strings that end in $1$. If $A(n)$ is the number of $n$ bit strings without $11$ we get $A(n)=A(n-1)+A(n-2)$, which is the Fibonacci recursion. Putting back in the zeros in your problem we have $S_n=S_{n-2}+S_{n-4}$.
For 8 to get an $n$ bit string you can start with $1$ and append an acceptable $n-1$ bit string, with $01$ and append an acceptable $n-2$ bit string, with $001$ and append an acceptable $n-3$ bit string, or with $000$ and append any $n-3$ bit string. I think the exponent on the $2$ should be $n-3$. That is supported by $S_3=1$ and $S_4=3$.
answered Dec 18 '18 at 3:14
Ross MillikanRoss Millikan
299k24200374
answered Dec 18 '18 at 3:14
Ross MillikanRoss Millikan
299k24200374
answered Dec 18 '18 at 3:14
Ross MillikanRoss Millikan
299k24200374
answered Dec 18 '18 at 3:14
Ross MillikanRoss Millikan
299k24200374
299k24200374
$begingroup$
I am trying to analyze your method and I'm getting confused quite a bit..For 8) do you just arbitrarily start with a bitstring of length n and start appending random bitstrings? Like, I don't understand the "acceptable bitstring" nor do I get why you are choosing 01, then 001 and then 000. I also dont get your conclusion of the exponent 2 ^ n-3. I'm so lost
$endgroup$
– Toby
Dec 18 '18 at 3:55
$begingroup$
No, I am trying to create a bitstring of length $n$ by taking a shorter one and adding bits. An acceptable string for this problem is one that already includes $000$. The point is that prepending $1,01$ or $001$ cannot create a $000$ so it must have been there already. If I start with $000$ I don't care if the rest of the string has $000$ or not because I already have one. The challenge is to not think of just starting with $0$, because you don't have a clear picture of what strings can be appended to it. $0$ can make $000$ with strings that start with $00$. You have to avoid dblcounting
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:02
$begingroup$
OK I still don't see it but I'm going to try. The question ask for at least one 000 occurence. So, I can start with a 000. And prepend 1, 01, 001 to it? What about 101, 111, or 011? And where is this exponential coming from? Is there a step by step way for this that I can follow, I just can't see it
$endgroup$
– Toby
Dec 18 '18 at 4:14
$begingroup$
The 000 can come at any position in the string. For an $n$ bit string you can start with $000$ and append any $n-3$ bit string to it. There are $2^{n-3}$ of those, which is where the exponential comes from. Otherwise, you need to take a shorter string that already includes $000$ somewhere and prepend something to make it $n$ bits long. That is where all the $S$ terms come from. I can see you are not getting the idea of constructing strings from shorter ones, but I don't know how to explain it better.
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:27
$begingroup$
For a question where 110 is not allowed, n>=4, how will the approach work? Do I start with n-1 here?
$endgroup$
– Toby
Dec 18 '18 at 4:39
add a comment |
$begingroup$
I am trying to analyze your method and I'm getting confused quite a bit..For 8) do you just arbitrarily start with a bitstring of length n and start appending random bitstrings? Like, I don't understand the "acceptable bitstring" nor do I get why you are choosing 01, then 001 and then 000. I also dont get your conclusion of the exponent 2 ^ n-3. I'm so lost
$endgroup$
– Toby
Dec 18 '18 at 3:55
$begingroup$
No, I am trying to create a bitstring of length $n$ by taking a shorter one and adding bits. An acceptable string for this problem is one that already includes $000$. The point is that prepending $1,01$ or $001$ cannot create a $000$ so it must have been there already. If I start with $000$ I don't care if the rest of the string has $000$ or not because I already have one. The challenge is to not think of just starting with $0$, because you don't have a clear picture of what strings can be appended to it. $0$ can make $000$ with strings that start with $00$. You have to avoid dblcounting
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:02
$begingroup$
OK I still don't see it but I'm going to try. The question ask for at least one 000 occurence. So, I can start with a 000. And prepend 1, 01, 001 to it? What about 101, 111, or 011? And where is this exponential coming from? Is there a step by step way for this that I can follow, I just can't see it
$endgroup$
– Toby
Dec 18 '18 at 4:14
$begingroup$
The 000 can come at any position in the string. For an $n$ bit string you can start with $000$ and append any $n-3$ bit string to it. There are $2^{n-3}$ of those, which is where the exponential comes from. Otherwise, you need to take a shorter string that already includes $000$ somewhere and prepend something to make it $n$ bits long. That is where all the $S$ terms come from. I can see you are not getting the idea of constructing strings from shorter ones, but I don't know how to explain it better.
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:27
$begingroup$
For a question where 110 is not allowed, n>=4, how will the approach work? Do I start with n-1 here?
$endgroup$
– Toby
Dec 18 '18 at 4:39
$begingroup$
I am trying to analyze your method and I'm getting confused quite a bit..For 8) do you just arbitrarily start with a bitstring of length n and start appending random bitstrings? Like, I don't understand the "acceptable bitstring" nor do I get why you are choosing 01, then 001 and then 000. I also dont get your conclusion of the exponent 2 ^ n-3. I'm so lost
$endgroup$
– Toby
Dec 18 '18 at 3:55
$begingroup$
I am trying to analyze your method and I'm getting confused quite a bit..For 8) do you just arbitrarily start with a bitstring of length n and start appending random bitstrings? Like, I don't understand the "acceptable bitstring" nor do I get why you are choosing 01, then 001 and then 000. I also dont get your conclusion of the exponent 2 ^ n-3. I'm so lost
$endgroup$
– Toby
Dec 18 '18 at 3:55
$begingroup$
No, I am trying to create a bitstring of length $n$ by taking a shorter one and adding bits. An acceptable string for this problem is one that already includes $000$. The point is that prepending $1,01$ or $001$ cannot create a $000$ so it must have been there already. If I start with $000$ I don't care if the rest of the string has $000$ or not because I already have one. The challenge is to not think of just starting with $0$, because you don't have a clear picture of what strings can be appended to it. $0$ can make $000$ with strings that start with $00$. You have to avoid dblcounting
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:02
$begingroup$
No, I am trying to create a bitstring of length $n$ by taking a shorter one and adding bits. An acceptable string for this problem is one that already includes $000$. The point is that prepending $1,01$ or $001$ cannot create a $000$ so it must have been there already. If I start with $000$ I don't care if the rest of the string has $000$ or not because I already have one. The challenge is to not think of just starting with $0$, because you don't have a clear picture of what strings can be appended to it. $0$ can make $000$ with strings that start with $00$. You have to avoid dblcounting
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:02
$begingroup$
OK I still don't see it but I'm going to try. The question ask for at least one 000 occurence. So, I can start with a 000. And prepend 1, 01, 001 to it? What about 101, 111, or 011? And where is this exponential coming from? Is there a step by step way for this that I can follow, I just can't see it
$endgroup$
– Toby
Dec 18 '18 at 4:14
$begingroup$
OK I still don't see it but I'm going to try. The question ask for at least one 000 occurence. So, I can start with a 000. And prepend 1, 01, 001 to it? What about 101, 111, or 011? And where is this exponential coming from? Is there a step by step way for this that I can follow, I just can't see it
$endgroup$
– Toby
Dec 18 '18 at 4:14
$begingroup$
The 000 can come at any position in the string. For an $n$ bit string you can start with $000$ and append any $n-3$ bit string to it. There are $2^{n-3}$ of those, which is where the exponential comes from. Otherwise, you need to take a shorter string that already includes $000$ somewhere and prepend something to make it $n$ bits long. That is where all the $S$ terms come from. I can see you are not getting the idea of constructing strings from shorter ones, but I don't know how to explain it better.
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:27
$begingroup$
The 000 can come at any position in the string. For an $n$ bit string you can start with $000$ and append any $n-3$ bit string to it. There are $2^{n-3}$ of those, which is where the exponential comes from. Otherwise, you need to take a shorter string that already includes $000$ somewhere and prepend something to make it $n$ bits long. That is where all the $S$ terms come from. I can see you are not getting the idea of constructing strings from shorter ones, but I don't know how to explain it better.
$endgroup$
– Ross Millikan
Dec 18 '18 at 4:27
$begingroup$
For a question where 110 is not allowed, n>=4, how will the approach work? Do I start with n-1 here?
$endgroup$
– Toby
Dec 18 '18 at 4:39
$begingroup$
For a question where 110 is not allowed, n>=4, how will the approach work? Do I start with n-1 here?
$endgroup$
– Toby
Dec 18 '18 at 4:39
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%2f3044723%2fcounting-how-do-i-get-the-number-of-bit-strings-of-length-n-without-always-havi%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
3
$begingroup$
From a test taking perspective, you can solve 7 by noting that $S_n$ is only defined for even $n$ and choices $a,b,c$ involve odd indices so it must be $d$.
$endgroup$
– Ross Millikan
Dec 18 '18 at 2:53
$begingroup$
Without the tricks of multiple choice, the idea is to think recursively. For 7, if the first two bits are 00 then..., if the first two bits are 10 then the next cannot be 1 so we must have the first 4 bits being 1000 and...
$endgroup$
– Michael
Dec 18 '18 at 3:14