set of compositions where each part is restricted based on its position I am trying to find a generating function for the set of compositions (say $S$) of any length with a unique restriction on it. ($S$ should also include the empty composition $\epsilon$).
The restriction is for any $c = (c_1, c_2, \ldots, c_k)$ in the set, each part $c_i$ must be congruent to $i \text{ mod } 2$.
edit:
If trying to find a generating function for the unrestricted set of compositions, via the string lemma, we get
$$
g(x) = \frac{1}{1 - \sum_{n \geq 1} x^n} = \frac{1-x}{1-2x}.
$$
using the generating function for the set of all positive integers.
 A: Hint
As you mentioned in your post, an unrestricted composition can be described as an ordered sequence of "objects," where there is one object of each positive integer weight. Each object therefore has generating function $(x+x^2+x^3+\dots)$, so sequences of them have g.f.
$$
\frac1{1-(x+x^2+\dots)}=\frac{1-x}{1-2x}
$$
We can do something almost as easy with these odd-even compositions. To make things easier, let us first find the g.f. for odd-even composition $(c_1,\dots,c_{k})$ where $k$ is even. The composition is a sequence of $k/2$ pairs of integers $(d,e)$, where $d$ is odd and $e$ is even. The g.f. for $d$ is $(x+x^3+x^5+\dots)$ (one for each odd natural number), and the g.f. for $e$ is $(x^2+x^4+x^6+\dots)$ (similar). What is the g.f. for the ordered pair $(d,e)$? That is, for picking $d$ and $e$ together?
Once you have the g.f. $F(x)$ for pairs of (odd, even) integers, the g.f. for compositions of even length is $\frac{1}{1-F(x)}$. You then need to do something similar to find the g.f. for sequences of odd length, and than add that to $\frac1{1-F(x)}$. The odd g.f. is just a little trickier; the idea is that an odd composition is a sequence of (odd, even) pairs, followed by an odd integer.
