Define recursively polynomials $f_n(a,b)$ by $$ f_0(a,b)=1,\ \ f_n(0,b)=0\ \mathrm{for}\ n>0 $$ $$ \frac{\partial}{\partial a}f_n(a,b) = f_{n-1}(b-a,1-a). $$ For instance, $$ f_1(a,b) = a,\ \ f_2(a,b) = \frac 12(2ab-a^2) $$ $$ f_3(a,b) = \frac 16(a^3-3a^2-3ab^2+6ab). $$ Is there a ``nice'' solution to this recurrence, e.g., a formula for the generating function $\sum_{n\geq 0}f_n(a,b)x^n/n!$? What I am really interested in is $f_n(1,1)$. For the motivation, see the solution to Exercise~4.56(d) (pg. 645) of Enumerative Combinatorics, vol.1, 2nd ed.
-
$\begingroup$ Hi Richard, I added the page number of the solution; I hope you don't mind. $\endgroup$– SuvritFeb 7, 2012 at 22:20
-
2$\begingroup$ Here are the values of $f_n(1,1)$ for $0\le n\le 15$: $1,1,1,1,2,5,14,47,182,786,3774,19974,115236,720038,4846512,34950929$ (of course they don't mach anything in the OEIS). $\endgroup$– Pietro MajerFeb 8, 2012 at 0:25
-
$\begingroup$ You mean $n!f_n(1,1)$. $\endgroup$– Richard StanleyFeb 8, 2012 at 1:07
-
$\begingroup$ (yes sorry, I meant the numerators) $\endgroup$– Pietro MajerFeb 8, 2012 at 9:01
-
$\begingroup$ It is in the OEIS: A096402, submitted by a certain Stanley ;). $\endgroup$– Brendan McKayFeb 8, 2012 at 10:43
1 Answer
There seems to be a PDE for $g(a,b,x)=\sum_{n\ge0}f_n(a,b)x^n$, which can be thought of as a boundary value problem in the triangle $0\lt a\lt b\lt1$. $$g_{aab}+g_{abb}+x^3g=0$$ ($x$ is a parameter and subscripts are derivatives) with boundary values $g(0,b,x)=1$, $g_a(a,a,x) = x$, and $g_{ab}(a,1,x) = x^2$. This comes from iterating the $f_n$ recurrence, after Pietro's remarks that $(a,b)\to(b-a,1-a)$ has period 3 suggested looking at third derivatives. Does that determine $g$ uniquely, nicely? I don't know yet. [Edit: I wrongly wrote $g$ at first using $\frac{x^n}{n!}$.]