# Counting

## Basic Counting Principles

### The product rule

乘法原理

#### Exercise

•Prove Theorem: $ if |S| = n, then |P(S)| = 2^n$

### The sum rule

加法原理

### The Inclusion-Exclusion Principle

容斥原理

### The Pigeonhole Principle

抽屉原理

#### Theorem 1:

If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

#### Theorem 2:

If n objects are placed into k boxes, then there is at least one box containing at least n/k objects.

## Permutation

排列（考虑顺序）

## Combination

组合（不考虑顺序）

### 隔板法

How many solutions does the equation a + b + c = 11 have where a, b, and c are non-negative integers?

## Binomial Coefficients

二项式定理：

## Recurrence Relations

### Linear Homogeneous recurrence relation

Theorem 1:

Let