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

1 Answer 1

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