Bivariate recurrence relation 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
 A: 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}
