Find coefficient of Generating function

Question

Here is my problem and what i have thought so far: How many ways i can arrange 9 letters when i have 3 pairs-> AA|BB|CC|DEF so without using generating functions i get $\frac{n!}{n_1n_2n_3n_4n_5n_6n_7n_8n_9}$ and i get$\frac{9!}{8}$ so how can i solve this using generating functions?

My first thought was that i use all 9 so my coefficient need to be $coefficient*x^9$, but i need to use egf or and ordinary and why? using an ordinary function i get $(1+x+x^2)^3*(1+x)^3$ , somewhere i heard about identities of genfunctions can someone enlighten me?

Answer 1

The exponential generating function for the number of strings of length $r$ taken from the given symbols is $$f(x) = \left( 1 + x + \frac{1}{2!} x^2 \right)^3 (1+x)^3$$ It's easy to see that the coefficient of $x^9$ in $f(x)$ is $1/2^3$, so the coefficient of $(1/9!) x^9$, which is the number of strings of length $9$, is $$\frac{9!}{2^3}$$

Answer 2

To make the answer more complete, I just indicate a derivation of the exponential generating function $f(x)$ that awkward used.

Let $S$ be the alphabet of symbols and we have as restriction for the number of $s$ symbols used, $n_s$: $0 \le n_s \le k_s, s\in S$. Then:

$f(x)=\sum_{k=0}^{\infty} C_k \frac{x^k}{k!} =\prod_{s\in S} \sum_{n_s=0}^{k_s}\frac{x^{n_s}}{n_s!} [1]$

One can check that the exponential function agrees with the one used by awkward, with $S=\{A,B,C,D,E,F\}$ and $k_A=k_B=k_B=2$ and $k_D=k_E=k_F=1$.

The expression is easily verified thinking that the number of configurations of length k and fixed occupations $\{ n_s \}$ is $\frac{k!}{n_1!...n_s!}$. Summing over all possible choices:

$C_k=\sum_{\{n_s\}|n_1+...+n_s=k, 0\le n_s \le k_s} \frac{k!}{n_1!...n_s!},$

which is exactly what the expansion of the right member of [1] provides.