2
$\begingroup$

Consider the following recurrence relation:

$A(h,0)=1\\ A(h,h)=c^h\\ A(h,r)=A(h-1,r)+(c-1)\cdot A(h-1,r-1).$

Obviously, this is just a generalization of A008949, where $c=2$. Since I'm pretty sure we're not the first ones dealing with it -- is there some source where it was already solved? I'm really only looking for a source to cite, we already have the solution.

Thanks in advance!

Sacha

1 Answers 1

2

Interesting double recurrence. Define the generating function $g(x, y) = \sum_{r, s} A(r, s) x^r y^s$, write without subtraction in indices: $ A(r + 1, s + 1) = A(r, s + 1) + (c - 1) A(r, s) $ Multiply by $x^r y^s$ and recognize the sums: \begin{align} \sum_{r, s} A(r + 1, s) x^r y^s &= \frac{1}{x} \left( g(x, y) - \sum_s A(0, s) y^s \right) \\ &= \frac{g(x, y) - g(0, y)}{x} \\ \sum_{r, s} A(r + 1, s + 1) x^r y^s &= \frac{g(x, y) - g(0, y) - g(x, 0) + g(0, 0)}{x y} \end{align} The $g(0, 0)$ term was subtracted twice in the last expression, and has to be restored.

Too bad that your boundary conditions take the form they do. You have: $ g(x, 0) = \frac{1}{1 - x} $ while $g(0, y)$ remains unknown. In any case: $ \frac{g(x, y) - g(0, y) - 1 / (1 - x) + 1}{x y} = \frac{g(x, y) - 1 / (1 - x)}{y} + (c - 1) g(x, y) $ Solving for $g(x, y)$ gives: \begin{align} g(x, y) &= \frac{g(0, y)}{1 - x - (c - 1) x y} \\ &= g(0, y) \frac{1}{1 - ((c - 1) y + 1)x} \\ &= g(0, y) \sum_r ((c - 1) y + 1)^r x^r \end{align} Thus: $ [x^r y^r] g(x, y) = [y^r] g(0, y) ((c - 1) y + 1)^r = c^r $ This is: $ \sum_{0 \le k \le r} \binom{r}{k} (c - 1)^{r - k} A(0, k) = c^r $ If we now define the exponential generating function: $ a(z) = \sum_{s \le 0} A(0, s) \frac{z^s}{s!} $ multiply the last equation by $\frac{z^r}{r!}$, and sum over $r \ge 0$, the resulting left hand side is the product of $a(z)$ and: $ \sum_{k \ge 0} (c - 1)^k \frac{z^k}{k!} = \exp((c - 1) z) $ while the right hand side is: $ \sum_{k \ge 0} c^k \frac{z^k}{k!} = \exp(c z) $ So: $ a(z) = \exp(z) $ Sneaky... it is just $A(0, s) = 1$, and thus $g(0, y) = 1 / (1 - y)$. We get: \begin{align} A(r, s) &= [x^r y^s] \frac{1}{(1 - y) (1 - x - (c - 1) x y} \\ &= [x^r y^s] \frac{1}{1 - y} \sum_k (1 + (c - 1) y)^k x^k \\ &= [y^s] \frac{(1 + (c - 1) y)^r}{1 - y} \\ &= \sum_{0 \le k \le s} \binom{r}{k} (c - 1)^k \end{align}

  • 0
    @Sacha, just solved it for fun.2014-07-03