As Thomas Andrews said in the comments, the formula that you have in mind is actually $\binom{n+k-1}{k-1}$, but it doesn’t apply here. Here you simply have to find a way to divide up the $n$-combinations into chunks that can easily be counted and then add up the results.
First count the $n$-combinations that have $k$ of their members from the set $\{1,\dots,n+1\}$. There are $\binom{n+1}k$ ways to choose those $k$ members. The rest of the $n$-combination is completely determined by the number of $a$’s, which may be anything from $0$ through $n-k$; this is a total of $n-k+1$ possibilities, so there are $(n-k+1)\binom{n+1}k$ $n$-combinations with $k$ of their members in the set $\{1,\dots,n+1\}$. The final answer is the sum of these totals over the possible values of $k$,
$\sum_{k=0}^n(n-k+1)\binom{n+1}k\;.$
If you manipulate the term $(n+1-k)\binom{n+1}k$ properly, you can transform it to a term of the form $c\binom{d}k$, where $c$ and $d$ don’t depend on $k$, and then evaluate the sum quite easily. I’ve included a hint for the manipulation that you need, but I’ve left it spoiler-protected to give you a chance to work it out on your own. Mouse-over to make it visible.
The manipulation that you need is of the form $\displaystyle(m-k)\binom{m}k=m\binom{m-1}k$, which you can check by writing out the binomial coefficients in factorial form.