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

(2017-04-04)

Combination Theory, 조합론, 조합 [Combination]

기초과학 1. 과학

수학
물리/화학
지구,천체 과학
생명과학
 > 수학기초수학
집합,논리
정수론(수론)
해석학(미적분 등)
대수학
확률/통계
수치해법
 > 정수론(수론) 1. 정수론
2. 절대값
3. 짝수,홀수,패리티

수의 구분
셈법(Counting)
나눗셈(가분성)
디오판투스 방정식
소수,최대공약수
합동
 > 셈법(Counting) 1. 셈법
2. 순열,조합
3. 이항/다항 정리
4. 비둘기집 원리

     
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. 비둘기집 원리  

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