In my abstract algebra course, I was trying to find the number of monic polynomials in $Z_3[x]$ that can be factored into a 3 linear terms.
$(x-a)(x-b)(x-c)$ where the order does not matter, and $a,b,c \in$ {$0,1,2$}.
There are ten possible polynomials here, and it seems that the formula ${n+k-1}\choose{k}$ seems to work here.
It has been a long time since I brushed up on my combinatorics and this method usually corresponds to the stars and bars approach from what I remember. How can I see this?
The stars-and-bars approach goes like this: consider three stars that represent the three variables $a,b,c$, and two bars. Those bars can be arranged freely among the stars – two bars may be adjacent, they may go at the ends – but they always partition the stars into three (possibly empty) parts.
When those three parts are interpreted as "those coefficients which have the value 0, 1, 2 respectively", there is a bijection between the partitions and the assignment of values to $a,b,c$ with repetition and without order. Thus the number of polynomials satisfying the condition is equivalent to the number of ways of choosing two objects out of five to be the bars, or $\binom52=\binom{3+3-1}{3-1}$.