MATH 239: Introduction to Combinatorics

Combinatorial proof: To show A and B refer to the same set, show

  • Basically, show that they show the same set

Links:

Chapter 1: Enumeration

Final Preparation

Things that i need to work on:

  • Bijection proof, revisit tutorial 8-4
  • Product lemma, string lemma, and sum lemma. When do you use these in proofs?
  • Overlap case…?

Other things to practice:

  • Hall’s theorem

Tip

I believe the key to mastering this final is being able to problem solve SUPER quickly. I struggled with the midterm for that. This is why you need to do lots of problems and just time yourself. Know the different theorems like the back of your hand, and when to use them. Build strong Intuition.

Get good at induction. It seems that a lot of the proof require the use of induction.

Final: I need to go through

  • all the assignments again,
  • as well as the practice final,
  • as well as other sample finals
  • as well as the tutorials

And then you should be good to go.

Practice Proofs:

  • Prove that “Every tree is bipartite” (use induction)

Template for strong induction

Inductive Hypothesis: Assume that X holds for any tree/graph with less than edges. Base Case: When , …, so the result holds Inductive Step: …