One of my favorite counting methods, not covered in your list, is counting via symmetries. Whenever the objects you want to count have some associated symmetry, you can exploit this symmetry to simplify the counting process. For instance, what is the number of ways to color the faces of a cube with three colors so that when you turn it around you do not reproduce the same color positions (so the all-blue cube is excluded)? This is a question where we can exploit the symmetries of the cube.
The technical tool for using symmetries to count is the notion of a group acting on a set. In general this is a complicated process and requires too much reading for you to present, but for an introduction all you need is to understand this wikipedia page:
which comes complete with an application of group theory to the counting problem I mentioned above. It still involves quite a bit of reading (you need to understand what a group action is on an elementary level), but with sufficient preparation it will make for an impressive presentation. It is always fascinating to see how geometrically-inspired concepts like orbits and stabilizers and transformations can be exploited to attack tricky counting problems!
If you search this site for group theory, coloring and combinatorics you will get lots of interesting questions and answers related to the applications of group theory to counting. Here is one (slightly advanced) I just dug up:
What are the symmetries of a colored rubiks cube?