Introduction to Combinatorics

Counting and Probability (High School Level)

Overview

Counting Addition Rule Multiplication Rule Perm. & Comb. Binomial Thm. Probability
$_nP_r$, $_nC_r$
$n!$
$(a+b)^n$
$P(A) = \dfrac{|A|}{|U|}$

In this introduction, we learn the basics of counting and probability covered in high school mathematics. Through the fundamental operation of "counting," we gain an entry point into combinatorial thinking.

Learning Objectives

  • Understand and apply the addition and multiplication rules
  • Understand the difference between permutations and combinations and compute them
  • Understand and apply the binomial theorem
  • Understand the basic concepts of probability

Table of Contents

  1. Chapter 1 Counting Principles

    Addition rule, multiplication rule, tree diagrams

  2. Chapter 2 Permutations

    Definition of permutations, factorials, circular permutations

  3. Chapter 3 Combinations

    Definition of combinations, binomial coefficients, Pascal's triangle

  4. Chapter 4 Binomial Theorem

    Binomial expansion, multinomial theorem

  5. Chapter 5 Probability Basics

    Definition of probability, addition theorem, complementary events

  6. Chapter 6 Conditional Probability

    Conditional probability, multiplication theorem, independence

Prerequisites

  • Basic middle school arithmetic skills
  • Basic concepts of sets

Key Formulas

Permutation

$$_nP_r = \frac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1)$$

The number of ways to choose $r$ items from $n$ and arrange them in order.

Combination

$$_nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

The number of ways to choose $r$ items from $n$ (order does not matter).

Binomial Theorem

$$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$$

References