[이산수학] Chapter 6. Counting methods and the pigeonhole principle

1. Basic Principles

  - Menu for Quick Lunch : 점심 메뉴를 고르는 경우의 수

  1) Multiplication Principle(곱셈법칙)

     : k개의 연속적인 행동이 있을 때, 이 행동을 수행하는 경우의 수는 n1n2...nk

 

     ex) 8 bit string 에서 101이나 111로 시작하는 것의 개수 : 2^5 * 2

  2) Addition Principle (덧셈법칙)

  nj개의 elements를 가지고 있는 k개의 pairwise disjoint sets가 있을 때, 이 sets의 결합 X = ∪Xj 는 n1 + n2+...+ nk의 elements를 가진다.

 

2. Permutations and Combinations (순열과 조합)

  1) Permutation : 순열 (n!)

     r-permutation of n distinct elements는 n개의 요소중에 r개의 element를 배열하는 경우의 수 ( P(n,r) )

  2) Combination : 조합 ( C(n,r) = P(n,r) / r! = n!/(n-r)!r! )

 

3. Generalized Permutations and Combinations

  1) 중복된 것이 있는 순열 : n! / n1!n2! ... nt!

  2) 중복 조합 H(n,r) = C(n+r-1, n-1) = C(n+r-1, r) 

 

 * Lexicographic order 

 : 두 문자열 α = s1s2... sp, β = t1t2...tq 가 있을 때,

   p<q이고 모든 i에 대해 si = ti이거나, 어떤 i에 대해서 si < ti 이면 α<β 이다. 

ex) α = 1324, β = 1332, γ = 132이면 γ < α, α < β 이다.

 

* Algorithm

  1) R-combination

    - set {X1, ..., Xn} 에서 s1<s2<... 이고,  주어진 숫자 s에 대해 다음 r-combination t를 구하기 위해서는?

 - max가 아닌  element sm에 대해서 tm = sm +1, tm+1 =  sm+2 ... until tr

//Pseudo code

Combination(r, n){
  for i=1 to r, si = i;
  print(s1, ..., sr);
  
  for i=2 to C(n,r){
    m = r;
    max_val = n;
    
    while(sm == max_val) {
      m = m - 1;
      max_val = max_val -1 
    }
    
    sm = sm + 1;
    
    for j = m+1 to r
      sj = sj-1 +1;
      
    print(s1, ..., sr);
    }
  }

 

 

 2) Permutation 

function perm(n, S){
  //print first perm
  print(S);
   for(i=2; i<factorial(n); i++){
   
     print('===Iteration');
     
     m=n-1;
     
     while( S(m) > S(m+1) )
       m = m-1;
        
     print('index of right most digit that is less than its right');
     print(m);
     
     k=n;
     
     while(S(m) > S(k))
       k=k-1;
         
     print('index of right most digit that is greater than pivot');
     print(k);
     
     //swap sm and sk
     tmp = S(k);
     S(k) = S(m);
     S(m) = tmp;
     
     p=m+1;
     q = n;
     
     while(p<q){
       tmp = S(q);
       S(q) = S(p);
       S(p) = tmp;
       p++; q--;
     }
     
     print(S);
 }

 

 

4. Introduction to Discrete Probability

 - experiment : process that yields an outcome (수행)

 - event : outcome or a set of outcomes from an experiment (사건)

 - sample space : event of all possible outcomes (표본공간)

 

 - probability : 확률 : E / S (Event, Sample space)

 

 

5. Discrete Probability Theory 

  - n개의 가능한 결과가 있을 때, 이 결과들이 완전히 같게 나온다면, 각각은 1/n의 확률을 갖는다.

  - 만약 각 확률이 같지 않다면..? 

 

  1) Probabiity Function 

   : Sample space S안에서 outcome x의 값과 대응되는 확률 p

    0<=P(x) <=1, ∑P(x) = 1 

 

  2) Probability of an Event 

  : 어떤 event를 만족하는 outcome들이 나올 확률의 합

 

* 여사건

 

  3) Mutually Exclusive Events : 배반사건 (교집합이 공집합)

 

  4) Conditional Probability : 조건부 확률

  - Independent Events : 독립사건

     -> P(E|F) = P(E) : 사건 E는 사건 F가 일어나나 일어나지 않나 확률이 같다. 즉 E는 사건 F와 독립사건이다.

     -> E와 F가 독립사건이면, P(E ∩ F) = P(E)P(F)

 

 

6. Pattern recognition 

  : items을 여러가지 특징을 기반으로 class를 나눈다. 

   - feature F의 집합이 주어졌을 때, F를 가지고 있을 때 class C일 확률은 F: P(C|F) 로 계산할 수 있다.

   - item은 가장 probable 한 class 에 배정한다. 즉, P(C|F)가 가장 큰 class에 할당한다.

 

 

7. Bayes' Theorem : 베이즈 정리

  : 각각 pairwise disjoint classes C1, ... Cn이 있고, feature set F가 있을 때, 

 

8. The pigeonhole Principle

  : n개의 pigeons가 k개의 pigeonholes로 날아들어갈 때 (k<n), 어떤 pigeonhole은 무조건 두 개 이상의 pigeons을 포함하고 있다.

 

  1) Combinatorial Identities and Combinatorial Argument

    - Combinatorial Identity : 어떤 counting process로부터 나오는 results

    - Combinatorial Argument : 그것의 formulation이 이끌어내는 argument