Ioi/combinatorics

หน้านี้รวบรวมหัวเรื่องที่สอนในหัวข้อ Combinatorics ในค่ายอบรมคอมพิวเตอร์โอลิมปิก

• Basic counting techniques
  • 0-th law - add exclusive options
  • 1-st law - multiply successive choices
  • 2-nd law - Shepard's law (if you overcount by the same amount, you can divide to correct)

• Counting by cases

Questions: How many strings with n bits contain no adjacent 1's?

• Permutations and combinations

• Counting with bijection (or, one-to-one mappings)

• Inclusion - exclusion

• Binomial coefficients

• Counting partitions

• Sets of permutations
  • Cycle structures of a permutation
  • Transposition
  • Even/odd permutations
  • Generators
  • Derangement

• Catalan numbers