How do you solve this recurrence (or multivariate recurrences in general)? Note that $p\in[0,1]$ and $n\in\mathbb{N}$ are given constants, where $np\leq 1$.


$$f:(\mathbb{N}\cup\{0\})\times(\mathbb{N}\cup\{0\})\rightarrow[0,1]$$
Base case: $f(0,b)=(1-np)^b$ $\forall$ $b\geq 0$.


$f(a,b)=f(a-1,b-1)[n-(a-1)]p+f(a,b-1)[1-(n-a)p]$, if $a\leq \min{(n,b)}$.


$f(a,b)=0$, otherwise.


Note: The recursive definition could just be applied for $a\leq b$. The function values for $n< a\leq b$ (if $n < b$) can be set to $0$ afterwards.


I have attempted using a multivariate generating function, but it doesn't yield a good simplification. Also looked into somehow manipulating the formula for multivariate taylor series, but to no avail.



How to solve a specific multivariate recurrence relation (or general ones)
I get $$f(a,b) = \frac{ (1-np)^b n!}{(n-a)!} \sum\_{j=0}^b \binom{b}{j} \left\{ j \atop a \right\} \left(\frac{p}{1-np}\right)^j,$$ where $\left\{ j \atop a \right\}$ is a [Stirling number of the second kind](http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind). I tested the formula in Mathematica against your recurrence for different values of $n$ and $p$, and they agree. Unfortunately I'm having trouble pasting the Mathematica input and output that verifies that agreement on this site without it turning into gobbledygook.


To get the formula I used Theorem 6 (which is actually due to Neuwirth) in my paper "[On Solutions to a General Combinatorial Recurrence](https://cs.uwaterloo.ca/journals/JIS/VOL14/Spivey/spivey31.pdf)," *Journal of Integer Sequences* 14 (9): Article 11.9.7, 2011. The paper is about solution techniques for solving certain multivariate recurrences. Your recurrence happens to be in one of the forms for which the techniques work.


There might be a way to simplify the summation involving binomial coefficients and Stirling numbers, but I don't see it right now.




---


*Added*: The formula I used is the following.


**Theorem**. Suppose $R(n,k)$ satisfies the recurrence $$(\alpha(n-1) + \beta k + \gamma)R(n-1),k) + (\beta' + \gamma')R(n-1,k-1) + [n=k=0].$$ Then $$ R(n,k) = \left(\prod\_{i=1}^k (\beta' i + \gamma') \right) \sum\_{i=0}^n \sum\_{j=0}^n \left[ n \atop i \right] \binom{i}{j} \left\{ j \atop k \right\} \alpha^{n-i} \beta^{j-k} \gamma^{i-j}.$$
(Here, $0^0$ is taken to be $1$.)


For the OP's recurrence, we have $\alpha = 0, \beta = p, \gamma = 1-np, \beta' = -p,$ and $\gamma' = (n+1)p$.


