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?


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}$$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.