I am new to generating functions and I am trying to solve the exercise that says to determine the number of strings of length $n$ formed from the alphabet $\{1, 2, 3, 4, 5, 6, 7\}$ with the constraint that there is never exactly 3 of the same letter. The problem says not to actually solve for the total number of strings as a function of $n$ but just to write down the egf. I was wondering if someone can help me as I am quite clueless on how to get started. I have seen lots of examples in the book for ogf, but egf seems like an entirely different thing to me.
I think I need to make a recurrence relation for $a_n$ with previous terms but I cannot seem to get it
Let $f(x) = e^x - \frac{x^3}{3!} = 1 + x + \frac{x^2}{2!} + \frac{x^4}{4!} + \frac{x^5}{5!} + \cdots$.
$n!$ times the coefficient of $x^n$ in $f$ gives you the number of ways you can construct a string of length $n$ from the alphabet $\{1\}$ such that there is never exactly 3 of the same letter.
Consider the coefficient of $x^4$ in $(f(x))^2$. Collecting terms, you have $1 \cdot \frac{x^4}{4!} + \frac{x^2}{2!} \frac{x^2}{2!} + \frac{x^4}{4!} \cdot 1$. If you multiply through by $4!$, you obtain $(1 + \frac{4!}{2! 2!} + 1) x^4$. This is the number of strings of length $4$ you can construct from the alphabet $\{1, 2\}$ such that no letter appears exactly 3 times. (The three terms in that sum $1+\frac{4!}{2!2!} + 1$ are the casework for considering a) four 1s, b) two 1s and two 2s, and c) four 2s.)
Can you take it from here?