# Generating Function and Mean

The problem I'am trying to solve is as follows :

We are given a Recurrence Relation, S(n,k) = (k+1)\cdot S(n-1, k) + 2 \cdot S(n-1, k-1) + (n-k-1)\cdot S(n-1,k-2) \\ \begin{aligned} for \ n \gt 2 \ , k \le n-2\end{aligned} \\S(i,k) = \begin{cases}0\ \ for\ \ k \ne 0\\2\ \ for \ \ k = 0 \end{cases} \\S(1,0) = 1 Some values for $S(n,k)$ are : $$S(4,0) = 2\ ,S(5,2) = 58\ ,S(3,2) = 0\ ,S(3,1) = 4\ ,S(5,1) = 28$$

I have a Generating Function $$G_n(z) = \sum_{k=0}^{n-2} \frac{S(n,k)}{n!}\cdot z^k$$

The Expected Value (Mean Value) can be found by $G'_n(1)$. This comes out to be $$G'_n(1) = \frac{2\cdot n}{3}$$ (I am yet to figure out how to come up with the right hand side of the above equation)

Now I am trying to calculate $$X = \sum_{k=0}^{n-2}\frac{ k^2\cdot S(n,k)}{n!}\\for\ n \ge4$$ I think this can be computed by adding the following 2 terms : $$G'_n(1) + G''_n(1)$$

But I dont know how to compute the Generating Function $G_n(z)$ and hence trying to avoid it. Is it possible to compute it without solving for $G_n(z)$ ? If yes then how should I proceed ?

• I think that, by hypothesis, you assume that $\displaystyle \sum_{i=0}^n a_i = 1$ and $a_i \in [0, 1] ~\forall i$. Then $\{a_i\}$ is a probability mass function. But $\{a_i^2\}$ may not be a probability mass function! – the_candyman Feb 19 '14 at 10:32
• @the_candyman : yes it seems I have understood the question wrong – Kyuubi Feb 19 '14 at 11:49
• try to improve your question, and then some one may help you :D – the_candyman Feb 19 '14 at 12:00
• I think you want the mean value of the square of the random variable that takes $0$ with probability $a_0$ and $1$ with probability $a_1$, etc. Is this correct? – ShreevatsaR Feb 19 '14 at 12:18
• @the_candyman: Edited the question. Although ShreevastsaR caught what I was looking for before I could finish my edit. – Kyuubi Feb 19 '14 at 15:06

I presume that in $$G(z) = a_0 + a_1 z + a_2 z^2 + \dots,$$ $a_k$ represents the probability that a certain discrete random variable (call it $X$) takes the value $k$, for each $k$.

For the mean $E[X]$ defined as $E[X] = a_0(0) + a_1(1) + a_2(2) + a_3(3) + \dots$, we can differentiate to get $$G'(z) = a_1 + 2a_2z + 3a_3z^2 + 4a_4z^3 + \dots,$$ whose value at $z = 1$ is exactly the mean we want.

For the mean $E[X^2]$ defined as $E[X^2] = a_0(0^2) + a_1(1^2) + a_2(2^2) + a_3(3^2) + \dots$ (which is not what you wrote, but what I presume you actually want), you can multiply the above $G'(z)$ by $z$, and differentiate again: $$zG'(z) = a_1z + 2a_2z^2 + 3a_3z^3 + 4a_4z^4\dots,$$ so $$(zG'(z))' = a_1 + 2^2 a_2z + 3^2 a_3z^2 + 4^2a_4z^3 + \dots.$$

The left-hand side is $G'(z) + zG''(z)$, and setting $z = 1$ in this (namely $G'(1) + G''(1)$) gives the value of $E[X^2]$.

• Yes thats exactly where I understood the question wrong. My only problem now is, How do I compute $G_n(z),\ G_n'(z)\ and \ G_n''(z)$ . I already know $G′n(1)$. – Kyuubi Feb 19 '14 at 15:12