Any finite graph has a chromatic polynomial, whose value at $n$ is the number of colorings using $n$ different colors. Its polynomiality can be proven by induction. What intrigues me more is its coefficients, which are all nonnegative integers (up to alternating signs). To any graph, there is a matroid behind it, which explains why the coefficients are integers and even log-concave. However, the meaning (if any) of the coefficients is still obscure to me.
I hope one can explain the coefficients without induction. What's the combinatorial meaning of the coefficients? Are there combinatorial models behind? Is there an integer matrix whose characteristic polynomial is proportional to it?