Show that the number of sequences of length 40 are there using the alphabet {a,b,c,d}
Show that the number of sequences of length 40 are there using the alphabet {a,b,c,d} such that number of a's in the sequence is divisible by 3 is $frac{4^{40}+2Re((3+w)^{40})}{3}$
sequence with 3 a's=$40C3times3^{(40-3)}$
sequence with 6 a's=$40C6times 3^{(40-6)}$
sequence with 9 a's=$40C9times3^{(40-9)}$
.
.
sequence with 36 a's=$40C36times3^{(40-36)}$
sequence with 39 a's=$40C39times3^{(40-39)}$
I'm stuck as to where the Re and $w$ come into play
combinatorics
add a comment |
Show that the number of sequences of length 40 are there using the alphabet {a,b,c,d} such that number of a's in the sequence is divisible by 3 is $frac{4^{40}+2Re((3+w)^{40})}{3}$
sequence with 3 a's=$40C3times3^{(40-3)}$
sequence with 6 a's=$40C6times 3^{(40-6)}$
sequence with 9 a's=$40C9times3^{(40-9)}$
.
.
sequence with 36 a's=$40C36times3^{(40-36)}$
sequence with 39 a's=$40C39times3^{(40-39)}$
I'm stuck as to where the Re and $w$ come into play
combinatorics
1
The $w$ might be $omega$, a unit cube root in $mathbb{C}$..
– Henno Brandsma
Dec 2 at 10:29
1
Use the same technique as here. Instead of $(1+x)^{40}$ with $x=1,omega,omega^2$, you will be needing $(3+x)^{40}$ with $x=1,omega,omega^2$. Do you see why?
– Jyrki Lahtonen
Dec 2 at 10:34
Yes after the solution down there , I now fully understand
– Tariro Manyika
Dec 2 at 21:11
That's great. TariroManyika !
– Jyrki Lahtonen
Dec 5 at 19:47
add a comment |
Show that the number of sequences of length 40 are there using the alphabet {a,b,c,d} such that number of a's in the sequence is divisible by 3 is $frac{4^{40}+2Re((3+w)^{40})}{3}$
sequence with 3 a's=$40C3times3^{(40-3)}$
sequence with 6 a's=$40C6times 3^{(40-6)}$
sequence with 9 a's=$40C9times3^{(40-9)}$
.
.
sequence with 36 a's=$40C36times3^{(40-36)}$
sequence with 39 a's=$40C39times3^{(40-39)}$
I'm stuck as to where the Re and $w$ come into play
combinatorics
Show that the number of sequences of length 40 are there using the alphabet {a,b,c,d} such that number of a's in the sequence is divisible by 3 is $frac{4^{40}+2Re((3+w)^{40})}{3}$
sequence with 3 a's=$40C3times3^{(40-3)}$
sequence with 6 a's=$40C6times 3^{(40-6)}$
sequence with 9 a's=$40C9times3^{(40-9)}$
.
.
sequence with 36 a's=$40C36times3^{(40-36)}$
sequence with 39 a's=$40C39times3^{(40-39)}$
I'm stuck as to where the Re and $w$ come into play
combinatorics
combinatorics
asked Dec 2 at 10:20
Tariro Manyika
62
62
1
The $w$ might be $omega$, a unit cube root in $mathbb{C}$..
– Henno Brandsma
Dec 2 at 10:29
1
Use the same technique as here. Instead of $(1+x)^{40}$ with $x=1,omega,omega^2$, you will be needing $(3+x)^{40}$ with $x=1,omega,omega^2$. Do you see why?
– Jyrki Lahtonen
Dec 2 at 10:34
Yes after the solution down there , I now fully understand
– Tariro Manyika
Dec 2 at 21:11
That's great. TariroManyika !
– Jyrki Lahtonen
Dec 5 at 19:47
add a comment |
1
The $w$ might be $omega$, a unit cube root in $mathbb{C}$..
– Henno Brandsma
Dec 2 at 10:29
1
Use the same technique as here. Instead of $(1+x)^{40}$ with $x=1,omega,omega^2$, you will be needing $(3+x)^{40}$ with $x=1,omega,omega^2$. Do you see why?
– Jyrki Lahtonen
Dec 2 at 10:34
Yes after the solution down there , I now fully understand
– Tariro Manyika
Dec 2 at 21:11
That's great. TariroManyika !
– Jyrki Lahtonen
Dec 5 at 19:47
1
1
The $w$ might be $omega$, a unit cube root in $mathbb{C}$..
– Henno Brandsma
Dec 2 at 10:29
The $w$ might be $omega$, a unit cube root in $mathbb{C}$..
– Henno Brandsma
Dec 2 at 10:29
1
1
Use the same technique as here. Instead of $(1+x)^{40}$ with $x=1,omega,omega^2$, you will be needing $(3+x)^{40}$ with $x=1,omega,omega^2$. Do you see why?
– Jyrki Lahtonen
Dec 2 at 10:34
Use the same technique as here. Instead of $(1+x)^{40}$ with $x=1,omega,omega^2$, you will be needing $(3+x)^{40}$ with $x=1,omega,omega^2$. Do you see why?
– Jyrki Lahtonen
Dec 2 at 10:34
Yes after the solution down there , I now fully understand
– Tariro Manyika
Dec 2 at 21:11
Yes after the solution down there , I now fully understand
– Tariro Manyika
Dec 2 at 21:11
That's great. TariroManyika !
– Jyrki Lahtonen
Dec 5 at 19:47
That's great. TariroManyika !
– Jyrki Lahtonen
Dec 5 at 19:47
add a comment |
1 Answer
1
active
oldest
votes
Consider the polynomial $(a+b+c+d)^{40}$. The coefficient of a term of the form $a^{k_1}b^{k_2}c^{k_3}d^{k_4}$ counts the number of sequences of length 40 composed of ${k_1}$ $a$'s, ${k_2}$ $b$'s, ${k_3}$ $c$'s, ${k_2}$ $d$'s. Therefore we are required to find the sum of coefficients of the terms of $(a+b+c+d)^{40}$ with the exponent of a divisible by the $3$.
To do this, we set $b=c=d=1$ in the polynomial as there is no restriction on the number of $b$'s, $c$'s or $d$'s. Thus our answer is the sum of coefficients of the terms with exponent divisible by $3$ of the polynomial $(a+3)^{40}$.
Let $f(a)=(a+3)^{40}=sum_{i=0}^{40}{l_i}a^{i}$. Therefore we have to get hold of $z=l_0+l_3+l_6+...+l_{39}$. Notice $f(1)= l_0+l_1+l_2+...+l_{40}$, $f(omega)=l_0+l_1omega+l_2omega^{2}+l_3+l_4omega+...+l_{40}omega$. $f(omega^2)=l_0+l_1omega^{2}+l_2omega+l_3+l_4omega^{2}+...+l_{40}omega^{2}$.
Therefore $f(1)+f(omega)+f(omega^{2})=3(l_0+l_3+l_6+...+l_{39})=3z$
Hence, $$z=frac{4^{40}+(3+omega)^{40}+(3+omega^{2})^{40}}{3}
=frac{4^{40}+(3+omega)^{40}+(3+bar omega)^{40}}{3}
=frac{4^{40}+2Re((3+omega)^{40})}{3}$$
Q.E.D.
Thank you so much , which text book can I read that can help me answer such questions in future ?
– Tariro Manyika
Dec 2 at 21:11
Sorry after hence, If w is a complex number, (3+w)^2 not equal to (3+conjugate w)
– Tariro Manyika
Dec 2 at 23:46
A Path to Combinatorics for Undergraduates by Titu Andreescu and Zuming Feng is good for general reference. I would recommend Generatingfunctionology by Herbert Wilf for exposure to a wide spectrum of problems solved using generating functions.
– Anubhab Ghosal
Dec 3 at 3:10
As $omega^{3}=1$, $bar omega = frac{1}{omega} = omega^{2}$.
– Anubhab Ghosal
Dec 3 at 3:14
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%2f3022467%2fshow-that-the-number-of-sequences-of-length-40-are-there-using-the-alphabet-a-b%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
Consider the polynomial $(a+b+c+d)^{40}$. The coefficient of a term of the form $a^{k_1}b^{k_2}c^{k_3}d^{k_4}$ counts the number of sequences of length 40 composed of ${k_1}$ $a$'s, ${k_2}$ $b$'s, ${k_3}$ $c$'s, ${k_2}$ $d$'s. Therefore we are required to find the sum of coefficients of the terms of $(a+b+c+d)^{40}$ with the exponent of a divisible by the $3$.
To do this, we set $b=c=d=1$ in the polynomial as there is no restriction on the number of $b$'s, $c$'s or $d$'s. Thus our answer is the sum of coefficients of the terms with exponent divisible by $3$ of the polynomial $(a+3)^{40}$.
Let $f(a)=(a+3)^{40}=sum_{i=0}^{40}{l_i}a^{i}$. Therefore we have to get hold of $z=l_0+l_3+l_6+...+l_{39}$. Notice $f(1)= l_0+l_1+l_2+...+l_{40}$, $f(omega)=l_0+l_1omega+l_2omega^{2}+l_3+l_4omega+...+l_{40}omega$. $f(omega^2)=l_0+l_1omega^{2}+l_2omega+l_3+l_4omega^{2}+...+l_{40}omega^{2}$.
Therefore $f(1)+f(omega)+f(omega^{2})=3(l_0+l_3+l_6+...+l_{39})=3z$
Hence, $$z=frac{4^{40}+(3+omega)^{40}+(3+omega^{2})^{40}}{3}
=frac{4^{40}+(3+omega)^{40}+(3+bar omega)^{40}}{3}
=frac{4^{40}+2Re((3+omega)^{40})}{3}$$
Q.E.D.
Thank you so much , which text book can I read that can help me answer such questions in future ?
– Tariro Manyika
Dec 2 at 21:11
Sorry after hence, If w is a complex number, (3+w)^2 not equal to (3+conjugate w)
– Tariro Manyika
Dec 2 at 23:46
A Path to Combinatorics for Undergraduates by Titu Andreescu and Zuming Feng is good for general reference. I would recommend Generatingfunctionology by Herbert Wilf for exposure to a wide spectrum of problems solved using generating functions.
– Anubhab Ghosal
Dec 3 at 3:10
As $omega^{3}=1$, $bar omega = frac{1}{omega} = omega^{2}$.
– Anubhab Ghosal
Dec 3 at 3:14
add a comment |
Consider the polynomial $(a+b+c+d)^{40}$. The coefficient of a term of the form $a^{k_1}b^{k_2}c^{k_3}d^{k_4}$ counts the number of sequences of length 40 composed of ${k_1}$ $a$'s, ${k_2}$ $b$'s, ${k_3}$ $c$'s, ${k_2}$ $d$'s. Therefore we are required to find the sum of coefficients of the terms of $(a+b+c+d)^{40}$ with the exponent of a divisible by the $3$.
To do this, we set $b=c=d=1$ in the polynomial as there is no restriction on the number of $b$'s, $c$'s or $d$'s. Thus our answer is the sum of coefficients of the terms with exponent divisible by $3$ of the polynomial $(a+3)^{40}$.
Let $f(a)=(a+3)^{40}=sum_{i=0}^{40}{l_i}a^{i}$. Therefore we have to get hold of $z=l_0+l_3+l_6+...+l_{39}$. Notice $f(1)= l_0+l_1+l_2+...+l_{40}$, $f(omega)=l_0+l_1omega+l_2omega^{2}+l_3+l_4omega+...+l_{40}omega$. $f(omega^2)=l_0+l_1omega^{2}+l_2omega+l_3+l_4omega^{2}+...+l_{40}omega^{2}$.
Therefore $f(1)+f(omega)+f(omega^{2})=3(l_0+l_3+l_6+...+l_{39})=3z$
Hence, $$z=frac{4^{40}+(3+omega)^{40}+(3+omega^{2})^{40}}{3}
=frac{4^{40}+(3+omega)^{40}+(3+bar omega)^{40}}{3}
=frac{4^{40}+2Re((3+omega)^{40})}{3}$$
Q.E.D.
Thank you so much , which text book can I read that can help me answer such questions in future ?
– Tariro Manyika
Dec 2 at 21:11
Sorry after hence, If w is a complex number, (3+w)^2 not equal to (3+conjugate w)
– Tariro Manyika
Dec 2 at 23:46
A Path to Combinatorics for Undergraduates by Titu Andreescu and Zuming Feng is good for general reference. I would recommend Generatingfunctionology by Herbert Wilf for exposure to a wide spectrum of problems solved using generating functions.
– Anubhab Ghosal
Dec 3 at 3:10
As $omega^{3}=1$, $bar omega = frac{1}{omega} = omega^{2}$.
– Anubhab Ghosal
Dec 3 at 3:14
add a comment |
Consider the polynomial $(a+b+c+d)^{40}$. The coefficient of a term of the form $a^{k_1}b^{k_2}c^{k_3}d^{k_4}$ counts the number of sequences of length 40 composed of ${k_1}$ $a$'s, ${k_2}$ $b$'s, ${k_3}$ $c$'s, ${k_2}$ $d$'s. Therefore we are required to find the sum of coefficients of the terms of $(a+b+c+d)^{40}$ with the exponent of a divisible by the $3$.
To do this, we set $b=c=d=1$ in the polynomial as there is no restriction on the number of $b$'s, $c$'s or $d$'s. Thus our answer is the sum of coefficients of the terms with exponent divisible by $3$ of the polynomial $(a+3)^{40}$.
Let $f(a)=(a+3)^{40}=sum_{i=0}^{40}{l_i}a^{i}$. Therefore we have to get hold of $z=l_0+l_3+l_6+...+l_{39}$. Notice $f(1)= l_0+l_1+l_2+...+l_{40}$, $f(omega)=l_0+l_1omega+l_2omega^{2}+l_3+l_4omega+...+l_{40}omega$. $f(omega^2)=l_0+l_1omega^{2}+l_2omega+l_3+l_4omega^{2}+...+l_{40}omega^{2}$.
Therefore $f(1)+f(omega)+f(omega^{2})=3(l_0+l_3+l_6+...+l_{39})=3z$
Hence, $$z=frac{4^{40}+(3+omega)^{40}+(3+omega^{2})^{40}}{3}
=frac{4^{40}+(3+omega)^{40}+(3+bar omega)^{40}}{3}
=frac{4^{40}+2Re((3+omega)^{40})}{3}$$
Q.E.D.
Consider the polynomial $(a+b+c+d)^{40}$. The coefficient of a term of the form $a^{k_1}b^{k_2}c^{k_3}d^{k_4}$ counts the number of sequences of length 40 composed of ${k_1}$ $a$'s, ${k_2}$ $b$'s, ${k_3}$ $c$'s, ${k_2}$ $d$'s. Therefore we are required to find the sum of coefficients of the terms of $(a+b+c+d)^{40}$ with the exponent of a divisible by the $3$.
To do this, we set $b=c=d=1$ in the polynomial as there is no restriction on the number of $b$'s, $c$'s or $d$'s. Thus our answer is the sum of coefficients of the terms with exponent divisible by $3$ of the polynomial $(a+3)^{40}$.
Let $f(a)=(a+3)^{40}=sum_{i=0}^{40}{l_i}a^{i}$. Therefore we have to get hold of $z=l_0+l_3+l_6+...+l_{39}$. Notice $f(1)= l_0+l_1+l_2+...+l_{40}$, $f(omega)=l_0+l_1omega+l_2omega^{2}+l_3+l_4omega+...+l_{40}omega$. $f(omega^2)=l_0+l_1omega^{2}+l_2omega+l_3+l_4omega^{2}+...+l_{40}omega^{2}$.
Therefore $f(1)+f(omega)+f(omega^{2})=3(l_0+l_3+l_6+...+l_{39})=3z$
Hence, $$z=frac{4^{40}+(3+omega)^{40}+(3+omega^{2})^{40}}{3}
=frac{4^{40}+(3+omega)^{40}+(3+bar omega)^{40}}{3}
=frac{4^{40}+2Re((3+omega)^{40})}{3}$$
Q.E.D.
edited Dec 3 at 3:02
answered Dec 2 at 13:47
Anubhab Ghosal
74412
74412
Thank you so much , which text book can I read that can help me answer such questions in future ?
– Tariro Manyika
Dec 2 at 21:11
Sorry after hence, If w is a complex number, (3+w)^2 not equal to (3+conjugate w)
– Tariro Manyika
Dec 2 at 23:46
A Path to Combinatorics for Undergraduates by Titu Andreescu and Zuming Feng is good for general reference. I would recommend Generatingfunctionology by Herbert Wilf for exposure to a wide spectrum of problems solved using generating functions.
– Anubhab Ghosal
Dec 3 at 3:10
As $omega^{3}=1$, $bar omega = frac{1}{omega} = omega^{2}$.
– Anubhab Ghosal
Dec 3 at 3:14
add a comment |
Thank you so much , which text book can I read that can help me answer such questions in future ?
– Tariro Manyika
Dec 2 at 21:11
Sorry after hence, If w is a complex number, (3+w)^2 not equal to (3+conjugate w)
– Tariro Manyika
Dec 2 at 23:46
A Path to Combinatorics for Undergraduates by Titu Andreescu and Zuming Feng is good for general reference. I would recommend Generatingfunctionology by Herbert Wilf for exposure to a wide spectrum of problems solved using generating functions.
– Anubhab Ghosal
Dec 3 at 3:10
As $omega^{3}=1$, $bar omega = frac{1}{omega} = omega^{2}$.
– Anubhab Ghosal
Dec 3 at 3:14
Thank you so much , which text book can I read that can help me answer such questions in future ?
– Tariro Manyika
Dec 2 at 21:11
Thank you so much , which text book can I read that can help me answer such questions in future ?
– Tariro Manyika
Dec 2 at 21:11
Sorry after hence, If w is a complex number, (3+w)^2 not equal to (3+conjugate w)
– Tariro Manyika
Dec 2 at 23:46
Sorry after hence, If w is a complex number, (3+w)^2 not equal to (3+conjugate w)
– Tariro Manyika
Dec 2 at 23:46
A Path to Combinatorics for Undergraduates by Titu Andreescu and Zuming Feng is good for general reference. I would recommend Generatingfunctionology by Herbert Wilf for exposure to a wide spectrum of problems solved using generating functions.
– Anubhab Ghosal
Dec 3 at 3:10
A Path to Combinatorics for Undergraduates by Titu Andreescu and Zuming Feng is good for general reference. I would recommend Generatingfunctionology by Herbert Wilf for exposure to a wide spectrum of problems solved using generating functions.
– Anubhab Ghosal
Dec 3 at 3:10
As $omega^{3}=1$, $bar omega = frac{1}{omega} = omega^{2}$.
– Anubhab Ghosal
Dec 3 at 3:14
As $omega^{3}=1$, $bar omega = frac{1}{omega} = omega^{2}$.
– Anubhab Ghosal
Dec 3 at 3:14
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.
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%2f3022467%2fshow-that-the-number-of-sequences-of-length-40-are-there-using-the-alphabet-a-b%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
The $w$ might be $omega$, a unit cube root in $mathbb{C}$..
– Henno Brandsma
Dec 2 at 10:29
1
Use the same technique as here. Instead of $(1+x)^{40}$ with $x=1,omega,omega^2$, you will be needing $(3+x)^{40}$ with $x=1,omega,omega^2$. Do you see why?
– Jyrki Lahtonen
Dec 2 at 10:34
Yes after the solution down there , I now fully understand
– Tariro Manyika
Dec 2 at 21:11
That's great. TariroManyika !
– Jyrki Lahtonen
Dec 5 at 19:47