TLDR Summary: There is a genre of undergraduate polynomial divisibility problems which look like this: Show that f(n) is divisible by some integer k. These pr

TLDR Summary: There is a genre of undergraduate polynomial divisibility problems which look like this: Show that f(n) is divisible by some integer k. These problems often appear to be (elementary) number theory problems. However, often there is a rather elegant proof associated with them which is based on combinatorics. The crux of this proof is that the polynomial counts the number of equivalence classes of a certain kind. This is closely related to https://en.wikipedia.org/wiki/Burnside%27s_lemma https://en.wikipedia.org/wiki/Burnside%27s_lemma The question at the end of the post is whether _all_ such problems must come this way