순열과 조합 공식 - sun-yeolgwa johab gongsig

우리는 중학교 2학년 2학기 때 이미 '경우의 수'에 관해 공부를 했습니다. 그 때 배운 '경우의 수'가 사실 가장 기본에 충실한 '경우의 수'였고, 우리 실생활에도 적지 않게 볼 수 있는 사례들이었습니다.

한 마디로 '어떤 사건이 일어나는 경우의 가지 수'를 배웠죠. 그리고 두 사건을 함께 고려해야 하는데 그게 동시에 일어나는 경우(곱의 법칙, m×n)와 동시에 일어나지 않는 경우(합의 법칙, m+n)도 중학교 때 배웠습니다. 사실 이게 가장 중요한 것이었습니다.

그리고 지금 고등학교에 올라와서는 좀 더 복잡한 경우의 수를 배웁니다.

어떤 면에서 복잡하냐구요?

전체중에서 두 가지 이상의 사건이 일어나는 경우를 뽑는 건데..그걸 더 자세하게 파고들어가 봅니다.

뽑는 순서를 따지느냐..안따지느냐...

중복을 허락해서 뽑느냐...아니냐...

예를 들어 보죠.

자..여기 여러가지 색깔의 볼펜 5자루와 연필 3세루가 있습니다. 머릿속에 그림을 그리세요..

1) 이 중에서 필기구 한 자루를 선택할 수 있는 경우의 수는? 답) 8가지 (5+3, 합의 법칙)

2) 이 중에서 필기구 두 자루를 선택하는데..볼펜과 연필 각각 한 자루씩을 선택하는 경우의 수는?

    답)15가지(5×3, 곱의 법칙)

3) 이 중에서 필기구 두 자루를 선택하여 배열하는 경우의 수는? 답) 56가지(8×7, 순열)

4) 이 중에서 첫번째 필기구를 선택하여 사용한 후 제자리에 돌려 놓고(중복 허락) 다시 또 두번째 필기구를 선택하여 배열하는 경우의 수는? 답) 64가지(8², 중복순열)

5) 이 중에서 필기구 두 자루를 선택하여 가지는 경우의 수는? 답) 28가지((8×7)/2, 조합)

6) 이 중에서 필기구 두 자루를 선택하는데 가지는데 똑같은 필기구 두 개도 허락하는 경우의 수는? 답) 36가지((9×8)/2, 중복조합)

같은 사례를 가지고도 경우의 수에 따르는 조건에 따라 그 가지수를 헤아리는 방법이 다양하다는 것을 느끼셨습니까? 그리고 고등학교 과정에서는 뽑는 것에서 그치지 않고, 그 뽑는 순서를 따지느냐? 안따지느냐? 그리고 중복해서 뽑아도 되느냐? 안되느냐? 라는 조건이 더 추가된 것뿐입니다. 그리고 나서 파스칼의 '이항정리'라는 이론을 잠깐 소개하면서 경우의 수는 문을 닫습니다.

저번 포스팅에서 말씀드렸듯이 경우의 수를 헤아리는 것은 수학이 아니라 사회속에서 살아가야 할 인간에게 요구되는 지능에 관련된 것입니다. 이를 좀 더 수학적 기호로 단순화 시켰을 뿐이죠..

​사실 이제 막 배우는 학생들에게 가장 어려운 부분은 '개념'입니다.

경우의 수, 순열, 조합...다 아신다구요?

그럼 이 개념을 유치원 아이에게 설명해 보십시오.

정확히 개념을 안다는 것은 유치원 아이에게도 설명할 수 있을 정도로 이해가 되어 있는 상태를 의미합니다. 그렇지 않고서는 항상 어려울 수 밖에 없습니다.

만약..순열과 조합을 공부할 때 문제 풀이 시간이 너무 많이 소요된다던가...해답과 풀이 과정을 보면 쉽게 이해가 가는데 막상 스스로 풀려고 하면 막막한 느낌을 받는다면..그 학생은 아직 '순열'과 '조합'에 대한 개념을 정확히 이해하지 못한 것입니다. 마치 우리가 아무리 세상 경험이 많고 책을 많이 읽어도 누군가에게 '사회의 정의'나 '공평한 분배'에 대해 설명해 보라 하면 머뭇거리듯이 말이죠.

