Basic Counting Principles

• product rule
  • n1 ways to do first task, n2 ways to do first task: total n1*n2 way
  • (set) for finite sets A1 … Am |A1 x A2 x … x Am| = |A1| |A2| … |Am| (cartesian product)
• Sum rule
  • one of n1 ways or one of n2 ways → n1+n2 ways
  • (set) for finite disjoint sets A1 … Am |A1 U A2 U … U Am| = |A1|+ … + |Am|
• Subtraction rule
  • one of n1 ways or one of n2 ways → n1+n2 -common ways
  • (set) for finite sets A,B |A U B| = |A| + |B| - |A ∩ B|

Pigeonhole Principle

• k+1 object in k box → at least one box contains more than 2 objects
• (general version) N object in k box → (ceil) N/k objects

Permutation 순열 ordered arrangement of r elements P(n,r) = nPr

Combination 조합 unordered selection of r elements C(n,r) = nCr = (n r) (세로로 씀)

Binomial theorem 이항정리 (x+y)^n = SIGMA nCi x^n-i y^i

Pascal’s Identity nCr = n-1Cr-1 + n-1Cr

Permutation with Repetition 중복순열 nPIr = n^r

Combination with Repetition 중복조합 H는 Homogeneous 를 뜻함 nHr = ((n r)) = n+r-1 C r

• n-1개의 칸막이와 r개의 칸