Help with finding the generating function of this language? I've simplified this a bit so that I can just get help with the basic steps.
Say we have a language of all words over $\{a,b,c,d\}$ where the only letters allowed to commute are $ab$. I need help understanding how to define equivalence classes of words in the language. Then, take a representative of each equivalence class and find a generating function for the sequence of these equivalence class representatives.
To make sure I understand the language, these would be the possible words, yes? Or am I missing some? I think maybe the restriction that only $ab$ commute is confusing me.
$$a, b,c,d$$
$$ab, ac,ad,bc, bd, cd, ba$$
$$abc,abd,acd,bcd,bac, bad$$
$$abcd, bacd$$
What would each equivalence class be? Words of the same length? Then how do I select a representative from each? Can I just pick any one? So maybe these would be them?
$$a,ab,abc,abcd$$
But then these would be the same representatives even if we said only $ab$ can commute so that doesn't seem right.
And then finally, once I find these, how do I find a generating function?
 A: Note: Main theme of this answer is to find a generating function for the language. We develop it by foot. Then we indicate a Rolls Royce variant.
If an alphabet $\mathcal{A}=\{a,b,c,d\}$ is given there are $4^n$ different words of length $n$, since for each of the $n$ positions within a word one out of four letters from $\mathcal{A}$ can be chosen.

The language $\mathcal{L}$
Let's assume that $ab$ commute, so that $ab$ and $ba$ are not distinguishable. This way we can choose either $ab$ or $ba$ as representative for the corresponding equivalence class. We select in the following lexicographically ordered $ab$ as representative for the equivalence class
  \begin{align*}
[ab]=\{ab,ba\}
\end{align*}
  The language $\mathcal{L}$ so defined consists of all words built from the alphabet $\mathcal{A}$ which does not contain the substring $ba$, since we always choose the representative $ab$ instead.

Let's look for all words in $\mathcal{L}$ of length $\leq 4$. We identify all words which contain a substring $ba$ since these are the words which are in a corresponding equivalence class with $ab$ and which are to exclude. Words of length $1$ and $2$ are simple.

Words in $\mathcal{L}$ with length $\leq 4$
  
  
*
  
*Words of length $=1$: There are $4^1=4$ words of length $1$ which can be built from $\mathcal{A}$,  namely
  \begin{align*}
a,b,c,d
\end{align*}
  and of course none of them contains a substring $ba$.  So all of them are elements of the language $\mathcal{L}$
  
  
  From now on we group words according to the number of occurrences of the substring $ba$. Words of length $2$ and $3$ have either zero or one occurrence of $ba$, words of length $4$ and $5$ have zero, one or two occurrences of $ba$.
  
  
*
  
*Words of Length $=2$: Words of length $2$ have the shape
  \begin{align*}
uv\qquad \color{blue}{ba} \qquad\qquad u,v \in\mathcal{A}\\
\end{align*}
  We have two groups. The number of different words in the first group $uv$, which are all words of length $2$ is $4\cdot4=16$. Since we want to count valid words only, we have to subtract the words from the second group, which is only $1$ in this case. We conclude
  
  
  There are
  \begin{align*}
4^2-1=15
\end{align*}
  words in $\mathcal{L}$ with length $2$.
  
  
*
  
*Length $=3$: Words of length $3$ have the shape
  \begin{array}{ccc}
uvw\qquad &\color{blue}{ba}u\qquad&\qquad\qquad u,v \in\mathcal{A}\\
\qquad &u\color{blue}{ba}\qquad &\\
\end{array}
  We have two groups. The number of different words in the first group $uvw$, which are all words of length $3$ is $4\cdot3=64$. Since we want to count valid words only, we have to subtract all words from the second group, which is     $\binom{2}{1}4=8$ in this case. There     are   $\binom{2}{1}$ possibilities to position $ba$ and $4$ possibilities     for    $u$. We conclude
  
  
  There are
  \begin{align*}
4^3-\binom{2}{1}4=56
\end{align*}
  words in $\mathcal{L}$ with length $3$.
  
  
*
  
*Length $=4$: Words of length $4$ have the shape
  \begin{array}{cccc}
uvwx\qquad &\color{blue}{ba}uv\qquad &\color{blue}{ba}\color{blue}{ba}\\
\qquad &u\color{blue}{ba}v\qquad&&\qquad u,v \in\mathcal{A}\\
\qquad &uv\color{blue}{ba}\qquad&&\\
\end{array}
  We have three groups. The number of different words in the first group $uvwx$, which are all words of length $4$ is $4\cdot4=256$. Since we want to count valid words only, we have to subtract all words from the second group, which is     $\binom{3}{1}4^2=8$ in this case. There     are   $\binom{3}{1}$ possibilities to position $ba$ and $4^2$ possibilities     for    $uv$. Since   we   count  occurrences of $ba$ twice in a word more than once, we have to add all words with $ba$ twice as substring. We conclude
  
  
  There are
  \begin{align*}
