We describe a framework for giving a combinatorial interpretation to some well-known results involving the power sum polynomials. We use some set-theoretic principles, such as the inclusion-exclusion principle and the image factorization of functions, to derive results about polynomials with rational coefficients that had previously been discovered by purely arithmetic or algebraic means. With this, we give a characterization for the divisibility of a polynomial by a binomial coefficient. Also, for any positive odd number $n$ and natural numbers $a, b$, we prove that $a^n + b^n$ is divisible by $a+b$ through combinatorial means. We then computationally examine when a power sum is divisible by the sum of cubes.