Combinatorial Analysis - (1) (수를 세는 원리와 순열)
수를 세는 원리
우리가 수를 셀 때 어떻게 세는지 설명할 수 있는가?
3명의 엄마가 있고 그 엄마 들은 각 3명의 자식들을 가진다. 이 중에서 엄마와 자식 한명씩 선택한다면 총 몇개의 그룹이 생기는가?
그렇다 답은 9명이다.
우리는 이미 직관적으로 3*3 = 9 라는것을 알고있다.
이 식을 일반화 해보면 case 1이 m개 이 m개의 case에 각각 관계된 case 2가 n개라면 이 두가지 case에서 얻을 수 있는 가능한 결과는 총 mn개이다.
우리가 수를 셀 때는 이런식으로 세고 있었던 것이다.
순열
다음은 순열에 대해 알아보자
순열은 서로 다른순서로 정렬하는 방법의 수라는 의미를 가졌다. 만약 우리가 n개의 물체가 있다면 n개의 물체를 정렬하는 순열은 아래와 같다.
이런식으로 나타낼 수 있다.
예시를 통해 더 자세히 알아보자,
동도리네 반은 7명의 남자와 3명의 여자 학생들로 구성되어 있다. 모의고사를 치룬 후 점수에 따라 등수를 나눴고, 이때 동점자는 없다고 가정 하자.
(a). 서로 다른 순위의 종류는 몇개 인가?
(b). 만약 성별 안에서 순위를 정한다면 몇개의 순위의 종류가 가능한가?
우선 (a)부터 확인해 보자면, 서로 다른 순위의 종류 라 함은 서로 다른순서로 정렬하는 종류 라 할 수 있고, 이는 곧 순열이다. 따라서 총 10명의 대한 순열은 10! = 3628800이다.
다음으로 (b)를 살펴보자면 성별끼리 순위를 정한다면 몇개가 가능할까? 그렇다 우린 이미 직관적으로 답을 알고있다. 위에서 수를 세는 방식에 따라 남자의 순열 여자의 순열을 구해 서로 곱해주면 된다. 그렇게 해주면 답은 7! * 3! = 5046 이 된다.
같은 종류로 묶을 수 있는 것들의 순열
마지막으로 같은 종류로 묶일 수 있는 순열에 대해 설명하겠다.
일반적으로, n개의 물체 중에, n1개가 서로 같고, n2개가 서로 같고,...nr개가 서로 같은 종류로 묶일 수 있다면, 순열은 다음과 같이 계산할 수 있다.
예제를 통해 더 자세히 알아보자,
cactus이라는 단어의 글자를 각 문자로 분류하여 정렬한다면 몇 개의 다른 글자를 만들 수 있을까?
cactus는 c가 2개 a가 1개 t가 1개 u가 1개 s가 1개씩있다. 그렇다면 같은 걸로 묶을 수 있는건 c가있고, 이 문자의 글자수는 총 6개 이므로 6!/2!*1!*1!*1!*1! = 360 이 된다.
다음시간엔 조합에 대해서 배우겠다.