# Combinatorics project ideas for high school students

It's that time again! Last year I asked for high school project ideas in the area of algebraic geometry, this year it's combinatorics (you can include graph theory and combinatorial game theory if you like). Here is the link to last year's post: Algebraic geometry project ideas for high school students

I am teaching a "senior seminar" course for strong students at my local high school. For 6 weeks the students learned about combinatorics. Soon they will start projects based on material from the course which they have to present. The idea is that the question they have to answer is difficult enough to be worth presenting, but not too difficult as to go beyond the scope of what was taught. Does anyone have combinatorics problems which would be good topics for projects? Unlike last year, there will surely be a plethora of possible projects accessible to high school students, so please give projects which lead to some interesting result and requires a bit of cleverness. The topic can be from general combinatorics, algebraic combinatorics, graph theory or even game theory.

I should mention what they have already learned in my lessons. They learned enumerative combinatorics (general counting methods, generating functions, recursion relations, inclusion/exclusion principle, rook polynomials etc.), Polya enumeration, the game of Nim, and graph theory (basic defintions, planar graphs, graph colouring, Hamilton circuits, the shortest distance algorithm, etc.).

Any ideas from past experience would be a big help.

• What particular level of difficulty do you want, could you give an example (I'm thinking about graph theory)? – dtldarek Jan 27 '15 at 0:50
• I was thinking a project on the various counting problems whose solution is the Catalan numbers, or a project on interesting sequences such as De Bruijin sequences. Projects especially involving topics from outside the class would be interesting. – Sergio Da Silva Mar 3 '15 at 18:30
• I am in a similar situation. For the last two years I have allowed them to 1. Extend work that we've already done in class 2. Ask a "problem solving" style question, that involves principles from class 3. Scour books (of my choosing) for ideas related to the class (Including, incidentally, Benjamin, Graham, and Stanley's Catalan Numbers) 4. Do simple presentations on topics that I did not include, but could have (eg, basics of graph theory) 5. Something interesting in the same vein. What did you end up doing? How did the presentations turn out? – Jonathan Halabi Jan 12 at 14:32
• Hi Jonathan, your list of project choices sounds good. One group ended up doing a project on the Catalan numbers. The other one was a proof of the Hoffman-Singleton Theorem. It states that if a regular graph of degree $r$ and girth 5 has $r^2+1$ vertices, then $r = 2,3,7,57$. A surprising fact is that there does not yet exist an example of a graph for which $r=57$. The projects went really well. The students were happy that they were able to show a non-trivial proof to a theorem related to the course. – Sergio Da Silva Jan 16 at 2:11