a.
If we take $m=1$, then we will get that $k+1+n^1=2009^n$ or that $k=2009^n-1-n$. It is clear that this will be a solution: $(n, m, k) = (n, 1, 2009^n - n - 1)$.

b.
If $m=1$, then our equation comes to $k+1+n=2009^n$, which holds for the only value of $k$. Thus, new solutions can exist only when $m \ge 2$.

Consider $n=2009^s$, where $s$ is natural. Then $(2009^{s m^k}) < k + m^k + n^{m^k} = 2009^{2009^s}$, whence $s \cdot m^k < 2009^s$, and so $m^k < 2009^s$. Let us make use of the following lemma:

Lemma. For every natural $n$: $2^n \ge n$.

This lemma implies that for $m \ge 2$ we have $m^k \ge 2^k \ge k$, i.e. $k + m^k < 2009^s + 2009^s = 2 \cdot 2009^s$. But $k + m^k = 2009^{2009^s} - n m^k = 2009^{2009^s} - 2009^{s - m^k}$. Now since $2009^s > 2 \cdot 1000^s > 2 \cdot 2^s \ge 2s$ and $m \ge 2$, we get that the right side is divisible by $2009^{2s}$. But at the same time $1 < k + m^k < 2 \cdot 2009^s$ and thus the left side cannot be divisible by $2009^{2s}$. The obtained contradiction shows that for $n=2009^s$ the solution is unique. And it is evident that there are infinitely many such $n$.