0
$\begingroup$

I'm trying to solve the following recurrence: $$ a(n) = \sum_{k=1}^n {{n-1}\choose{k-1}} a(n-k) \sum_{r=1}^k (r-1)! a(k-r).$$

My first thought was to use generating functions. However, I can't quite seem to get an answer. The first summation suggests to me that I should use exponential generating functions (since it looks like a product of exponential generating functions), but the second summation suggests to me that I should use ordinary generating functions (since it looks like a product of ordinary generating functions).

For example, if I assume $A(x)= \sum_n a(n)x^n/n!$, then I get something like $$A(x) = \int A(x)B(x) +1$$ where $B(x)=\sum_n b(n) x^n/n!$ and $b(n) = \sum_{k=0}^n k!a(n-k)$. But then I'm stuck on how to get $B(x)$ in terms of $A(x)$.

Maybe someone has some insight? Should I use ordinary or exponential? Or should I use some other technique to solve this recurrence? Thanks for any help!

$\endgroup$
  • $\begingroup$ I suggest exponential since if $\alpha_0=1$, then $\alpha_n$ grows like $n!c^{n+1}$ for $c=1.31...$ Where did you find this recursion? $\endgroup$ – Somos Aug 8 '17 at 17:38
  • $\begingroup$ I found it looking at some properties of labelled trees. $\endgroup$ – K.A. Aug 9 '17 at 15:08

Your Answer

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

Browse other questions tagged or ask your own question.