2
$\begingroup$

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=$40C3\times3^{(40-3)}$

sequence with 6 a's=$40C6\times 3^{(40-6)}$

sequence with 9 a's=$40C9\times3^{(40-9)}$

.

.

sequence with 36 a's=$40C36\times3^{(40-36)}$ sequence with 39 a's=$40C39\times3^{(40-39)}$

I'm stuck as to where the Re and $w$ come into play

$\endgroup$
  • 1
    $\begingroup$ The $w$ might be $\omega$, a unit cube root in $\mathbb{C}$.. $\endgroup$ – Henno Brandsma Dec 2 '18 at 10:29
  • 1
    $\begingroup$ 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? $\endgroup$ – Jyrki Lahtonen Dec 2 '18 at 10:34
  • $\begingroup$ Yes after the solution down there , I now fully understand $\endgroup$ – Tariro Manyika Dec 2 '18 at 21:11
  • $\begingroup$ That's great. TariroManyika ! $\endgroup$ – Jyrki Lahtonen Dec 5 '18 at 19:47
2
$\begingroup$

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_1\omega+l_2\omega^{2}+l_3+l_4\omega+...+l_{40}\omega$. $f(\omega^2)=l_0+l_1\omega^{2}+l_2\omega+l_3+l_4\omega^{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.

$\endgroup$
  • $\begingroup$ Thank you so much , which text book can I read that can help me answer such questions in future ? $\endgroup$ – Tariro Manyika Dec 2 '18 at 21:11
  • $\begingroup$ Sorry after hence, If w is a complex number, (3+w)^2 not equal to (3+conjugate w) $\endgroup$ – Tariro Manyika Dec 2 '18 at 23:46
  • $\begingroup$ 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. $\endgroup$ – Anubhab Ghosal Dec 3 '18 at 3:10
  • $\begingroup$ As $\omega^{3}=1$, $\bar \omega = \frac{1}{\omega} = \omega^{2}$. $\endgroup$ – Anubhab Ghosal Dec 3 '18 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.