Let $C_n$ be the set of all compositions of n such that each letter is one of ${1,2,\ldots,d-1}$.
A. Calculate the generating function of the number of compositions in $C_n$.
B. For each composition $\pi \in C_n$ define $f(\pi)$ as the number of letters that equal $1$. Find yhe generating function of $\sum_{n\geq 0} \sum_{\pi \in C_n} q^{f(\pi)} x^n$.
C.Find the expectation of the number of letters that equal 1 (1's appearances) in these compositions, and analyze it asymptotically.
*Generally: Composition of $n$: a sequence of numbers in $N$ such that their sum equals $n$. For example: $C_0={\epsilon}$ , $C_1={1}$, $C_2={11,2}$ , $C_3={111,12,21,3}$.
In this question, a composition of a number $n$ , consists of numbers from the set {$1,2,\ldots, d-1$} where $d$ is a given number.
This is what I did:
A. Every compisition of n = empty compisition $\cup$ (1 / every compisition) $\cup$ (2 / every compisition) $\cup$....$\cup$((d-1) / every compisition). so if x counts the length of a number, then the generating function $C(x)$ for the problem satisfy:
$C(x)=1+xC(x)+x^2C(x)+\cdots+x^{d-1}C(x)$
(1 for the empty compisition)
$C(x)=1+C(x)(x+x^2+\cdots+x^{d-1})$
Therefore, $C(x)=\frac{1-x}{1-2x+x^d}=\frac{1}{1-x-x^2-...-x^{d-1}}$
B.Let $q$ counts the appearances of 1 and $x$ as we mentioned counts the length of a number. Then:
$C(x)=1+qxC(x,q)+x^2C(x,q)+\cdots+x^{d-1}C(x,q)$
$C(x,q)=1+C(x,q)(qx+x^2+\cdots+x^{d-1})$
So, $C(x,q)=\frac{1-x}{x^d+(q-1)x^2-(q+1)x+1}$
C. We have to calculate $[x^n]C(x,1)=[x^n] C(x)$ and $[x^n] ([(d/dq) C(x,q)]_{q=1})=\frac{x}{(1-x-x^2-...-x^{d-1})^2}=xC(x)^2$ so the expectation will be the proportion of them.
But I could not see how the coefficients can be calculated! I did not succeed to connect it to Fibonacci series which I know (the case of d=2).
I would be thankful for any help to show part C.
Thanks in advance
The analysis of this sort of generating function's asymptotics is an exercise in partial fraction decomposition. Suppose we're trying to find the asymptotics of $P_n$ whose generating function $\sum_i P_ix^i$ is $\dfrac1{P(x)}$. If we can factor the polynomial $P(x)$ as $(x-r_1)(x-r_2)\cdots(x-r_n)$ (and all the roots are distinct), then we can write $\dfrac1{P(x)}$ as $\sum_i\dfrac{m_i}{x-r_i}$ for some constants $m_i$ (more on this later). We can then go the other direction, using the geometric series to write $P_n$ as $\sum_i \frac{m_i}{r_i}(r_i^{-1})^n$. If $r_1$ is the smallest root in absolute value, then this implies that $P_n=\frac{m_1}{r_1}(r_1^{-1})^n(1+O(\epsilon^n))$ for some $\epsilon\lt 1$. (There are very minor complications when the smallest roots are complex conjugates but that's not relevant here.)
In this case, we know that the polynomial $P(x)=1-(x+x^2+\ldots+x^{d-1})$ is positive at $x=0$ and negative at $x=1$ (as long as $d\gt 2$; if $d=2$ the analysis is trivial), so it has a root in $(0,1)$. What's more, since $P'(x)$ is negative on this interval, it has a single, simple root $\rho_{d-1}$ in the interval. (And in fact, all roots of $P()$ are simple since $\gcd(P, P')=1$.) Using Rouché's Theorem applied to $(1-x)P(x) = 1-2x+x^d$, we can show that there are no other roots of $P(x)$ in the disc $x\lt 1$, so this root dominates the asymptotics; we have that $C_n=C(\xi_{d-1})^n$ for some constant $C$, where $\xi_{d-1}=\rho_{d-1}^{-1}$. Note that we can say this even without being able to write an explicit formula for $\xi_{d-1}$ (except in the first few cases, such as the Fibonacci numbers).
The next piece of the puzzle is to compute $C$; fortunately, there's a standard tool for this, the residue method — I'll leave the details of this to you.
Also, one small additional note: if you're curious, you can also examine the asymptotics of $\xi_d$ itself — specifically, the asymptotics as $d$ goes to infinity. It should be straightforward to find the limiting value (hint: what $x$ has $x+x^2+x^3+\ldots=1$?) but the rate of approach is a really nice problem.
A similar analysis can be done in principle for $[x^n]\left(xC(x)^2\right)$ $=[x^{n-1}]\left(C(x)^2\right)$, but it's substantially complicated by the fact that the root is no longer simple. Fortunately, there's another way of finding the asymptotics: you can use the equation for the coefficients of $C(x)^2$ in terms of the $C_n$ and then applying the asymptotic analysis of the $C_n$ to those terms. (You should find that each of the summands in the equation for the coefficients of $C(x)^2$ is comparable in size — see if you can figure out why.)