Words of length $n$ containing an odd number of zeros
$begingroup$
Let $a_n$ be the number of words of length $n$ with letters from the alphabet ${0, 1, 2, 3}$
containing an odd number of zeros.
I have already verified that this is given by the recurrence relation:
$$a_{n+1} = 2 a_n + 4^n.$$ where $a_0=0$.
I then used the method of a generating function to solve this and arrive at:
$$a_n= 2^{2n-1} - 2^{n-1}.$$
Which seems to work for the first couple of values, also Wolfram Alpha agrees with my deduction.
This problem can also be solved alternatively, using a new sequence $B_n$, I find this method more difficult but wish to learn it as well. It's more of a combinatorics method, probably using a clever counting argument.
Another way to find the same result is as follows:
1) Consider the set $B_n$ of
words of length $n$ with at least one $0$ or $1$.
How many of those are there?
I am not sure how to express this in terms of $a_n$
2) In
this set there are exactly as many words with an even number of zeros as there are with
an odd number of zeros. Just change the first occuring $0$ or $1$ with its dierence
with $1$ $dots$ (not sure what is meant here, the wording is a bit vague)
I am not sure what the author is getting at, can anybody see where the argument is going and give me some pointers?
combinatorics recurrence-relations
asked Dec 13 '18 at 22:46
Wesley StrikWesley Strik
2,113423
$endgroup$
add a comment |
$begingroup$
Let $a_n$ be the number of words of length $n$ with letters from the alphabet ${0, 1, 2, 3}$
containing an odd number of zeros.
I have already verified that this is given by the recurrence relation:
$$a_{n+1} = 2 a_n + 4^n.$$ where $a_0=0$.
I then used the method of a generating function to solve this and arrive at:
$$a_n= 2^{2n-1} - 2^{n-1}.$$
Which seems to work for the first couple of values, also Wolfram Alpha agrees with my deduction.
This problem can also be solved alternatively, using a new sequence $B_n$, I find this method more difficult but wish to learn it as well. It's more of a combinatorics method, probably using a clever counting argument.
Another way to find the same result is as follows:
1) Consider the set $B_n$ of
words of length $n$ with at least one $0$ or $1$.
How many of those are there?
I am not sure how to express this in terms of $a_n$
2) In
this set there are exactly as many words with an even number of zeros as there are with
an odd number of zeros. Just change the first occuring $0$ or $1$ with its dierence
with $1$ $dots$ (not sure what is meant here, the wording is a bit vague)
I am not sure what the author is getting at, can anybody see where the argument is going and give me some pointers?
combinatorics recurrence-relations
asked Dec 13 '18 at 22:46
Wesley StrikWesley Strik
2,113423
$endgroup$
add a comment |
$begingroup$
Let $a_n$ be the number of words of length $n$ with letters from the alphabet ${0, 1, 2, 3}$
containing an odd number of zeros.
I have already verified that this is given by the recurrence relation:
$$a_{n+1} = 2 a_n + 4^n.$$ where $a_0=0$.
I then used the method of a generating function to solve this and arrive at:
$$a_n= 2^{2n-1} - 2^{n-1}.$$
Which seems to work for the first couple of values, also Wolfram Alpha agrees with my deduction.
This problem can also be solved alternatively, using a new sequence $B_n$, I find this method more difficult but wish to learn it as well. It's more of a combinatorics method, probably using a clever counting argument.
Another way to find the same result is as follows:
1) Consider the set $B_n$ of
words of length $n$ with at least one $0$ or $1$.
How many of those are there?
I am not sure how to express this in terms of $a_n$
2) In
this set there are exactly as many words with an even number of zeros as there are with
an odd number of zeros. Just change the first occuring $0$ or $1$ with its dierence
with $1$ $dots$ (not sure what is meant here, the wording is a bit vague)
I am not sure what the author is getting at, can anybody see where the argument is going and give me some pointers?
combinatorics recurrence-relations
asked Dec 13 '18 at 22:46
Wesley StrikWesley Strik
2,113423
$endgroup$
Let $a_n$ be the number of words of length $n$ with letters from the alphabet ${0, 1, 2, 3}$
containing an odd number of zeros.
I have already verified that this is given by the recurrence relation:
$$a_{n+1} = 2 a_n + 4^n.$$ where $a_0=0$.
I then used the method of a generating function to solve this and arrive at:
$$a_n= 2^{2n-1} - 2^{n-1}.$$
Which seems to work for the first couple of values, also Wolfram Alpha agrees with my deduction.
This problem can also be solved alternatively, using a new sequence $B_n$, I find this method more difficult but wish to learn it as well. It's more of a combinatorics method, probably using a clever counting argument.
Another way to find the same result is as follows:
1) Consider the set $B_n$ of
words of length $n$ with at least one $0$ or $1$.
How many of those are there?
I am not sure how to express this in terms of $a_n$
2) In
this set there are exactly as many words with an even number of zeros as there are with
an odd number of zeros. Just change the first occuring $0$ or $1$ with its dierence
with $1$ $dots$ (not sure what is meant here, the wording is a bit vague)
I am not sure what the author is getting at, can anybody see where the argument is going and give me some pointers?
combinatorics recurrence-relations
combinatorics recurrence-relations
asked Dec 13 '18 at 22:46
Wesley StrikWesley Strik
2,113423
asked Dec 13 '18 at 22:46
Wesley StrikWesley Strik
2,113423
asked Dec 13 '18 at 22:46
Wesley StrikWesley Strik
2,113423
asked Dec 13 '18 at 22:46
Wesley StrikWesley Strik
2,113423
asked Dec 13 '18 at 22:46
Wesley StrikWesley Strik
2,113423
2,113423
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
For (1), we have $|B_n| = 4^n - 2^n$ since there are $4^n$ total strings over the alphabet, and $2^n$ of them have no zeros and no ones.
To expand on (2), let $O_n subset B_n$ be the subset of strings with an odd number of zeros and $E_n subset B_n$ be the subset with an even number of zeros. Note that the function $f : O_n to E_n$ which on input $x$ replaces the first $0$ or $1$ in $x$ with $1$ or $0$, respectively, is a bijection. Thus $a_n = |O_n| = |E_n|$, and further, $O_n$ and $E_n$ partition $B_n$, so each has size $frac{1}{2}(4^n - 2^n)$.
answered Dec 13 '18 at 23:07
Zach LangleyZach Langley
9731019
$endgroup$
$begingroup$
That is indeed an elegant way to derive the same result, the bijection is very satisfying, thank you.
$endgroup$
– Wesley Strik
Dec 14 '18 at 6:44
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%2f3038688%2fwords-of-length-n-containing-an-odd-number-of-zeros%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$
For (1), we have $|B_n| = 4^n - 2^n$ since there are $4^n$ total strings over the alphabet, and $2^n$ of them have no zeros and no ones.
To expand on (2), let $O_n subset B_n$ be the subset of strings with an odd number of zeros and $E_n subset B_n$ be the subset with an even number of zeros. Note that the function $f : O_n to E_n$ which on input $x$ replaces the first $0$ or $1$ in $x$ with $1$ or $0$, respectively, is a bijection. Thus $a_n = |O_n| = |E_n|$, and further, $O_n$ and $E_n$ partition $B_n$, so each has size $frac{1}{2}(4^n - 2^n)$.
answered Dec 13 '18 at 23:07
Zach LangleyZach Langley
9731019
$endgroup$
$begingroup$
That is indeed an elegant way to derive the same result, the bijection is very satisfying, thank you.
$endgroup$
– Wesley Strik
Dec 14 '18 at 6:44
add a comment |
$begingroup$
For (1), we have $|B_n| = 4^n - 2^n$ since there are $4^n$ total strings over the alphabet, and $2^n$ of them have no zeros and no ones.
To expand on (2), let $O_n subset B_n$ be the subset of strings with an odd number of zeros and $E_n subset B_n$ be the subset with an even number of zeros. Note that the function $f : O_n to E_n$ which on input $x$ replaces the first $0$ or $1$ in $x$ with $1$ or $0$, respectively, is a bijection. Thus $a_n = |O_n| = |E_n|$, and further, $O_n$ and $E_n$ partition $B_n$, so each has size $frac{1}{2}(4^n - 2^n)$.
answered Dec 13 '18 at 23:07
Zach LangleyZach Langley
9731019
$endgroup$
$begingroup$
That is indeed an elegant way to derive the same result, the bijection is very satisfying, thank you.
$endgroup$
– Wesley Strik
Dec 14 '18 at 6:44
add a comment |
$begingroup$
For (1), we have $|B_n| = 4^n - 2^n$ since there are $4^n$ total strings over the alphabet, and $2^n$ of them have no zeros and no ones.
To expand on (2), let $O_n subset B_n$ be the subset of strings with an odd number of zeros and $E_n subset B_n$ be the subset with an even number of zeros. Note that the function $f : O_n to E_n$ which on input $x$ replaces the first $0$ or $1$ in $x$ with $1$ or $0$, respectively, is a bijection. Thus $a_n = |O_n| = |E_n|$, and further, $O_n$ and $E_n$ partition $B_n$, so each has size $frac{1}{2}(4^n - 2^n)$.
answered Dec 13 '18 at 23:07
Zach LangleyZach Langley
9731019
$endgroup$
For (1), we have $|B_n| = 4^n - 2^n$ since there are $4^n$ total strings over the alphabet, and $2^n$ of them have no zeros and no ones.
To expand on (2), let $O_n subset B_n$ be the subset of strings with an odd number of zeros and $E_n subset B_n$ be the subset with an even number of zeros. Note that the function $f : O_n to E_n$ which on input $x$ replaces the first $0$ or $1$ in $x$ with $1$ or $0$, respectively, is a bijection. Thus $a_n = |O_n| = |E_n|$, and further, $O_n$ and $E_n$ partition $B_n$, so each has size $frac{1}{2}(4^n - 2^n)$.
answered Dec 13 '18 at 23:07
Zach LangleyZach Langley
9731019
edited Feb 1 at 21:00
answered Dec 13 '18 at 23:07
Zach LangleyZach Langley
9731019
answered Dec 13 '18 at 23:07
Zach LangleyZach Langley
9731019
answered Dec 13 '18 at 23:07
Zach LangleyZach Langley
9731019
9731019
$begingroup$
That is indeed an elegant way to derive the same result, the bijection is very satisfying, thank you.
$endgroup$
– Wesley Strik
Dec 14 '18 at 6:44
add a comment |
$begingroup$
That is indeed an elegant way to derive the same result, the bijection is very satisfying, thank you.
$endgroup$
– Wesley Strik
Dec 14 '18 at 6:44
$begingroup$
That is indeed an elegant way to derive the same result, the bijection is very satisfying, thank you.
$endgroup$
– Wesley Strik
Dec 14 '18 at 6:44
$begingroup$
That is indeed an elegant way to derive the same result, the bijection is very satisfying, thank you.
$endgroup$
– Wesley Strik
Dec 14 '18 at 6:44
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%2f3038688%2fwords-of-length-n-containing-an-odd-number-of-zeros%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
