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.
Best Answer
I can recommend two books: "Concrete Mathematics: Foundation for Computer Science" by R. Graham (ISBN-10: 0201558025) and "Proofs that Really Count: The Art of Combinatorial Proof" by A. Benjamin (ISBN-10: 0883853337). They are both worth a closer look.