1
$\begingroup$

I am fairly new to generating functions and have been trying to solve the following recurrence for a computer science problem. $$ f(k,d,n) = \sum_{i=1}^{n-1} \binom{n-2}{i-1} \left(\frac{1}{2}\right)^{n-2} \left(\sum_{j=0}^{k} f(k-j,d-1,n-i)\cdot f(j,d-1,i)\right)$$ Note that $$ f:\mathbb{N}^3 \rightarrow [0,1] $$ with the following base cases: $$ \begin{split} f(k,d,1)& = \begin{cases} 1 & (k=0 \wedge d!=0) \vee (k=1 \wedge d=0)\\ 0 & \text{otherwise} \end{cases} \\ f(k,d,2)&= \begin{cases} 1 & ((k=0 \wedge d!=1) \vee (k=2 \wedge d=1))\\ 0 & \text{otherwise} \end{cases} \\ \end{split} $$ and the following domains: $$ \begin{split} n &\in \{1,2,3,4,\ldots\} \\ k &\in \{0,1,2,\ldots,n-1,n\} \\ d &\in \{-\infty,\ldots,-2,-1,0,1,2,\ldots,\infty\} \\ \end{split} $$

From f(k,d,n) and base cases we can derive the following for d<0: $$ f(k,d,n)= \begin{cases} 1 & k=0 \\ 0 & k>0 \end{cases} \\ $$

I would like to mention that $f(k,d,n)$ can also be expressed as the following: $$ f(k,d,n) = \sum_{i=1}^{n-1} \binom{n-2}{i-1} \left(\frac{1}{2}\right )^{n-2} \left(\sum_{j=0}^{k} f(j,d-1,n-i)\cdot f(k-j,d-1,i)\right)$$

Thank you for your time and help in advance.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Define $$F_d(x,y) := \sum_{k\geq 0}\sum_{n\geq 1} f(k,d,n) x^k \frac{y^{n-1}}{(n-1)!}.$$ Then the recurrence is equivalent to $$\frac{\partial F_d}{\partial y}(x,y) = F_{d-1}(x,y/2)^2,$$ while the initial conditions imply $$F_0(x,0)=x,\quad F_d(x,0)=1\ \text{for}\ d\ne 0$$ and $$\frac{\partial F_1}{\partial y}(x,0)=x^2,\quad \frac{\partial F_1}{\partial y}(x,0)=1\ \text{for}\ d\ne 1.$$

This can be seen as a generalization of your previous question.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Well, I was trying to look at the same problem from different perspective and was hoping to be able to find an "easier" formula for it, since the formula in my previous question did not have non recursive expression. $\endgroup$
    – Koko Nanahji
    Commented May 24, 2020 at 22:17
  • 1
    $\begingroup$ @KokoNanahji: The g.f. for $\sum_{k=0}^n kf(k,d,n)$ is $\frac{\partial F_d}{\partial x}(1,y)$. If we denote it as $H_d(y)$, then $H_d'(y) = 2 F_{d-1}(1,y/2) H_{d-1}(y/2)$. $\endgroup$
    – Max Alekseyev
    Commented May 25, 2020 at 1:30
  • $\begingroup$ thank you very much for your quick response. I deleted my question because I figured out a way to simplify $\sum_{k=0}^{n} k \cdot f(k,d,n)$ using the constraint that I forgot to mention which is $\sum_{k=0}^{n} f(k,d,n)=1$. Let $f(d,n)=\sum_{k=0}^{n} k \cdot f(k,d,n)$ then $f(d,n)=\sum_{i=0}^{n-2} \binom{n-2}{i} \left(\frac{1}{2}\right)^{n-3} \cdot f(d-1,i+1) $ $\endgroup$
    – Koko Nanahji
    Commented May 25, 2020 at 17:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .