Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The recurrence is

$ a_n = (n-1) a_{n-1} + (n-2)a_{n-2} $

I tried using exponential generating functions and have problems with it (the second term mostly) Further can this be solved without reducing it to a differential equations?

share|improve this question
    
You could try $b_n=na_n$. Then your recurrence becomes $\frac{b_n}{n}=b_{n-1}+b_{n-2}$ –  vadim123 Apr 25 '13 at 13:58
    
That's the recurrence relation for the dearrangements problem (hatcheck problem), which is solved using calculus. I guess there is no way to circumvent that little devil, calculus that is.. –  Vigneshwaren Apr 25 '13 at 16:17
    
@Vigneshwaren, it is close to the derangements recurrence $D_n = (n - 1) (D_{n - 1} + D_{n - 2})$, but not the same. –  vonbrand Apr 25 '13 at 18:03

3 Answers 3

up vote 1 down vote accepted

Define $A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!}$. Write: $$ a_{n + 2} = (n + 1) a_{n + 1} + n a_n $$ From properties of exponential generating functions: $$ \begin{align*} A''(z) &= (z \frac{d}{d z} + 1) A'(z) + z A'(z) \\ A''(z) &= z A''(z) + (1 + z) A'(z) \end{align*} $$ This looks second order, but is a homogeneous linear first order differential equation for $A'(z)$. Courtesy of maxima we have for some $c_1$: $$ A'(z) = \frac{c_1 e^{-z}}{(1 - z)^2} $$ This gets ugly... maxima integrates this to: $$ A(z) = c_2 + \frac{c_1 E_2(z - 1)}{1 - z} $$ where: $$ E_2(z) = z \int_z^\infty \frac{e^{-t} d t}{t} $$ NIST has details on this function.

Expanding $A'(z)$ in series (multiply the exponential by the series for $(1 - z)^{-2}$) and integrating term by term might be a nicer bet...

$$ \begin{align*} A'(z) &= c_1 \sum_{k \ge 0} \binom{-2}{k} (-z)^k e^{-z} \\ &= c_1 \sum_{k \ge 0} \binom{k + 1}{1} z^k e^{-z} \\ &= c_1 \sum_{k \ge 0} (k + 1) z^k e^{-z} \\ A(z) &= c_2 - c_1 \sum_{k \ge 0} (n + 1) \int_z^\infty t^k e^{-t} d t \end{align*} $$ Too bad that the integrals don't give any sort of nice polynomials... would need to set up a recurrence for those by integration by parts.

Edit

Do I feel dumb... when I do know that if: $$ C(z) = \sum_{n \ge 0} c_n z^n $$ then: $$\frac{C(z)}{1 - z} = \sum_{n \ge 0} \left( \sum_{0 \le k \le n} c_k \right) z^n $$ For an exponential generating function it is $a_0 = A(0)$, $a_1 = A'(0)$. So we can say: $$ \begin{align*} A'(z) &= \frac{a_1 e^{-z}}{(1 - z)^2} \\ &= a_1 \sum_{n \ge 0} \left( \sum_{0 \le r \le n} \sum_{0 \le s \le r} \frac{(-1)^s}{s!} \right) z^n \end{align*} $$ This gives: $$ \frac{a_n}{n!} = [n = 0] a_0 + [a > 0] a_1 \sum_{0 \le r \le n - 1} \sum_{0 \le s \le r} \frac{(-1)^s}{s!} $$ Summing by parts: $$ \sum_{0 \le r \le n - 1} \sum_{0 \le s \le r} \frac{(-1)^s}{s!} = n \sum_{0 \le s \le n} \frac{(-1)^s}{s!} - 0 \cdot 1 - n \cdot \frac{(-1)^n}{n!} = n \sum_{0 \le s \le n - 1} \frac{(-1)^s}{s!} $$ So: $$ a_n = [n = 0] a_0 + a_1 n! \cdot n \sum_{0 \le s \le n - 1} \frac{(-1)^s}{s!} $$ (I think something isn't quite right here, but I'm tired...)

share|improve this answer
1  
That was brilliant and helpful, and this is gonna take some of my time. Thanks –  Vigneshwaren Apr 26 '13 at 16:40

By vadim123's hint, the substitution $b_{n + 1} = n a_n$ gives: $$ b_{n + 1} = n (b_n + b_{n - 1}) $$ Defining the exponential generating function $B(z) = \sum_{n \ge 0} b_n \frac{z^n}{n!}$, by properties of exponential generating functions: $$ \begin{align*} B'(z) &= z B'(z) + z \frac{d}{dz} \int B(z) \\ B'(z) (1 - z) &= z B(z) \\ B(z) = \frac{c e^{-z}}{1 - z} \end{align*} $$ From here: $$ \begin{align*} b_n &= c n! \sum_{0 \le k \le n} \frac{(-1)^k}{k!} \\ a_n &= c (n + 1) (n - 1)! \sum_{0 \le k \le n - 1} \frac{(-1)^k}{k!} \end{align*} $$ Ugly as they come... but at least $a_n \approx c (n + 1) (n - 1)! e^{-1}$

share|improve this answer

The original problem which follows this recursion is:

A good permutation of {1,2,..., n} is one which doesn't
have two consecutive numbers (like {1,2} etc.). Find the number
of such permutations.

I figured the recursion which was fun to construct. I was later told that this was somehow related to Euler's totient function $\phi$, which I don't see how though. But most importantly the proof of this recursion is what makes it fun and interesting.

share|improve this answer
    
You should really add this as an edit to your question. –  vonbrand Apr 26 '13 at 18:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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