For a positive integer $q$ define a sequence of polynomial as follows:
$$\begin{align} p_0(q)&\equiv1\\ p_1(q)&\equiv0\\ p_n(q)&=q^n-\sum_{k=1}^n{k+q-1\choose k}p_{n-k}(q),\ n\geq2 \end{align}$$
Experimentation suggests that $$p_n(q)=(q-1)^qq^{n-q},\text{ for }n\geq q$$
I stumbled on this while trying to solve this problem on the probability that a randomly selected polynomial in a field with $q$ elements has no roots in the field. I wanted to figure out what the answer would be, so I counted the non-vanishing monic polynomials by subtracting the number of polynomials with a root. An $n$th-degree polynomial with a root is a product of $k>0$ terms of the form $(q-a)$ times a non-vanishing polynomial of degree $n-k,$ which accounts for the recurrence relation above.
While these experiments allowed me to guess the correct probability, I wasn't able to prove anything, because the polynomials themselves get complicated very fast.
$$\begin{align} p_2(q)&=\frac{q \left(q - 1\right)}{2}\\ p_3(q)&=\frac{q^{3}}{3} - \frac{q}{3}\\ p_4(q)&=\frac{q \left(q - 1\right) \left(3 q^{2} + q + 2\right)}{8}\\ p_5(q)&=\frac{q \left(q - 1\right) \left(q + 1\right) \left(11 q^{2} - 5 q + 6\right)}{30}\\ p_6(q)&=\frac{q \left(q - 1\right) \left(53 q^{4} + 26 q^{3} + 19 q^{2} - 2 q + 24\right)}{144}\\ p_7(q)&=\frac{q \left(q - 1\right) \left(q + 1\right) \left(309 q^{4} - 154 q^{3} + 239 q^{2} - 154 q + 120\right)}{840}\\ &\vdots \end{align}$$
Jyrki Lahtonen has given an elegant solution to the original problem, which incidentally establishes this identity when $q$ is a prime power, but in my experiments, I noticed that it seems likely to be true when $q$ is any positive integer. Using sympy, I calculated the polynomials $p_n$ for $n\leq25,$ and verified the identity for $q$ in the same range.
I don't have any good ideas about how to prove this. Since we know it's true for prime powers, I thought about trying to prove that if it's true for relatively prime integers $q$ and $r,$ then it's true for $qr,$ but the problem is that we have to deal with $p_n$ when $n$ is small, and 1) the induction hypothesis doesn't cover that, and 2) the polynomials themselves don't have a convenient explicit formula. I'm not clever enough to find the explicit formula for the $p_n$ given in Felix Matin's answer.
So the only promising approach I can think of is to find something that the $p_n$ count, even when $q$ is not a prime power, but I have no idea what that would be.
Of course, the definition of the $p_n$ is valid if $q$ is a real (or even a complex) number. Can anything be said in these larger domains?
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
$$ \bbx{\mbox{Lets}\ \mc{P}\pars{q,z} \equiv \sum_{n = 0}^{\infty}p_{n}\pars{q}z^{n} \implies p_{n}\pars{q} = \bracks{z^{n}}\mc{P}\pars{q,z}} $$
The above general recurrence is conveniently rewritten as $\pars{~\mbox{with}\ n \geq 2~}$: $$ p_{n}\pars{q} + qp_{n - 1}\pars{q} = q^{n} - \sum_{k = 2}^{n}{k + q - 1 \choose k} p_{n - k}\pars{q} $$
Then, \begin{align} &\sum_{n = 2}^{\infty}p_{n}\pars{q}z^{n} + q\sum_{n = 2}^{\infty}p_{n - 1}\pars{q}z^{n} \\ = &\ \sum_{n = 2}^{\infty}q^{n}z^{n} - \ \sum_{n = 2}^{\infty}z^{n} \sum_{k = 2}^{n}{k + q - 1 \choose k} p_{n - k}\pars{q} \\[5mm] &\ \overbrace{\sum_{n = 0}^{\infty}p_{n}\pars{q}z^{n}} ^{\ds{\mc{P}\pars{q,z}}}\ -\ \overbrace{p_{0}\pars{q}}^{\ds{1}}\ -\ \overbrace{p_{1}\pars{q}}^{\ds{0}}\ z\ +\ q\ \overbrace{\sum_{n = 1}^{\infty}p_{n}\pars{q}z^{n + 1}} ^{\ds{z\bracks{\mc{P}\pars{q,z} - 1}}} \\ = &\ {q^{2}z^{2} \over 1 - qz} - \sum_{k = 2}^{\infty}\ \underbrace{k + q - 1 \choose k} _{\ds{{-q \choose k}\pars{-1}^{k}}}\ \underbrace{\sum_{n = k}^{\infty} p_{n - k}\pars{q}z^{n}}_{\ds{z^{k}\mc{P}\pars{q,z}}} \\[5mm] & \bracks{1 + qz + \sum_{k = 2}^{\infty}{-q \choose k}\pars{-z}^{k}} \mc{P}\pars{q,z} = 1 + qz + {q^{2}z^{2} \over 1 - qz} = {1 \over 1 - qz} \\[5mm] & \bracks{1 + qz + \pars{1 - z}^{-q} - 1 - qz}\mc{P}\pars{q,z} = {1 \over 1 - qz} \\[5mm] & \implies \bbx{\mc{P}\pars{q,z} = {\pars{1 - z}^{q} \over 1 - qz}} \end{align}
\begin{align} \mc{P}\pars{q,z} & = {\pars{1 - z}^{q} \over 1 - qz} = \bracks{\sum_{i = 0}^{\infty}{q \choose i}\pars{-z}^{i}} \bracks{\sum_{j = 0}^{\infty}\pars{qz}^{j}} \\[5mm] & = \sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty}{q \choose i} q^{j}\pars{-1}^{i}\sum_{n = 0}^{\infty}z^{n} \bracks{i + j = n} \\[5mm] & = \sum_{n = 0}^{\infty}\braces{\sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty}{q \choose i} q^{j}\pars{-1}^{i}\bracks{j = n - i}}z^{n} \\[5mm] & = \sum_{n = 0}^{\infty}\braces{\sum_{i = 0}^{\infty}{q \choose i} q^{n - i}\pars{-1}^{i}\bracks{n - i \geq 0}}z^{n} \\[5mm] & = \sum_{n = 0}^{\infty}\braces{q^{n} \sum_{i = 0}^{n}{q \choose i} \pars{-\,{1 \over q}}^{i}}z^{n} \end{align}
$$ \bbox[15px,#ffd,border:1px groove navy]{p_{n}\pars{q} = q^{n}\sum_{i = 0}^{n}{q \choose i} \pars{-\,{1 \over q}}^{i}\,,\qquad q \in \mathbb{N}_{\ \geq\ 1}} $$