순열과 조합! 그 어떤 단원보다도 개념에 대한 충실한 이해가 요구되는 파트입니다.

상상 속에서 현실을 볼 줄 알아야 하는 능력?

세상을 구체적으로 짚어내가면서 그 가짓수를 헤아릴 줄 아는 능력?

이렇게 이해하면 어떻겠습니까?

순열, 순서대로 나열하는 경우의 수, 나열의 목적은 일어날 수 있는 모든 가짓수를 단 하나도 빠짐 없이 보여주기 위한 것, 앞 뒤의 순서가 틀리면 서로 다른 경우의 수, 소유보다는 존재(being)

(사과 배 귤 세 과일 중 두 개를 보여주는 경우의 수는? 6가지, 사과배, 배사과, 사과귤, 귤사과, 배귤, 귤배)

조합, 어떤 것을 묶는 경우의 수, 보여주기 위한 나열이 아닌 본격적으로 선택하는 경우의 수, 가지거나 분배하기 위한 것, 소유(have)와 관계가 깊음, 앞 뒤 순서는 틀려도 괜찮고 다만 무엇을 선택했느냐? 가 중요.

(사과 배 귤 세 과일 중 두 개를 가지는 경우의 수는? 3가지, 사과배, 사과귤, 배귤)

자..시작해봅시다.

1. 순열과 조합은 한꺼번에 연결해서 공부해야 한다.

대부분의 교과서나 참고서는 순열의 뜻, 원순열, 중복순열..이렇게 설명한 후 문제를 풀고 나서 조합으로 들어갑니다. 그래서 그런지 대부분의 학생들이 조합과 순열을 구분해서 공부하고 정리하고들 있죠..여러분들은 어떠신지?

하지만 이 방법, 매우 안좋은 방법입니다. 위의 볼펜과 연필 사례에서도 보셨듯이 순열과 조합은 물 흐르듯 개념과 공식이 유기적으로 머릿속에 잡혀 있어야 하는데..구분해서 인식되면 확률통계 첫 시작부터 어렵게 돌아가는 결과만 초래할 뿐입니다.

저는 그래서 여러분의 머릿속에 순열과 조합이라는 이름보다 이 둘을 구분짓는 기준을 먼저 집어 넣어드리고 싶습니다. '순서를 따지느냐? 안따지느냐?"

그리고 난후 문제에서 맞닥뜨리는 두번째 기준 '중복을 허락하느냐? 안하느냐?'를 집어 넣으셔야 합니다.

실전 문제에서는 이게 순열문제인지 조합문제인지 여러분 스스로 찾아야 하기 때문입니다.

어떤 경우의 수 문제를 보더라도 두 눈을 부릅뜨고 이 기준부터 적용하십시오

순서를 따지느냐? 안따지느냐?

중복을 허락하느냐? 안하느냐?

일단 공식부터 봅시다.

 (잘 보이시지 않으시면 첨부 파일을 열어 보세요)

순열과 조합에 관련된 기본적 공식들을 정리해보았습니다.

인쇄해서 앞에 놓고 관련 문제들을 푸시면 일부러 외우지 않아도 저절로 외워진답니다.

자..그럼 하나 하나 이해를 해 가면서 내 것으로 만들어 볼까요?

2. 순열과 조합의 기본 개념 이해하기

우선 !(팩토리알)의 정의부터 시작하죠..

팩토리알(!) 이란 1부터 자연수 n까지의 모든 수를 차례대로 곱하는 것을 의미합니다.

5! = 1×2×3×4×5 = 120

이런식으로 말이죠..

(순열과 조합에서는 거꾸로 내려오면서 곱하는 게 더 편하더군요)

그리고 가장 중요한 약속 하나...0! = 1

좀 납득이 안가시죠? 1! = 1인데....왜 0!을 1로 약속해야 하는 걸까요?

