# 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=$$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

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

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.
• As $\omega^{3}=1$, $\bar \omega = \frac{1}{\omega} = \omega^{2}$. – Anubhab Ghosal Dec 3 '18 at 3:14