Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

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}

share|improve this answer
    
Thanks ... but the question was for a reference, not for a solution. (We had that already, as I clearly posted in the OP.) –  Sacha Jul 3 at 8:57
    
@Sacha, just solved it for fun. –  vonbrand Jul 3 at 23:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.