If I have $k$ integers, how many sequences of length $n > k$ can I make of them such that the order of the elements does not matter?
If the length was equal to the amount of integers in our use, $n=k$, we could calculate it somewhat like $$ k + k \cdot (k-1) \cdot \left( \begin{array}{cl} k \\1\end{array} \right) + k \cdot (k-1) \cdot (k-2) \cdot \left( \begin{array}{cl} k \\2\end{array} \right) + \ldots + k \cdot \ldots \cdot 2 \cdot \left( \begin{array}{cl} k \\k-2\end{array} \right) + 1 $$ by first assuming every integer is the same, then that there is one differing from the others, then two etc. I am interested in showing that while the number of all sequences grows exponentially with $n$, the number of sequences such as this grows only polynomially. Is there a way to see this without resulting to raw calculation like this?
You're probably overthinking it. Because order does not matter, the answer by stars-and-bars is $$\binom{n+k-1}{k-1}$$ This also works if $n\le k$. For fixed $k$, this is a polynomial in $n$, because among all linear factors with $n$ in them in the expansion of the binomial, all but $k-1$ terms in the numerator are cancelled out.
Of course, if order does matter, the number of sequences $k^n$ grows exponentially in $n$.