1!=1 인 것은 자연스럽게 이해가 가는데..0!도 1인 것은 이해가 안가는 것이 당연합니다.

아래를 보시죠

4! = 4×3×2×1  (이젠 팩토리알의 뜻을 아시죠?)

위 식에서 숫자들을 묵으면 4! = 4× (3×2×1))​ =  4×3!

즉, n! = n×(n-1)!  

여기서 n에 1을 대입하면 1! = 1×(1-1)! = 1×0!   근데 이 결과는 1이어야 하므로 결국

1×0! = 1, 따라서 0!=1이 되는 것입니다.

0!이 1이 아니라 0으로 약속한다면 ​1!와 동일한 0!×1의 값도 1이 아닌 0이 되어버리거든요.

이제 팩토리알의 개념을 바탕으로 순열과 조합 공식을 이해해 봅시다.

우선 가장 쉽게 순열과 조합의 뜻을 말하라 한다면...조합은 뽑는 것이고 순열은 뽑아서 배열하는 것?

뽑는 조합은 손에 쥐기만 하면 그 뿐 그 안의 배열은 상관 안합니다. ABC나 BCA나 다 똑같이 봅니다.

하지만 순열은 뽑은 후 그 배열의 다름도 구분하기 때문에 ABC와 BCA는 서로 다른 경우의 수로 봐야죠. 어? 그럼 가짓수가 적은 조합부터 공부하고 가짓수가 더 많은 순열을 나중에 공부하는 것이 순서 아닌가요? 아닙니다. 공식유도는 순열부터 시작됩니다. 순열 공식을 이용해서 간단한 조합 공식도 유도할 수 있습니다. 보시죠. 차근 차근.. 

위와 똑같이 서로 다른 볼펜 5가지와 연필 3가지가 있습니다.

1) 기본 순열

위 8가지 필기구 중 3가지를 선택하여 배열하는 방법의 수는?(순서 ok, 중복 불허)

(비슷한 개념 문제 : 위 8가지 필기구 중 3가지를 선택하여 3명의 학생에게 나눠주는 방법의 수는? 

                           위 8가지 필기구 중 3가지를 선택하여 진열하는 방법의 수는?)

첫번째 필기구를 고를 수 있는 선택권(옵션)의 경우의 수는 일단 8가지 입니다. 처음 선택이니깐요.

그리고 첫 번째 선택이 지나간 후 두번째 선택권의 경우의 수는 7가지 입니다. 첫번째 것이 빠지니깐요. 그러면 세번째 선택권의 경우의 수는 또 하나가 빠진 6가지가 되겠지요?

이를 모두 곱하면 8×7×6=336가지가 됩니다. n(n-1)(n-2)이지요

만약 8가지 필기구 중 4가지를 선택하라면요? 8×7×6×5,  5가지를 선택하라면 8×7×6×5×4...

뒤로 갈수록 선택권이 줄어드는군요...(그래서 줄 잘서야 합니다요..인생은...^^)

암튼..그럼 공식으로 일반화 시켜볼까요?

서로 다른 n개 중 r개를 택하여 배열하는 방법의 수는?

이를 '순열'이라고 부릅니다. 영어로는 permutation, 그리고 기호는 

말로 설명하면 쉽게 이해가 가지만 공식으로 보여주면 거부 반응이 일어나는 것은 당연합니다. 공식은 일종의 '기호'이기 때문에 그 의미를 다시 '말'로 해석해야 하는 귀찮은 두뇌 에너지를 써야 하기 때문입니다. 하지만 수학에서 평가하는 여러분의 능력중 반 이상은 이러한 공식 해석 능력입니다.

익숙하지 않은 기호들을 보면서 인류 최고의 정교함과 창의력을 가지고 놀아 보세요.

(응용 문제는 따로 내지 않겠습니다. 여러분의 일상 생활에서 보이는 대로 사례를 만들어 이 공식들을 체화시키세요..훨씬 효과가 더 큽니다.)

2) 기본 조합

사례는 위의 순열과 똑같이 서로 다른 볼펜 5자루와 연필 3자루로 가겠습니다.

