* 순열
순열이란
서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게선택하는 혹은 나열하는 것을 '순열(permutation)' 이라고 한다.
예시로 카드를 고르는 상황이 나와있다.
첫번째에서 A,B,C,D,E 중 하나를 고르고 두번째에선 고른 카드를 뺀 나머지를 다시 선택할 수 있을 것이다.
이 상황에서 경우의 수를 구해보면 첫번째 상황은 5 가지의 경우의 수, 두 번째 상황은 4가지의 경우의 수....
결과로써 5 * 4 * 3 * 2 * 1 = 5! ( factorial ) 이 구해진다.
한 단계 더 나아가서 A,B,C,D,E 5장 카드를 모두 고르는 것이 아닌 2장의 카드만 고른다면
경우의수는 5*4 = 20 이 될 것이다.
카드의 개수를 n, 고르는 카드 개수를 r 로 놓고 위 내용을 식으로 전개하면
n! / ( n - r )!
5! / ( 5 - 3 ) ! = 5 * 4 = 20 으로 도출된다.
이를 순열에서는 5P2라고 표현한다.
* 조합
조합은 순열의 개념에서 약간의 개념이 추가되는 부분이 존재한다.
바로 뽑은 결과의 순서를 상관하지 않는다는 것이다. 어떤 순서로 원소를 선택했는지 중요하지 않다.
즉, 조합이란
서로 다른 n 개의 원소에서 순서에 상관없이 r 개를 뽑는 경우의 수를 말하며 '조합 ( Combination )' 이라고 부른다.
위 카드 예시에 덧붙여 설명하면,
서로 다른 A,B,C,D,E 5장 카드에서 2장의 카드가 순서에 상관없이 뽑을 때의 경우의 수는
5P2 / 2! = 10 이 되겠다.
이는 A,B 를 선택한 것과 B,A 를 선택한 것을 같은 경우의수로 취급하기 때문이다.
위를 식으로 표현하면
n! / ( n - r )! * r!
순열 식에서 r! 를 나누어주는 식이 도출된다.
이를 조합에서는 5C2 라고 표현된다.
결국,
순열과 조합의 차이점은 '순서의 상관 여부' 이다.
순열과 조합의 대표적 예시를 살펴보자.
1. 5장의 카드 중 3장의 카드를 골라 만들 수 있는 세 자리수의 경우의 수는 ??
=> 5P3
2. 3명 중 대표 2명을 뽑는 경우의 수는 몇일까??
=> 3P2 / 2! = 3C2
일반적인 순열 개념과 조합 개념은 많이 접하기도 했고 이해하기 어렵진 않았다.
조금 더 나아가서 이를 활용해 알아볼 수 있는 중복 순열과 중복 조합에 대해서 알아보자.
* 중복 순열
먼저 중복 순열은 말 그대로 순열에서 중복을 허락하는 것이다.
일반적으로 카드를 고르거나 의자에 앉은 행위는 카드나 의자가 선택되어지므로
경우의 수들이 하나씩 줄어들면서 계산되어졌지만
이와 다르게 중복 순열은 철수가 1번 의자와 2번 의자 동시에 앉거나 1번 카드를 계속해서 고를 수 있다는 전재가 바탕된다.
간단히 나오는 예시로
중복을 허락해 네 개의 숫자 1,2,3,4 를 써 세 자리 자연수를 만드는 경우의 수를 구할 때,
4 * 4 * 4 = 64 가지로 해당 상황마다 1,2,3,4 를 선택할 수 있는 모든 경우가 살아있다.
* 중복조합
중복 순열과 비슷하게 조합을 확장한 개념인데
중복 조합은 서로 다른 n 개에서 중복을 허락해서 r 개를 뽑는 경우의 수를 말한다.
즉,
앞서본 중복 순열처럼 중복해서 해당 원소를 뽑을 수 있으며 뽑은 이후의 결과에서 순서는 상관없다.
원리를 알기 전 식을 먼저 살펴보자.
nHr = n + r - 1 C r
우리는 이 식을 파헤치기 위해서 흔히 중복 조합에서 증명되는 '칸막이 이론' 을 사용할 것이다.
갑자기 뜬금없이 칸막이란 말이 나와서 의아하지만 이런 개념이 필요한 이유는
다른 시각으로 바라보기 위함이며 그 시각에서 우리가 구하고자 하는 것과 같은 원리가 적용되기 때문이다.
여기서 칸막이는 원소를 선택할 수 있는 하나의 자리로써 인식된다.
3개의 중복될 수 있는 원소에서 5개를 선택하는 경우의 수 3H5 에 관한 예시를 보자.
그림에서 예측될 수 있는 것은 칸막이는 중복될 수 있는 원소를 나누는 경계선이다.
원소 5개를 선택하는 상황에서 중간에 칸막이를 넣음으로써 우리는
칸막이로 구분되는 원소들의 순서도 상관할 필요가 없기 때문에
첫번째 칸막이의 왼쪽은 A, 첫번째 두번째 칸막이의 사이는 B, 두번째 칸막이 오른쪽은 C 라고 여길 수 있다.
이 시점에서 다른 시각으로 이 상황을 바라보도록 하자.
이것은 굉장히 재밌게도 칸막이를 어디에 놓은 것인지와 같은 과정이 된다.
3개의 중복된 원소에서 5개의 원소를 뽑을 때 칸막이가 들어갈 수 있는 자리는
칸막이 개수 + 뽑을 원소 개수가 된다.
따라서,
경우의 수는 7P2 가 되고 칸막이 2개는 순서가 상관없으니 2! 로 나누게 되면 결과적으로 7C2 라는 값에 도출한다.
시점이 약간 바뀌어진 7C5 의 경우도
총 7자리에 같은 원소 5개를 넣는 경우의 수와 같다. 결국 7P5 / 5! = 7C5 가 된다.
같은 원소가 되는 이유는 어차피 7자리에 5개를 넣게 되면 비어있는 자리로 해당 원소를 구분하기 때문이다.
따라서 최종적으로,
n+r-1Cr
3H5 = 3 - 1 ( 칸막이 개수 ) + 5 C (3 - 1) = 7C2 = 7C5 가 되겠다.
참고 자료
'수학 > 개념 정리' 카테고리의 다른 글
| [Math]이항 정리 (0) | 2023.01.08 |
|---|