Permutation, Ordered Sequence, Combination   순열, 조합 (Combination)

(2017-04-04)

Combination Theory, 조합론, 조합

1. 조합 론 (Combination Theory, Combinatrics)

  ㅇ 대상이되는 요소들의 배열에 대해 연구하는 수학의 한 분야
     - 이산적 구조(특정한 패턴 배열 등)의 존재성, 셈법, 최적화 문제(최적 배열) 등
        . 특히, 특정 배열/사건/사물들의 수를 셈하는 문제(Counting,셈법)가 매우 중요함


2. 순열 또는 치환 (Permutation,Ordered Sequence)

  ㅇ 순서를 바꿔보는 것
     - 전체 또는 일부의 순서적 배열(arrangement) 또는 재배열(rearrangement)하는 것
     - 어떤 집합 중 일부를 택하여 순서있게 나열하는 것

  ※ 例)  S = {1,2,3}에서 3개를 뽑아 나열(재배열)하는 모든 순열 방법의 경우의 수는?
     - 123을 기준으로 보면, 경우의 수는 총 6번 = 3P3
        . ① 123 : 자리바꿈 0번 (우순열)
        . ② 132 → 123 : 자리바꿈 1번 (기순열)
        . ③ 213 → 123 : 자리바꿈 1번 (기순열)
        . ④ 231 → 213 → 123 : 자리바꿈 2번 (우순열)
        . ⑤ 312 → 132 → 123 : 자리바꿈 2번 (우순열)
        . ⑥ 321 → 231 → 213 → 123 : 자리바꿈 3번 (기순열)


3. 순열 셈하는 종류

  ㅇ 비중복 순열 (sampling without replacement)
    
     - (전체 순열)
        . 서로다른 n개를 순서있게 배열하는 경우의 수 : n!

     - (일부 순열)
        . 서로다른 n개 중 r개를 취하여 순서있게 배열하는 경우의 수 : nPr
          

     - (원 순열, circular permutation)
        . 서로다른 n개를 원형으로 순서있게 배열하는 경우의 수 : (n-1)!
 
     - (유사 순열)
        . 서로다른 n개 중 p개가 같다면, 이때 순서있게 늘여놓는 경우의 수 : n!/p!

     - (그룹 순열)
        . 서로다른 n개를 n1,n2,...,nk개의 그룹으로 순서있게 배열하는 경우의 수
          
        . 例) 11개 문자(a가 5개,b가 2개,c가 2개,d가 1개,f가 1개)로 나열 가능한 방법 수 :
           .. (11!)/(5! 2! 2! 1! 1!) = 83160

  ㅇ 중복 순열 (sampling with replacement) 
     - 중복을 허용하여 나열하는 경우의 수 
        . m개 중 중복을 허용하며 n개를 뽑아 나열하는 경우의 수  :  mn
        . 例) 알파벳으로 2개 문자를 만들 수 있는 단어 수는, 262 = 676


4. 분할 (Partition)

  ㅇ 서로다른 n개 집합을 r개의 부분집합으로 분할하는 경우의 수
     


5. 조합 (Combination)

  ㅇ 유한개의 서로 다른 원소를 갖는 집합에서 일부를 선택하여 부분집합을 만드는 것
     - 서로다른 n개의 물건에서 k개를 뽑는 경우의 수 (k-조합,k-combination)

     
        . 은 일명 이항계수라고도 함


[셈법(Counting)] 1. 셈법 2. 순열,조합 3. 이항/다항 정리 4. 비둘기집 원리
  1.   기술공통
  2.   기초과학
        1. 과학
    1.   수학
      1.   기초수학
      2.   집합,논리
      3.   정수론(수론)
            1. 정수론
            2. 절대값
            3. 짝수,홀수,패리티
        1.   수의 구분
        2.   셈법(Counting)
          1.   1. 셈법
              2. 순열,조합
              3. 이항/다항 정리
              4. 비둘기집 원리
        3.   나눗셈(가분성)
        4.   디오판투스 방정식
        5.   소수,최대공약수
        6.   합동
      4.   해석학(미적분 등)
      5.   대수학
      6.   확률/통계
      7.   수치해법
    2.   물리/화학
    3.   지구,천체 과학
    4.   생명과학
  3.   파동/광학/음향
  4.   방송/멀티미디어/정보이론
  5.   전자/전기/제어
  6.   통신/네트워킹
  7.   정보기술(IT)
  8.   기계/재료/공업일반
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     모바일웹     참고문헌