위 8가지 필기구 중 3가지를 선택하는 방법의 수는?(순서 안중요, 중복 불허)

잘 보셔야 합니다. '선택하여 배열하는'이 아닌 '선택하는'입니다.

'선택하여 가지는' '고르는' 어떤 식으로 해석하든 간에 보여주기 위한 것이 아니라 실제 소유하는 개념으로 이해하셔야 합니다. 순서가 중요하지 않고 실제적으로 무엇을 선택하였는가가 중요한 것입니다.

(비슷한 개념 문제 : 위 8가지 필기구 중 3가지를 선택하여 1명의 학생에게 나눠주는 방법의 수는? 

                           위 8가지 필기구 중 3가지를 선택하여 한 세트로 구성하는 방법의 수는?)

일단 3가지를 선택하여 그 순서까지도 고려하여 배열하는 '순열'을 기본으로 구하셔야 합니다. 그 다음 '고려하지 않아도 되는 순서'의 경우의 수를 제외시켜 주면 되지요...

서로 다른 8개의 필기구 중 3개를 선택하여 늘어 놓는(순서 중요) 순열의 수는 위에서 구한 것처럼 총 336 가짓수 입니다. 이 336 가짓수에는 어떻게 3개가 구성되었든 간에 그 똑같은 3개 자체내 순서 배열의 가지숫까지도(3×2×1=6)이 고려되어 있습니다. 이걸 이제는 고려하지 않도록 처리해줘야 합니다. 어떻게 처리할까요? 필기구 3개를 늘어 놓는 방법의 수 6가지를 어떻게 처리해야 1로 만들수 있을까요? 네...맞습니다. 6으로 나눠주면 되는 것입니다. 336÷6=56

결국 조합(combination)의 수란 것은

(총 n개 중 r개를 택하는 순열의 수) ÷ (r개 자체를 배열하는 경우의 수)

로 공식을 만들면 되겠군요

 이를 '조합'이라고 부릅니다. 영어로는 combination, 그리고 기호는 nCr ..... 순서 안중요, 중복 불허임을 잊지 마세요

그리고 조합은 중요한 변형 공식이 하나 더 있답니다.

즉 8C6은 8C2와도 같다는 거죠

r이 큰수면 그냥 n-r을 선택해서 구하는 것이 더 정확하고 빠를 수 있습니다.

어렵지 않게 증명됩니다.

위 조합공식에 직접 대입해보세요

r 대신 n-r을 넣고 말이죠

같은 결과가 나올 것입니다.

자 최종적으로 정리 한 번 해 볼까요?

총 n개 중 r개를 선택하는데..그 r개를 또 늘어 놓아야 한다면 순열(순서 중요, 중복 불허), 그 r개 자체를 늘어 놓을 필요가 없다면 조합(순서 안중요, 중복 불허)

조합은 일단 순열의 수를 구한 다음 r개의 늘어 놓는 가짓수(팩토리알)로 나눠주면 됨..

자...마지막으로 조금 더 어려운 문제로 머리를 회전시킴과 동시에 기본순열과 기본조합을 완전히 내 것으로 만들어 봅시다. decision tree의 개념도 조금 맛보구요

문1) 서로 다른 볼펜 5자루 중 2자루, 서로 다른 연필 3자루 중 2자루를 선택(총 4자루)하여 배열하는 방법의 수는?

문2) 서로 다른 볼펜 5자루 중 2자루, 서로 다른 연필 3자루 중 2자루를 선택(총 4자루)하는 방법의 수는?

일단 문제 풀이부터

1번 문제의 정답은 720가지입니다. 5C2 × 3C2 × 4!  = 10 × 3 × 24 = 720

2번 문제의 정답은 30가지입니다. 5C2 × 3C2 = 10 × 3 = 30

​

