Show that the number of sequences of length 40 are there using the alphabet {a,b,c,d}












1














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










share|cite|improve this question


















  • 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














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










share|cite|improve this question


















  • 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








1


0





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










share|cite|improve this question













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






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










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














  • 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










1 Answer
1






active

oldest

votes


















2














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.






share|cite|improve this answer























  • 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













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
});


}
});














draft saved

draft discarded


















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









2














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.






share|cite|improve this answer























  • 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


















2














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.






share|cite|improve this answer























  • 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
















2












2








2






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.






share|cite|improve this answer














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.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








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




















  • 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




















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Berounka

Sphinx de Gizeh

Different font size/position of beamer's navigation symbols template's content depending on regular/plain...