generating function, compositions odd, congruence modulo

Question

Find the generating function for the number of compositions of $n$ with an odd number of parts, each of which is congruent to $1 \bmod 3$.

We have $k$ parts where the total of the $k$ parts must be odd, and each $k$ is congruent to $1 \bmod 3$. Denote $N_{1 \bmod 3}=\{3 m+1 \mid m \in \mathbb{Z}\}$ and $S=N_{1 \bmod 3}^k$. Let $w\left(c_1, \ldots, c_k\right)=c_1+\cdots+c_k$. Then, a composition of $n$ with $k$ parts is an element of $S$ with weight $n$, which must be odd. Let $w\left(c_i\right)=c_i$ for $c_i \in N_{\geq i}$, for all $i$. Then, the Product Lemma can be applied to obtain $$ \Phi_S(x)=\Phi_{N_{1 \bmod 3}^k}(x)=\left(\Phi_{N_{1 \bmod 3}}(x)\right)^k . $$

$$ [x^n] \Phi_S(x) =\left[x^n\right] \Phi_{N_{1 \bmod 3}^k}(x) $$ $$=\left[x^n\right]\left(\Phi_{N_{1 \bmod 3}}(x)\right)^k, \quad \text { by the Product Lemma } $$

$$ =\left[x^n\right]\left(x+x^4+x^7+\ldots\right)^k $$

$$=\left[x^n\right]\left(x\left(1+x^3+x^6+\ldots\right)\right)^k $$ $$=\left[x^{n}\right]\left(\frac{x}{1-x^3}\right)^k \quad \text { using the Geometric Series } x \sum_{i \geq 0} x^{3 i}=\frac{x}{1-x^3}$$ $$=\left[x^{n}\right] x^k\left(1-x^3\right)^{-k} $$ $$= [x^{n-k}] \sum_{i\geq 0} \binom{k+i-1}{i} x^{2i}$$ I don't know how to continue and I don't even know if I'm doing it correctly.

Answer 1

We are looking for the number of compositions of odd parts, each part with generating function \begin{align*} x+x^4+x^7+x^{10}+\cdots=x\left(1+x^3+x^6+\cdots\right)=\frac{x}{1-x^3}\tag{1} \end{align*}

A generating function where the coefficient of $x^n$ gives the number of compositions of odd parts each of type (1) is \begin{align*} &\frac{x}{1-x^3}+\left(\frac{x}{1-x^3}\right)^3+\left(\frac{x}{1-x^3}\right)^5+\cdots\\ &\qquad=\sum_{k=0}^{\infty}\left(\frac{x}{1-x^3}\right)^{2k+1}\\ &\qquad=\frac{x}{1-x^3}\,\frac{1}{1-\left(\frac{x}{1-x^3}\right)^2}\\ &\qquad\,\,\color{blue}{=\frac{x\left(1-x^3\right)}{1-x^2-2x^3+x^6}}\tag{2}\\ &\qquad=x+x^3+x^4+x^5+3x^6+2x^7+5x^8+7x^9+\cdots\tag{3} \end{align*} The last line was calculated with some help of Wolfram Alpha.

We write as small plausibility check the valid compositions for the given coefficients in (3). \begin{align*} x^1:& 1\\ x^3:& 1+1+1\\ x^4:& 4\\ x^5:& 1+1+1+1+1\\ 3x^6:&1+1+4,\\ &1+4+1,\\ &4+1+1\\ 2x^7:&1+1+1+1+1+1+1,\\ &7\\ 5x^8:&1+1+1+1+4,\\ &1+1+1+4+1,\\ &1+1+4+1+1,\\ &1+4+1+1+1,\\ &4+1+1+1+1\\ 7x^9:&1+1+1+1+1+1+1+1+1,\\ &1+1+7,\\ &1+7+1,\\ &7+1+1,\\ &1+4+4,\\ &4+1+4,\\ &4+4+1 \end{align*}