Counting strings: Determine the number of valid strings of length n
Question: Consider strings consisting of characters, where each character is an element of {a; b; c; d}. Such a string is called valid, if it does not contain aa, it does not contain bb, it does not contain cc, and it does not contain dd.
For any integer n >= 2, what is the number of valid strings of length n?
Answer: 4 * 3^(n-1)
Attempt: I took n=4 for a string for the word "baad". Since, a valid string does not have "aa" I counted the possible ways to write "baad" without haveing 2 consecutive a's.
I did this by: 2!*(3C2) and got 6. My answer is way off. I'm assuming my logic doesn't make sense. Can someone please explain to me how to logically approach this.
combinatorics permutations
asked Nov 25 at 19:13
Toby
1577
|
show 2 more comments
Question: Consider strings consisting of characters, where each character is an element of {a; b; c; d}. Such a string is called valid, if it does not contain aa, it does not contain bb, it does not contain cc, and it does not contain dd.
For any integer n >= 2, what is the number of valid strings of length n?
Answer: 4 * 3^(n-1)
Attempt: I took n=4 for a string for the word "baad". Since, a valid string does not have "aa" I counted the possible ways to write "baad" without haveing 2 consecutive a's.
I did this by: 2!*(3C2) and got 6. My answer is way off. I'm assuming my logic doesn't make sense. Can someone please explain to me how to logically approach this.
combinatorics permutations
asked Nov 25 at 19:13
Toby
1577
1
Hint: the first letter can be anything. After that, you have three choices each time.
– lulu
Nov 25 at 19:15
@lulu I still don't get it. If the first letter is 4C1 and the 2nd letter is 3C2 because of the "aa" string, and the last letter is 1C1 that gives me 12. If I substitute n=4 to the answer equation I get 108. Do I take 5!-12 =108? This logic doesn't apply if n=6 for say the word "beldda". I dont know if I'm over thinking this or what
– Toby
Nov 25 at 19:51
2
I don't understand what you mean by "the $aa$ string". Say the string has length $2$. Then there are four candidates for the first letter and, having chosen the first letter, there are three candidates for the second. Hence the answer is $4times 3=12$.
– lulu
Nov 25 at 19:53
2
I don't understand any of your calculations...they don't appear to be connected to the problem. Look at my calculation for length $2$. Now do it for length $3$. You should see that you again have three choices for the third character. Continue in this way.
– lulu
Nov 25 at 19:54
1
You have four choices for the first slot, then three for the second (since you can't match the first), then three for the third (since you can't match the second). Hence $4times 3^2$.
– lulu
Nov 25 at 20:11
|
show 2 more comments
Question: Consider strings consisting of characters, where each character is an element of {a; b; c; d}. Such a string is called valid, if it does not contain aa, it does not contain bb, it does not contain cc, and it does not contain dd.
For any integer n >= 2, what is the number of valid strings of length n?
Answer: 4 * 3^(n-1)
Attempt: I took n=4 for a string for the word "baad". Since, a valid string does not have "aa" I counted the possible ways to write "baad" without haveing 2 consecutive a's.
I did this by: 2!*(3C2) and got 6. My answer is way off. I'm assuming my logic doesn't make sense. Can someone please explain to me how to logically approach this.
combinatorics permutations
asked Nov 25 at 19:13
Toby
1577
Question: Consider strings consisting of characters, where each character is an element of {a; b; c; d}. Such a string is called valid, if it does not contain aa, it does not contain bb, it does not contain cc, and it does not contain dd.
For any integer n >= 2, what is the number of valid strings of length n?
Answer: 4 * 3^(n-1)
Attempt: I took n=4 for a string for the word "baad". Since, a valid string does not have "aa" I counted the possible ways to write "baad" without haveing 2 consecutive a's.
I did this by: 2!*(3C2) and got 6. My answer is way off. I'm assuming my logic doesn't make sense. Can someone please explain to me how to logically approach this.
combinatorics permutations
combinatorics permutations
asked Nov 25 at 19:13
Toby
1577
asked Nov 25 at 19:13
Toby
1577
asked Nov 25 at 19:13
Toby
1577
asked Nov 25 at 19:13
Toby
1577
asked Nov 25 at 19:13
Toby
1577
1577
1
Hint: the first letter can be anything. After that, you have three choices each time.
– lulu
Nov 25 at 19:15
@lulu I still don't get it. If the first letter is 4C1 and the 2nd letter is 3C2 because of the "aa" string, and the last letter is 1C1 that gives me 12. If I substitute n=4 to the answer equation I get 108. Do I take 5!-12 =108? This logic doesn't apply if n=6 for say the word "beldda". I dont know if I'm over thinking this or what
– Toby
Nov 25 at 19:51
2
I don't understand what you mean by "the $aa$ string". Say the string has length $2$. Then there are four candidates for the first letter and, having chosen the first letter, there are three candidates for the second. Hence the answer is $4times 3=12$.
– lulu
Nov 25 at 19:53
2
I don't understand any of your calculations...they don't appear to be connected to the problem. Look at my calculation for length $2$. Now do it for length $3$. You should see that you again have three choices for the third character. Continue in this way.
– lulu
Nov 25 at 19:54
1
You have four choices for the first slot, then three for the second (since you can't match the first), then three for the third (since you can't match the second). Hence $4times 3^2$.
– lulu
Nov 25 at 20:11
|
show 2 more comments
1
Hint: the first letter can be anything. After that, you have three choices each time.
– lulu
Nov 25 at 19:15
@lulu I still don't get it. If the first letter is 4C1 and the 2nd letter is 3C2 because of the "aa" string, and the last letter is 1C1 that gives me 12. If I substitute n=4 to the answer equation I get 108. Do I take 5!-12 =108? This logic doesn't apply if n=6 for say the word "beldda". I dont know if I'm over thinking this or what
– Toby
Nov 25 at 19:51
2
I don't understand what you mean by "the $aa$ string". Say the string has length $2$. Then there are four candidates for the first letter and, having chosen the first letter, there are three candidates for the second. Hence the answer is $4times 3=12$.
– lulu
Nov 25 at 19:53
2
I don't understand any of your calculations...they don't appear to be connected to the problem. Look at my calculation for length $2$. Now do it for length $3$. You should see that you again have three choices for the third character. Continue in this way.
– lulu
Nov 25 at 19:54
1
You have four choices for the first slot, then three for the second (since you can't match the first), then three for the third (since you can't match the second). Hence $4times 3^2$.
– lulu
Nov 25 at 20:11
1
1
Hint: the first letter can be anything. After that, you have three choices each time.
– lulu
Nov 25 at 19:15
Hint: the first letter can be anything. After that, you have three choices each time.
– lulu
Nov 25 at 19:15
@lulu I still don't get it. If the first letter is 4C1 and the 2nd letter is 3C2 because of the "aa" string, and the last letter is 1C1 that gives me 12. If I substitute n=4 to the answer equation I get 108. Do I take 5!-12 =108? This logic doesn't apply if n=6 for say the word "beldda". I dont know if I'm over thinking this or what
– Toby
Nov 25 at 19:51
@lulu I still don't get it. If the first letter is 4C1 and the 2nd letter is 3C2 because of the "aa" string, and the last letter is 1C1 that gives me 12. If I substitute n=4 to the answer equation I get 108. Do I take 5!-12 =108? This logic doesn't apply if n=6 for say the word "beldda". I dont know if I'm over thinking this or what
– Toby
Nov 25 at 19:51
2
2
I don't understand what you mean by "the $aa$ string". Say the string has length $2$. Then there are four candidates for the first letter and, having chosen the first letter, there are three candidates for the second. Hence the answer is $4times 3=12$.
– lulu
Nov 25 at 19:53
I don't understand what you mean by "the $aa$ string". Say the string has length $2$. Then there are four candidates for the first letter and, having chosen the first letter, there are three candidates for the second. Hence the answer is $4times 3=12$.
– lulu
Nov 25 at 19:53
2
2
I don't understand any of your calculations...they don't appear to be connected to the problem. Look at my calculation for length $2$. Now do it for length $3$. You should see that you again have three choices for the third character. Continue in this way.
– lulu
Nov 25 at 19:54
I don't understand any of your calculations...they don't appear to be connected to the problem. Look at my calculation for length $2$. Now do it for length $3$. You should see that you again have three choices for the third character. Continue in this way.
– lulu
Nov 25 at 19:54
1
1
You have four choices for the first slot, then three for the second (since you can't match the first), then three for the third (since you can't match the second). Hence $4times 3^2$.
– lulu
Nov 25 at 20:11
You have four choices for the first slot, then three for the second (since you can't match the first), then three for the third (since you can't match the second). Hence $4times 3^2$.
– lulu
Nov 25 at 20:11
|
show 2 more comments
active
oldest
votes
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%2f3013258%2fcounting-strings-determine-the-number-of-valid-strings-of-length-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3013258%2fcounting-strings-determine-the-number-of-valid-strings-of-length-n%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
1
Hint: the first letter can be anything. After that, you have three choices each time.
– lulu
Nov 25 at 19:15
@lulu I still don't get it. If the first letter is 4C1 and the 2nd letter is 3C2 because of the "aa" string, and the last letter is 1C1 that gives me 12. If I substitute n=4 to the answer equation I get 108. Do I take 5!-12 =108? This logic doesn't apply if n=6 for say the word "beldda". I dont know if I'm over thinking this or what
– Toby
Nov 25 at 19:51
2
I don't understand what you mean by "the $aa$ string". Say the string has length $2$. Then there are four candidates for the first letter and, having chosen the first letter, there are three candidates for the second. Hence the answer is $4times 3=12$.
– lulu
Nov 25 at 19:53
2
I don't understand any of your calculations...they don't appear to be connected to the problem. Look at my calculation for length $2$. Now do it for length $3$. You should see that you again have three choices for the third character. Continue in this way.
– lulu
Nov 25 at 19:54
1
You have four choices for the first slot, then three for the second (since you can't match the first), then three for the third (since you can't match the second). Hence $4times 3^2$.
– lulu
Nov 25 at 20:11