Basic

• Introduction
• Complex Counting Problem
• Subtraction rule (inclusion and exclusion
• Division rule


• Circular problem:
  
  \( \frac{n!}{n} = (n-1)! \)
  
  Circular problem -- stirling number of the first kind

Inclusion and Exclusion

• Inclusion and exclusion -- Inclusion and Exclusion (continue -- [Exercise]
• onto function -- onto function (continue
• Euler's \(\phi\)-function (relative to the prime number)

The Pigeonhole Principle

• basic pigeonhole
• the general pigeonhole
• The sequence problem
• The ramsey theory

Permutation && combination

• permutation
• combination -- [ combination exercise ]

Binomial theorem

• Binomial theorem -- [more term] -- [Exercise] More term
• pascal identity and triangle
• other Binomial identities

some exercises

• some exercises

generalize permutation and combination

• permutations with no repetition: \( P_{r}^{n} = \frac{n!}{(n-r)!} \)
• combinations with no repetition: \( C_{r}^{n} = \frac{n!}{r!(n-r)!} \)
• permutations with repetition: \( n^r \)
• combinations with repetition: \( \begin{pmatrix} n-1+r \\ r \end{pmatrix} \)
  [Exercise] combinations with repetition
  [Exercise] combinations with repetition (continue
  
• permutation with indistinguishable objects:

distributing objects

• Distributing distinguishable objects into distinguishable boxes = permutation with indistinguishable objects.
• Indistinguishable objects into distinguishable boxes as same as combinations with repetition.
• distinguishable objects and indistinguishable boxes - more difficult(no closed formulae).
  Stirling numbers of the second kind.(boxes cannot be empty.)
  S(n,j): n distinguishable objects into j indistinguishable boxes.
  
  Formula:
  \[ S(n,j)= \frac{1}{j!}\sum_{i=0}^{j-1}(-1)^{i} \begin{pmatrix} j \\ i \end{pmatrix} (j-i)^{n} \]
  
  Using in n distinguishable objects and k indistinguishable boxes.
  \[ \sum_{j=1}^{k} S(n,j)= \sum_{j=1}^{k} \frac{1}{j!}\sum_{i=0}^{j-1}(-1)^{i} \begin{pmatrix} j \\ i \end{pmatrix} (j-i)^{n} \] ex.
  S(4,3)=6.
  S(4,2)=7.
  S(4,1)=1.
  6+7+1=14.
  stirling number of the second kind
• indistinguishable objects and indistinguishable boxes

Derangement

• Derangement

Probability

• probability -- continue
• conditional probability
• random variable
• independent event
• expected value

Question