Help with the proof of a recurrence

Question

I have this recurrence to solve $$f(n,m)= f(n,m-1) + nf(n-1,m-1)$$ with $f(n,0)=1$ $\forall n \in \mathbb{N}$ with $n\geq m$ , and I found the solution guessing and it is $$\sum_{k=0}^m \frac{n!}{(n-k)!} \frac{m!}{(m-k)!k!}$$ But I can't prove it by induction and I'm sure that it is correct because I used Matlab to verify the result. I would be glad if someone can help me.

Answer 1

Computing some small values, we can find them in a table under A088699 in the OEIS, which gives us the definition

$A(n,m)$ is the number of ways to pair the elements of two sets (with respectively $n$ and $m$ elements), where each element of either set may be paired with zero or one elements of the other set.

Given a pairing counted by $A(n,m)$, if we inspect the first element of the $m$-element set, it is either

• not paired at all, leaving $A(n,m-1)$ ways to choose pairs for the other elements, or
• paired with any of the $n$ elements in the other set; both elements are removed from consideration, leaving $A(n-1,m-1)$ ways to choose pairs for the other elements,

which gives us the recurrence $A(n,m) = A(n,m-1) + n A(n-1,m-1)$. Also, when $m=0$, there is only one way to choose the pairs: not to choose any pairs. So $A(n,0) = 1$. The recurrence and initial conditions match $f(n,m)$, which confirms that OEIS's $A(n,m)$ is equal to your $f(n,m)$.

But from OEIS's combinatorial interpretation, it is easy to prove a formula. If we decide that we are going to choose a total of $k$ pairs, $k$ must satisfy $0 \le k \le m$. We choose a subset of $k$ elements from the $n$-element set that will belong to a pair, in $\binom nk$ ways. We choose a subset of $k$ elements from the $m$-element set that will belong to a pair, in $\binom mk$ ways. Finally, we can pair these up in $k!$ ways. This tells us that $$f(n,m) = \sum_{k=0}^m k! \binom nk \binom mk = \sum_{k=0}^m \frac{n!}{(n-k)!} \frac{m!}{(m-k)!\, k!}$$ as desired.