In Enumerative Combinatorics, students are learning strategies to count possibilities.
Doc Durst is choosing pokémon to fight at the gym. The way that this works is as follows: you choose an unordered set of 6 pokémon for your battle. She has 4 Abras, 3 Vaporeons, and 5 Snorlaxes. How many ways can she choose a team to fight with?
The question above could have originated in Pokémon Go club, but it actually first appeared on the practice End of Block Assessment that we took in Enumerative Combinatorics on Friday. This is a tough question! If Doc Durst had unlimited amounts of each pokémon, then it would be much easier to solve: and that's the first key to solving this problem. Earlier in the block, students in Enumerative Combinatorics learned that if you want to count the number of ways to select an unordered list of identical objects (pokémon) and place them in distinct boxes (Abra, Vaporeon, Snorlax) then you can use a method called stars and bars.
However, there's a catch: Doc Durst only has a limited supply of each type of pokémon. So, we can't just use stars and bars, because this would over-count the possibilities: we accidentally counted situations where Doc Durst chose 5 Abras, or 4 Vaporeons and 2 Abras, or other impossible combinations. The students had to be able to subtract off all of the situations where Doc Durst used too many Abras, too many Vaporeons, or too many Snorlaxes.
This is what the subject of enumerative combinatorics is about. Counting problems, at their essence, can be distilled into basic principles: in one problem we are sorting unordered identical objects into distinct boxes, in another problem we are selecting an ordered list of k people from n people, in yet another problem we are selecting an unordered set of k people from n people. However, it can be quite tricky to see through the facade of the problem, and identify the method needed to solve it.
In addition to learning principles of counting, the Enumerative Combinatorics class covers a few more core topics in discrete math. We have been playing games and puzzles with graphs, and learning about graph theory and graph properties. We have also been studying proofs by induction, a key type of mathematical proof, which allows us to prove a formula or statement for all positive integers in a step by step process. On one particularly fun day of induction proofs, we played around with "Odd Pie Fights", and showed that if an odd number of proofniks decided to have a pie fight, and each throw pies at the closest proofnik, at least one person would be left unscathed.
In our last week of class, we will continue playing graph theory games and explore some of the basics of Ramsey theory. Even though next week is our last week of class, students will surely see the techniques they learned in Enumerative Combinatorics in future math classes!
-- Sachi Hashimoto