4^4-\binom{3}{1}4^2+\binom{2}{2}4^0=209
\end{align*}
  words in $\mathcal{L}$ with length $4$.

We obsere a nice scheme. According to the Inclusion-exclusion principle 
we subtract and add words containing an increasing number of substrings $ba$. In case words have length $n$ and $k$ occurrences of $ba$, there are $\binom{n}{k}$ possibilities to choose the positions of $ba$ and $n-2k$ positions left for the other letters which give a total of
\begin{align*}
\binom{n}{k}4^{n-2k}
\end{align*}
different words for $n\geq 0$ and $0\leq k\leq \left\lfloor\frac{n}{2}\right\rfloor$.

We conclude the following is valid. There are
  \begin{align*}
\sum_{k=0}^{ \left\lfloor\frac{n}{2}\right\rfloor}\binom{n-k}{k}(-1)^k4^{n-2k}\qquad\qquad n\geq 0
\end{align*}
  different words of length $n$ in $\mathcal{L}$.

We allow $n=0$   which  means  that   the empty word $\varepsilon$ of length zero  is also element in $\mathcal{L}$.

Generating function $L(x)$
A generating function is a formal power series
\begin{align*}
L(x)=\sum_{n=0}^{\infty}a_nx^n
\end{align*}
  with the coefficient  $a_n$ of $x^n$ denoting the number of words of length $n$ in $\mathcal{L}$.
Since we know the number of words of $\mathcal{L}$ we can write the generating function as
  \begin{align*}
L(x)&=\sum_{n=0}^{\infty}\sum_{k=0}^{ \left\lfloor\frac{n}{2}\right\rfloor}\binom{n-k}{k}(-1)^k4^{n-2k}x^n\\
&=1+4x+15x^2+56x^3+209x^4+780x^5+\cdots
\end{align*}

We can do even better. We derive an expression of $L(x)$ as rational function in $x$. In order to do so we use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a generating series and transform the coefficients of $L(x)$ appropriately.

We obtain
  \begin{align*}
\sum_{k=0}^n&\binom{n-k}{k}(-1)^k4^{n-2k}\tag{1}\\
&=\sum_{k=0}^n\binom{k}{n-k}(-1)^{n-k}4^{2k-n}\tag{2}\\
&=\sum_{k=0}^\infty\binom{k}{n-k}\left(-\frac{1}{4}\right)^{n-k}4^k\tag{3}\\
&=\sum_{k=0}^\infty4^k[x^{n-k}]\sum_{l=0}^k\binom{k}{l}\left(-\frac{1}{4}\right)^{l}x^l\tag{4}\\
&=\sum_{k=0}^\infty[x^{n}](4x)^k\left(1-\frac{1}{4}x\right)^k\tag{5}\\
&=[x^n]\sum_{k=0}^\infty\left(4x-x^2\right)^k\tag{6}\\
&=[x^n]\frac{1}{1-4x-x^2}\\
\end{align*}

Comment: 


*

*In (1) we put for convenience only the upper limit of the index $k$ to $n$ without changing anything, since we use the convention $\binom{n}{k}=0$ if $0<n<k$.

*In (2) we exchange $k$ with $n-k$.

*In (3) we do a small rearrangement and put the upper limit of the index $k$ to $\infty$ for convenience only. This changes nothing with the same reasoning as in (1).

*In (4) we write $\binom{k}{n-k}\left(-\frac{1}{4}\right)^{n-k}$ as a Cauchy product $[x^{n-k}]\sum_{l=0}^k\binom{k}{l}\left(-\frac{1}{4}\right)^{l}x^l$. This is the core of the derivation since it allows a drastic simplification in the next step.

*In (5) we  can write the polynomial in $x$ as $k$-th power of a binom.

*In (6) we obtain a geometric series representation which gives us in the next line a representation as rational function in $x$.

We conclude
\begin{align*}
L(x)&=\frac{1}{1-4x+x^2}\tag{7}\\
&=1+4x+15x^2+56x^3+209x^4+780x^5+\cdots
\end{align*}

Note:  In fact, there is a powerful method to solve problems of this kind, called the Goulden-Jackson Cluster Method. In this context we regard $ba$ as bad word and derive immediately (see formula of $f(s)$ on page $9$)  the rational expression (7) of $L(x)$.
A: It looks like you're working with the set of ALL strings whose characters are $a,b,c,d$. You are defining an equivalence class by saying that $uabv \equiv ubav$ (where $u$ and $v$ are arbitrary strings), and then taking the transitive closure to make it an equivalence relation.
Hence, $ bacab \equiv bacba \equiv abcba \equiv abcab \equiv bacab$, so the equivalence class for $bacab$ would be $\{bacab ,bacba ,abcba ,abcab\}$. As for the representative, I would choose $abcab$, where there are no substrings of the form $ba$.
I'm not sure what you mean by a "generating function" in this context; generating functions usually are for sequences of real numbers.
