초간단 Permutation과 Combination이야기
확률통계를 시작할 때 제일 먼저 만나게 되는 "난관"이죠. Permutation과 Combination. Permutation은 순서를 고려하여 늘어놓는 방법, Combination은 순서를 고려하지 않고 뽑는 방법이라고 설명하는 경우가 대부분인데, 이렇게 말하게 되면 어차피 $_nP_r $이나 $_nC_r$ 공식을 모르면 풀 수가 없게 되니까. 조금 더 쉽게 원리로 다가가 볼까 합니다.
아무리 어려운 것도 원리를 깨달으면 어렵지 않다는 사실은 변치 않아요.라고 말해놓고 보니 좀 뻔뻔하군요. 일단 Permutation은 말이죠. 마련된 자리에 순서를 고려해서 늘어놓는 방법을 말합니다. 예를 들어 1~9까지 숫자들을 순서를 고려해서 늘어놓는 방법을 생각해 봅시다.
늘어놓는 자리는 9개, 그럼 첫 번째 자리에 올 수 있는 숫자는 9개, 두 번째 자리에 올 수 있는 숫자는 8개, 세 번째 자리에 올 수 있는 숫자는 7개, 네 번째 자리에 올 수 있는 숫자는 6개…… 마지막 9번째 자리에 올 수 있는 숫자는 1개겠네요.
그러면, 몇 가지 방법이 나올까 하면,
9×8×7×6×5×4×3×2×1 가지가 나오겠습니다.
그러면, 9개 숫자를 가지고, 3자리의 숫자를 만드는 방법은요?
9×8×7
이렇게 계산할 수 있겠군요.
자, 그럼 장난을 좀 쳐 볼까요?
9×8×7을 !로 표현하려면 무엇이 좋을까요.
$$ \frac{9!}{6!}$$
이렇게 표현하면 딱 맞겠군요.
홓 이걸 Permutation이라는 걸로 정의하면 어떻게 될까요.
$$ _9P_3 $$
요렇게 표현한답니다. Permutation의 정의가
$$ _nP_r = \frac{n!}{(n-r)!}$$
이런식으로 생겨먹은 이유가 n개 자리에 r개를 늘어놓는 경우의 수라고 표현하려고 하다가 보니 이렇게 생긴 거죠.
사실 편하게 생각한다면
이렇게 생각하면 굉장히 편리하답니다.
자, 이제 Combination도 살펴볼 차례입니다. 네모, 삼각형, 동그라미 3개의 도형 중 2개를 순서에 상관없이 뽑는다고 해 보자구요.
이 말은 즉, 네모, 삼각형 동그라미 3개의 도형을 2개의 자리에 일단 늘어놓는다고 생각하고 순서에 상관없게 만들어야 하니까 중복되는 것들을 없애면 된다고 생각하면 훨씬 편합니다.
결국 이 경우는
$$ \frac{3×2}{2!}$$
와 같게 됩니다. 이걸 다시 써 보면
$$ \frac{\frac{3!}{1!}}{2!} $$ 이 되고요, 이것은 $$ \frac{_3P_2}{2!} $$ 와 같은 말이 됩니다. - 3개 중 2개를 순서를 두고 늘어놓은 후에 늘어놓은 2개 자리에 대해서 늘어놓는 방법의 수 2!로 나눠주면 됩니다.
음. 그러니까, Combination이라는 건 주어진 개수만큼 뽑아서 늘어놓은 후에, 중복되는 자릿수 만큼을 나눠주면 된다! 고 생각하면 정말 편합니다.
$$ _n C_r $$
조합을 이렇게 표현하는데요, 제가 좋아하는 표현은
$$ \frac{_n P_r}{r!} $$
입니다. 다시 반복합니다. 다시 반복합니다. n개 중 r개를 순서를 고려해서 늘어놓은 후에 r개에 대한 순서를 제거. 그러니까, 결국에는 Permutation이든, Combination이든 공식을 외울 필요가 전혀 없게 되는 거죠.
사실 조합이라는 게, n개중 r 개 뽑아서 이것들을 늘어놓았는데, 순서가 없다는 의미이거든요. r개를 늘어놓는데 r!로 나누면 순서가 없어집니다.
다시 말합니다 다시 말합니다.
결국 조합이라는 것은
입니다.
이걸 아주 조금 더 복잡한 실제 예로 다시 한번 살펴보면 더 확실하게 매직아이가 보여집니다.
a,b,c,d 4개의 문자로 3글자의 단어 만드는 방법을 생각해 보시죠.
Permutation 입장에서 보면 $$_4P_3 = 4×3×2 = 24$$
으로 24가지가 있지만
abc 세 개를 뽑은 경우
abc acb bac bca cab cba (Combination의 입장에서 보면 abc 1개를 6개라고 뻥튀기 된 겁니다.)
bcd 세 개를 뽑은 경우
bcd bdc cbd cdb dbc dcb (×6 뻥튀기)
acd 세 개를 뽑은 경우
acd adc cad cda dac dca (×6 뻥튀기)
abd 세 개를 뽑은 경우
abd adb bad bda dab dba (×6 뻥튀기)
Combination의 입장에서 보면 1개를 3!개라고 뻥튀기해서 보는 것과 같습니다. 여기에서 6은 3! 인데요, 3자리에 순서를 고려하여 늘어놓는 방법이니까 그렇습니다.
따라서 24 / 3! = 4 개
Permutation으로 볼 때는 24개라고 하는 것이 Combination으로 볼 때는 4개가 됩니다.
결국 $$ \frac{_4P_3}{3!} $$ 이 되었군요.
이제 늘어놓는 방법에서 늘어놓아야 할 것 중에 같은 것이 있는 경우를 따져 볼게요.
예를 들어서, aacc를 늘어놓는 방법을 따져봐요 우리.
일단 편하게 늘어놓기 위해서
aacc를 abcd라고 생각하고 늘어놓아 볼까요?
그러면 4!개의 늘어놓는 방법이 나오겠죠?
한번 늘어놓아 봐요 우리.
abcd로 생각 → 원래 값으로 대치하면,
abcd → aacc
abdc → aacc
bacd → aacc
badc → aacc
cdab → ccaa
cdba → ccaa
dcab → ccaa
dcba → ccaa
acbd → acac
adbc → acac
bcad → acac
bdac → acac
acdb → acca
adcb → acca
bcda → acca
bdca → acca
cabd → caac
cbad → caac
dabc → caac
dbac → caac
cbda → caca
cadb → caca
dacb → caca
dbca → caca
이렇게 하고 보니,
결국 aacc, ccaa, acac, acca, caac, caca 이렇게 6가지가 나오게 되겠습니다.
중복 된 것을 고려하지 않고 늘어 놓아 보면 24가지가 나오지만, 막상 같은 것들을 제거해 보니까 총 6가지가 나오게 되는거죠.
그러니까, 지금까지 알아본 내용을 근거로 이 총 6가지는 어떻게 나오는지 확인해 보면
4!개에서 a와 c를 2개씩 같은 걸 늘어놓으니까, 순서에 상관없는 것들이 2!, 2! 두 가지가 있는 거에요.
$ \frac{4!}{2!×2!} = 3×2 = 6 $ 이렇게 나오게 되는 거에요.
이 사각형에서 나올 수 있는 사각형의 총 개수를 구해볼까요?
이럴 때 아래처럼 번호를 매겨놓고 abcde와 ①②③④두 선분에 대해서 2개를 골라서 짝을 만드는 경우라고 생각하면 굉장히 편합니다.
그러니까, (5개를 늘어 세우는데, 순서를 없애는 방법) × (4개를 늘어세우는데, 순서를 없애는 방법)이라고 생각하면 간단하겠습니다
$$ \frac{_5P_2}{2!} × \frac{_4P_2}{2!} = {_5C_2}\cdot{_4C_2} = \frac{5×4}{2!} × \frac{4×3}{2!} = 60$$ 이 되겠습니다.
Binomial Distribution을 이해하기 위해서 이 부분을 꼭 짚고 넘어가야 해서 조금 아기자기한 문제를 들여다보고 가는 거니까, 조금만 기다려주세요.
중요하니까, 다시 한번 공식을 리마인드 하면 $ _nP_r = _nC_r × r! $이고요
$$ _nC_r = \frac {_nP_r}{r!} $$
이니까 Combination은 Permutation에서 뻥튀기 된 순서를 없애주는 것이고 - 즉 순서를 무시하는 과정 -, 반대로 Permutaion은 Combination에 r개 순서를 만들어서 뻥튀기 하는 과정입니다. 이런 간단한 교훈을 기억하면 Binomial을 이해 할 때 편리할테니 마음에 넣어주세요.
친절한 데이터 사이언스 강좌 글 전체 목차 (링크) - 
댓글