2. (BUL 3) Let $n$ be a positive integer. Find the number of odd coefficients of the polynomial
$$
u_{n}(x)=\left(x^{2}+x+1\right)^{n} .
$$
2. For polynomials $f(x), g(x)$ with integer coefficients, we use the notation $f(x) \sim g(x)$ if all the coefficients of $f-g$ are even. Let $n=2^{s}$. It is immediately shown by induction that $\left(x^{2}+x+1\right)^{2^{2}} \sim x^{2^{2+1}}+x^{2^{4}}+1$, and the required number for $n=2^{5}$ is 3 .

Let $n=2^{s}-1$. If $s$ is odd, then $n \equiv 1(\bmod 3)$, while for $s$ even, $n \equiv 0$ (mod 3). Consider the polynomial
$$
R_{s}(x)=\left\{\begin{array}{ll}
(x+1)\left(x^{2 n-1}+x^{2 n-4}+\cdots+x^{n+3}\right)+x^{n+1} & \\
+x^{n}+x^{n-1}+(x+1)\left(x^{n-4}+x^{n-7}+\cdots+1\right), & 2 \nmid s ; \\
(x+1)\left(x^{2 n-1}+x^{2 n-4}+\cdots+x^{n+2}\right)+x^{n} & \\
+(x+1)\left(x^{n-3}+x^{n-6}+\cdots+1\right), & 2 \mid s .
\end{array}\right.
$$

It is easily checked that $\left(x^{2}+x+1\right) R_{s}(x) \sim x^{2^{t+1}}+x^{2^{4}}+1 \sim\left(x^{2}+x+1\right)^{2^{4}}$, so that $R_{s}(x) \sim\left(x^{2}+x+1\right)^{2}-1$. In this case, the number of odd coefficients is $\left(2^{s+2}-(-1)^{s}\right) / 3$.
Now we pass to the general case. Let the number $n$ be represented in the binary system as
$$
n=\underbrace{11 \ldots 1}_{a_{k}} \underbrace{00 \ldots 0}_{b_{k}} \underbrace{11 \ldots 1}_{a_{k-1}} \underbrace{00 \ldots 0}_{b_{k-1}} \cdots \underbrace{11 \ldots 1}_{a_{1}} \underbrace{00 \ldots 0}_{b_{1}},
$$
$b_{i}>0(i>1), b_{1} \geq 0$, and $a_{i}>0$. Then $n=\sum_{i=1}^{k} 2^{x_{i}}\left(2^{a_{i}}-1\right)$, where $s_{i}=b_{1}+a_{1}+b_{2}+a_{2}+\cdots+b_{i}$, and hence
$$
u_{n}(x)=\left(x^{2}+x+1\right)^{n}=\prod_{i=1}^{k}\left(x^{2}+x+1\right)^{2^{2^{4}}\left(2^{a_{i}}-1\right)} \sim \prod_{i=1}^{k} R_{\mathrm{n}_{4}}\left(x^{2^{\alpha^{4}}}\right) .
$$

Let $R_{u_{i}}\left(x^{2^{\alpha_{1}}}\right) \sim x^{r_{i, 1}}+\cdots+x^{r_{2,1}}$; clearly $r_{i, j}$ is divisible by $2^{x_{i}}$ and $r_{i, j} \leq 2^{x_{i}+1}\left(2^{n_{i}}-1\right)<2^{x_{i+1}}$, so that for any $j, r_{i, j}$ can have nonzero binary digits only in some position $t, s_{i} \leq t \leq s_{i+1}-1$. Therefore, in
$$
\prod_{i=1}^{k} R_{a_{1}}\left(x^{2^{\alpha_{c}}}\right) \sim \prod_{i=1}^{k}\left(x^{r_{i, 1}}+\cdots+x^{r_{i, d_{i}}}\right)=\sum_{i=1}^{k} \sum_{p_{i}=1}^{d_{1}} x^{r_{1, r_{1}}+r_{2, r_{2}}+\cdots+r_{k}, r_{k}}
$$
all the exponents $r_{1, p_{1}}+r_{2 p_{2}}+\cdots+r_{k, p_{k}}$ are different, so that the number of odd coefficients in $u_{n}(x)$ is
$$
\prod_{i=1}^{k} d_{i}=\prod_{i=1}^{k} \frac{2^{\mathrm{a}_{i}+2}-(-1)^{\mathrm{a}_{i}}}{3} .
$$