<첫번째 문제가..'선택하여 배열'이란 단어 때문에 순열로 보일 수도 있지만...정확한 의미는 '일단 선택한 후...다시 배열'입니다. 모든 순열은 조합으로 식을 나타낼 수 있지요. 예를 들어 위 문제에서 서로 다른 볼펜 5자루중 2자루를 선택하여 배열하는 방법의 수만 찾아내라고 한다면..일단 이 문제는 순서를 중요시 하는 순열이지만 ...먼저 선택(​5C2)한 후에 다시 배열 2!를 곱한 것과도 같습니다.

​즉, 일단 볼펜 2자루 선택하고, 연필 2자루 선택해서 모두 4자루 모은 후...주루룩 배열하는 4!을 곱해준 것이죠>

이 문제를 왜 샘플로 선택했냐면....경우의 수나 확률을 공부함에 있어 가장 첫 출발점은 ‘또는’과 ‘그리고’의 구별이기 때문입니다. 보통 덧셈 공식, 곱셈 공식으로 설명되어 있죠.

보통 이 기초 개념을 쉽게 넘어가는 학생들이 많을텐데..절대 그러시면 안됩니다.

경우의 수나 확률 파트에서 가장 중요한 첫 번째 꼭지는 ‘또는’과 ‘그리고’의 구별이기 때문입니다. 이 개념을 잘 잡으셔야 조건부확률도 쉽게 자기 것으로 만들고, 추론 능력을 물어보는 수능형 문제도 잡을 수 있기 때문입니다. 위 문제는 매우 간단하지만 순열과 조합의 기본 개념과 두 사건이 동시에 일어나는 ‘그리고’를 얼마나 잘 이해했는가를 물어보는 좋은 사례입니다.

교과서나 참고서에서 ‘두 사건이 동시에 일어나는’이란 문장 자주 접해보셨죠? 여기서 우리는 ‘동시에’라는 단어의 함정에 빠지시면 안됩니다. ‘동시에’를 단어 그대로 해석하면 ‘같은 시간대’ ‘한꺼번에’ 등으로 이해되지만 경우의 수, 확률에서의 ‘동시에’는 시간적 요소가 아닌 ‘사건의 연결성’을 의미하기 때문입니다. 경우의 수, 확률에서의 ‘동시에’는 두 사건이 ‘연결되어 일어나는’으로 이해하셔야 합니다.

집에서 학원 가는 길을 예로 들어보겠습니다.

마을버스(3개 노선이 있음)를 타고 지하철(1개 노선이 있음)로 환승해서 가는 루트1, 일반버스(4개 노선이 있음)를 타고 20분 정도 도보(2종류의 길이 있음)로 가는 루트2이 있다고 칩시다.

첫 번째 루트인 마을버스와 지하철이란 각 사건은 서로 연결되어 있습니다. 마찬가지로 두 번째 푸트인 일반버스와 도보도 서로 연결되어 있습니다. 마을버스가 먼저고 지하철이 나중이지만 확률에서는 이 두 사건은 ‘동시에’ 일어난다고 표현합니다. 같은 시간대가 아니라 첫 번째 루트를 선택하면 마을버스와 지하철은 서로 연결되어 사건이 발생하기 사건 선택을 기준으로 ‘동시에’라고 표현하는 것입니다. 루트1의 구성요소인 마을버스와 지하철은 ‘마을버스 타고 지하철로’ 즉, 그리고(and)로 연결되어 있지요. 루트1의 방법은 마을버스(3)×지하철(1) = 3가지입니다. 루트2는 일반버스(4)×도보(2) = 8가지 이구요. 마을버스와 지하철 경우의 수는 곱셈으로 연결되어 있습니다. 루트2의 일반버스와 도보 역시 곱셈으로 연결되어 있구요.

하지만 루트1과 루트2는 서로 연결되어 있지 않은, 각각이 독립적인 사건들입니다. 루트1을 선택하면 루트2를 포기해야 하고, 루트2를 선택하면 루트1을 포기해야 합니다. 이러한 경우가 바로 ‘또는(or)’입니다. 덧셈으로 연결되어 있지요. 루트1의 3가지 방법과 루트2의 8가지 방법을 ‘또는’으로 더하면 집에서 학원으로 갈 수 있는 전체 경우의 수인 11가지 방법이 있다는 의미입니다.