6. Combinatorics and Probability

Loosely, combinatorics is the area of mathematics concerned with “counting”. This has a natural relation to discrete mathematics. Recall countably infinite sets.

Combinatorics deals with the processes of counting. That is, how to count. But it also deals with counts themselves. Finding the number of things that satisfy a certain property, for example.

In this chapter we will explore some of the principles of counting. It’s not as easy as it sounds! This includes formulas for counting, the inclusion-exclusion principle, the pigeonhole principle. We will explore applications in permutations, combinations, and discrete probability.

• 6.1. Counting
  • 6.1.1. The Principles of Counting
    • Product Rule
      • The Product Rule for Sets
    • Sum Rule
      • The Sum Rule for Sets
    • Sum and Product, together
    • The Principle of Inclusion-Exclusion
  • 6.1.2. The Pigeon Hole Principle
    • Pigeon holes as functions
  • 6.1.3. Generalized Pigeon Hole
  • 6.1.4. Exercises
• 6.2. Permutations and Combinations
  • 6.2.1. Permutations
  • 6.2.2. Combinations
  • 6.2.3. Binomial Coefficients
  • 6.2.4. Exercises
• 6.3. Discrete Probability
  • 6.3.1. Finite Probability
    • With and without replacement
    • Probability of Complements and Unions
  • 6.3.2. Exercises