수학방

조합에 대해서 공부했으니까 이번에는 조합의 활용에 대해서 공부해보죠.

순열은 뽑는 순서가 중요하고 조합은 뽑는 순서는 상관이 없어요. 활용 문제는 주관식으로 나오니까 문제를 읽고 뽑는 순서가 중요한지 중요하지 않은지를 잘 파악해야 해요. 뽑을 때 꼭 뽑아야 하는 게 있는지 뽑으면 안 되는 게 있는지도 영향을 주니까 그 부분도 주의해야 하고요.

그리고 뽑기 문제가 아닐 때도 조합을 이용해서 풀어야 하는 경우가 있어요. 이런 문제는 순열과 조합의 활용이라고 알아채기가 매우 어렵습니다. 따라서 유형을 잘 익혀두세요.

조합의 활용

한 반의 학생 수가 30명일 때 다음을 구하여라.
(1) 반장 1명, 부반장 1명을 뽑는 경우의 수를 구하여라.
(2) 주번 2명을 뽑는 경우의 수를 구하여라.

(1)번은 총 2명을 뽑는데, 한 명은 반장, 한 명은 부반장이에요. 반장과 부반장을 뽑을 때는 순서가 중요해요. 뽑히는 순서에 따라 역할이 달라지니까요. 그럼 순열로 풀어야 하죠?

30명 중에 두 명을 뽑는 거니까 ₃₀P₂ = 30 × 29 = 870(가지)

(2)번은 30명 중에서 2명을 뽑는데, 둘 다 주번이라서 역할이 같아요. 뽑히는 순서가 중요하지 않죠. 조합으로 풀어야 해요.

₃₀C₂ = 30 × 29 ÷ 2 = 435(가지)

수정이는 라면을 끓여 먹으려고 한다. 라면, 수프, 물, 떡, 달걀, 치즈, 만두, 파, 김치의 9가지 재료 중 라면, 수프, 물을 포함하여 5가지를 선택해서 라면을 끓인다고 할 때, 라면을 끓일 수 있는 경우의 수를 구하여라.

여기서 선택할 때 순서를 중요하지 않죠? 그러니까 조합을 이용해서 경우의 수를 구해야 해요.

9가지 중의 5가지를 선택해서 라면을 끓일 수 있어요. 그러니까 ₉C₅인 것 같죠?

하지만 라면, 수프, 물의 세 가지는 꼭 포함해야 해요. 그렇다면 수정이가 실제로 선택할 수 있는 건 라면, 수프, 물의 세 가지를 제외한 떡, 달걀, 치즈, 만두, 파, 김치의 6가지 중 2가지예요. 그러니까 전체 재료의 수와 선택할 수 있는 재료의 수 모두에서 3을 빼줘야 해요.

₉C₅ → _{9 - 3}C_{5 - 3} = ₆C₂

위 식의 -3에서 3은 라면, 수프, 물을 의미해요.

(가지)

부분집합의 개수 구하기에서 특정한 원소 k개를 반드시 포함하는 부분집합의 개수를 구했어요. 이때 특정한 원소 k개를 제외한 원소를 이용해서 부분집합을 구하고 그 특정한 원소를 부분집합에 넣어주는 방법을 이용했었죠? 즉, (특정한 원소 k개를 반드시 포함하는 부분집합의 개수 ) = (특정한 원소 k개를 포함하지 않는 부분집합의 개수 )라는 거죠.

여기서도 같아요. 어떤 항목을 반드시 포함되어야 할 때는 그 항목을 뺀 그 나머지를 이용해서 경우의 수를 구하는 거죠. (특정한 항목을 반드시 포함하는 경우의 수) = (특정한 항목을 제외한 경우의 수)예요.

수정이는 라면을 끓여 먹으려고 한다. 라면, 수프, 물, 떡, 달걀, 치즈, 만두, 파, 김치의 9가지 재료 중 라면, 수프, 물을 포함하여 5가지를 선택해서 라면을 끓인다고 할 때, 라면을 끓일 수 있는 경우의 수를 구하여라. (단, 달걀과 치즈 중 적어도 하나는 넣어야 한다.)

문제를 살짝 바꿨어요. 나머지는 다 똑같고 달걀과 치즈 중 적어도 하나는 넣어야 해요. 달걀과 치즈 둘 다를 넣어도 되고, 달걀만 넣거나 치즈만 넣어도 괜찮아요.

이런 문제도 부분집합의 개수 구하기에서 했어요. 특정한 원소 k개 중 적어도 한 개를 포함하는 부분집합의 개수를 구하는 거였죠. 이때는 (전체 부분집합의 개수) - (특정한 원소 k개를 포함하지 않는 부분집합의 개수)를 이용해서 구했어요.

치즈도 없고 달걀도 없는 조리 방법의 수는 처음부터 라면과 치즈가 선택 목록에 없었다고 생각하면 쉽게 구할 수 있어요. 떡, 만두, 파, 김치의 4가지 중에서 2가지를 선택하는 방법의 수와 같죠.

그리고 전체 라면 조리법 수에서 달걀과 치즈가 둘 다 없는 라면 조리법 수를 빼면 둘 중 적어도 하나를 포함하는 조리법 수를 구할 수 있어요.

전체 라면의 조리 방법 개수는 위에서 구한 것처럼 _{9 - 3}C_{5 - 3} = ₆C₂ = 15
치즈도 없고 달걀도 없는 라면의 조리 방법 수 = _{6 - 2}C₂ = ₄C₂ = 6

라면, 수프, 물은 반드시 포함하고 치즈와 달걀 중 적어도 하나는 포함하는 라며 조립법 수 = 15 - 6 = 9

전체 n가지 중 r가지를 선택할 때
p가지를 반드시 포함해야 하는 경우의 수 = _{n - p}C_{r - p}
p가지 중 적어도 하나를 포함해야 하는 경우의 수 = (전체 경우의 수) - (p가지를 포함하지 않는 경우의 수) = _nC_r - _{n - p}C_r

다음 그림에서 사각형의 총 개수를 구하여라.

보통 이런 형태의 문제는 어떻게 풀었나요?

사각형 1개짜리: (3 × 4) = 12
사각형 2개짜리: (2 × 4) + (3 × 3) = 17
사각형 3개짜리: (1 × 4) + (2 × 3) = 10
사각형 4개짜리: (2 × 3) + (1 × 3) = 9
사각형 6개짜리: (1 × 3) + (2 × 2) = 7
사각형 8개짜리: 2
사각형 9개짜리: 2
사각형 12개짜리: 1

12 + 17 + 10 + 9 + 7 + 2 + 2 + 1 = 60(개)

다른 방법으로 한 번 풀어보죠.

사각형에서 각 선분에 이름을 붙여봤어요. 가로줄은 a, b, c, d, e, 세로줄은 ①, ②, ③, ④

a, b와 ①, ②가 있으면 사각형을 한 개 만들 수 있어요. 또, a, b와 ①, ③이 있으면 사각형을 만들 수 있고요. 이런 식으로 가로줄 2개와 세로줄 2개가 있으면 사각형을 만들 수 있어요.

가로줄은 총 5개가 있는데 그중 2개를 선택할 수 있죠. 세로줄은 총 4개가 있는데 그중 2개를 선택하고요. 가로줄과 세로줄에서 모두 2개씩을 골라야 하니까 곱의 법칙을 이용해야겠네요.

₅C₂ × ₄C₂ = 10 × 6 = 60

조합을 이용하니까 더 쉽게 풀 수 있죠?

일직선 위에 있지 않은 서로 다른 n개의 점에서 두 점을 잇는 직선의 개수 = _nC₂
일직선 위에 있지 않은 서로 다른 n개의 점에서 세 점을 잇는 삼각형의 개수 = _nC₃
가로 m개의 선과 세로 n개의 선이 만나서 생기는 사각형의 개수 = _mC₂ × _nC₂

직선은 서로 다른 두 점을 연결하면 생겨요. 따라서 두 점의 개수를 구하는 방법과 직선의 개수는 같아요. 삼각형은 서로 다른 세 점을 연결하면 생기니까 세 점의 개수를 구하는 방법의 개수와 삼각형의 개수가 같고요. 마지막 사각형의 개수는 위 예제에서 했던 거예요.

함께 보면 좋은 글

순열과 조합 - 조합이란
순열과 조합 - 조합의 성질
순열과 조합 - 순열이란
순열과 조합 - 순열2. 팩토리얼(factorial), 계승

순열과 조합의 차이에 대해서 이해했나요? 순열과 조합은 둘 다 서로 다른 n개에서 r개를 고르는 경우의 수를 말해요. 순열은 r개를 택할 때 순서대로 택하는 거고, 조합은 순서와 관계없이 그냥 택하는 거죠.

이 글에서는 조합에서 고르는 개수가 특수한 경우 즉, r = n일 때와 r = 0일 때의 값을 구해볼 거예요. 그리고 조합을 나타내는 식 _nC_r을 다른 식으로 표현해볼 거고요.

약간의 증명과 유도가 필요하니까 잘 보세요.

순열과 조합 - 조합의 성질

순열과 조합 - 조합이란에서 이었어요. 모양을 한 번 바꿔볼까요?

세 개의 계승을 이용해서 _nC_r을 표현할 수 있어요.

r = n일 때는 어떻게 되는지 한 번 보죠.

팩토리얼(factorial), 계승에서 0! = 1 이었어요.

_nC_n = 1인 걸 알 수 있네요.

이번에는 r = 0일 때를 보죠.

_nC₀ = 1로 정의할 수 있어요.

서로 다른 n개에서 r개를 고르는 조합의 수는
 (단, 0 ≤ r ≤ n)
_nC_n = _nC₀ = 1

그리고 아래 네 가지는 헷갈릴 수 있으니까 따로 정리하죠.

_nP_n = n!
_nP₀ = 1
_nC_n = 1
_nC₀ = 1

함께 보면 좋은 글

순열과 조합 - 조합이란
순열과 조합 - 순열이란
순열과 조합 - 순열2. 팩토리얼(factorial), 계승
합의 법칙, 곱의 법칙

순열에 이어 조합이에요. 조합과 순열은 너무 비슷해서 구분하기 어려워요. 정확히 말하면 문제를 푸는 식이 특별히 어려운 게 아닌데 서술형으로 된 문제를 읽고 순열로 풀어야 하는지 조합으로 풀어야 하는지 결정하기가 어렵죠.

교과서에 나와 있는 여러 문제를 잘 읽어보고 순열과 조합을 구별할 수 있도록 유형을 잘 익혀두세요.

이 글에서는 조합의 뜻과 표현법을 알아보고 순열과의 관계를 이용해서 조합을 구하는 방법도 알아보죠.

조합이란

보통 가수들의 음반은 트랙 번호라고 해서 1번부터 노래가 순서대로 번호가 매겨져 있어요.

그룹 f(x)가 새로운 음반을 발매하려고 한다고 치죠. a부터 j까지 총 10곡의 노래가 있는데 이 중 5곡을 앨범에 넣으려고 해요. 몇 가지 경우의 수가 나오는지 계산해보죠.

이 과정을 두 단계로 나눠서 생각해볼까요? 앨범에 넣을 노래 다섯 곡을 고르는 단계와 이 다섯 곡의 노래들을 앨범에 넣을 때 앨범에 실을 순서를 결정하는 단계요.

먼저 1단계로 앨범에 넣은 다섯 곡을 결정하는 단계예요. 10곡 중에서 5곡을 고르는 경우의 수는 몇 가지가 있을까요?

1. 10곡 중에서 한 곡을 고르는 경우의 수: 10
2. ①에서 고른 한 곡을 뺀 나머지 9곡 중에서 한 곡을 고르는 경우의 수: 9
3. ①, ②에서 고른 2곡을 뺀 나머지 8곡 중에서 한 곡을 고르는 경우의 수: 8
4. ①, ②, ③에서 고른 3곡을 뺀 나머지 7곡 중에서 한 곡을 고르는 경우의 수: 7
5. ①, ②, ③, ④에서 고른 4곡을 뺀 나머지 6곡 중에서 한 곡을 고르는 경우의 수: 6

①, ②, ③, ④, ⑤의 과정은 동시에 연달아서 일어나는 사건이므로 곱의 법칙을 이용해야겠지요?

10 × 9 × 8 × 7 × 6

그런데, 여기서 주의해야 할 게 있어요. ①에서 a, ②에서 b, ③에서 c, ④에서 d, ⑤에서 e라는 곡을 골랐을 때와 ①에서 b, ②에서 c, ③에서 d, ④에서 e, ⑤에서 a를 골랐을 때 차이가 있나요? 곡이 뽑힌 순서는 다르지만 두 경우 모두 a, b, c, d, e라는 다섯 곡을 뽑은 결과는 같지요? 두 경우가 서로 같으니까 단순히 10 × 9 × 8 × 7 × 6으로 경우의 수를 구할 수 없어요.

1단계는 10곡 중에서 5곡을 고르기만 했어요. 어떤 곡을 먼저 고르고 나중에 고르고는 아무런 상관이 없지요. 이처럼 서로 다른 n개에서 순서와 상관없이 r개를 고르는 걸 조합이라고 해요. 순열과 달리 조합에서는 순서가 중요하지 않아요. 그냥 r개를 고르기만 하면 돼요.

n개에서 r개를 고르는 조합은 영어단어 Combination의 첫 글자 C를 따서 _nC_r이라고 나타내고 엔씨알이라고 읽어요.

이 경우에는 ₁₀C₅가 되겠죠.

1단계로 5곡을 다 정했어요.

이제 2단계로 앨범에 넣을 순서 즉, 트랙 번호를 정해야 해요. 트랙 번호를 매기는 건 순서대로 해야 하죠? 1단계에서 뽑은 5곡에서 한 곡씩 모두 뽑아서 순서를 매기는 거니까 이때의 경우의 수는 순열이에요. ₅P₅ = 5!

이번에는 1, 2단계를 하나의 과정으로 생각해보죠. 결과적으로는 10개의 노래 중에서 앨범에 넣을 5곡을 순서대로 뽑아서 트랙 번호를 정하는 거예요. 순열이죠? ₁₀P₅에요.

1, 2단계는 동시에 연달아서 일어나는 사건이므로 곱의 법칙을 이용해서 경우의 수를 구할 수 있어요. 그런데 이 경우의 수는 1, 2단계를 한 과정으로 본 ₁₀P₅로 구한 경우의 수와 같죠.

계산 결과가 중요한 건 아니니까 결과를 구하지는 않을게요. 모양을 잘 보세요. n = 10, r = 5인 순열과 조합의 관계를 알 수 있죠?

이걸 n과 r을 사용해서 일반적인 순열과 조합의 관계로 나타내보죠.

여기서 r은 개수에요. 그러니까 당연히 0보다 커야겠죠? 그리고 n개 중에서 뽑는 거니까 n보다 클 수는 없어요. n보다 작거나 같지요. 0 < r ≤ n

서로 다른 n개에서 r개를 순서와 상관없이 고르는 조합의 수는

(단, 0 < r ≤ n)

조합은 순열과 팩토리얼을 이용해서 표현할 수 있겠죠? 식으로 한 번, 말로 한 번 풀어서 써보면 다음 그림처럼 나타낼 수 있어요.

조합을 구하는 방법을 조금 더 쉽게 알 수 있겠죠?

함께 보면 좋은 글

순열과 조합 - 순열이란
순열과 조합 - 순열2. 팩토리얼(factorial), 계승
합의 법칙, 곱의 법칙
경우의 수 공식 - 대표 뽑기

순열과 조합은 경우의 수 공식 - 대표 뽑기에서 했던 건데 조금 더 자세히 알아볼게요. 순열과 조합은 조금 어려운 내용이라서 공부하기 힘들 거예요. 계산 자체가 어렵다기보다는 순열인지 조합인지 판단하기가 상당히 모호해요. 잘 구별해야 합니다.

어렵긴 하지만 양이 많지는 않으니까 금방 지나가요. 순열은 순서가 중요하고 조합은 순서가 중요하지 않다는 차이만 확실히 이해하시면 돼요.

순열

1부터 5까지 적힌 카드가 한 장씩 있다고 해보죠. 이 중 세 장을 뽑아서 세 자리 숫자를 만드는 방법의 경우의 수를 구해볼까요?

1. 백의 자리 카드를 뽑을 때는 1 ~ 5중 한 장을 뽑을 수 있어요. 총 다섯 가지
2. 십의 자리 카드를 뽑을 때는 ① 뽑은 카드를 제외한 네 장중 하나를 뽑을 수 있어요. 네 가지
3. 일의 자리 카드를 뽑을 때는 ①, ②에서 뽑은 카드를 제외한 세 장중에서 하나를 뽑을 수 있어요. 세 가지

연달아 일어나는 사건이므로 곱의 법칙을 이용하면 다섯 장의 카드 중 세 장의 카드를 뽑아서 숫자를 만드는 방법은 5 × 4 × 3 = 60가지예요.

위 예에서 카드를 뽑아서 순서대로 놓았죠? 바로 이런 걸 순열이라고 해요. 이름 그대로 순서대로 뽑아서 줄을 세우는 걸 순열이라고 하지요.

순열을 기호로 나타낼 때는 순열을 뜻하는 영어 Permutation의 첫 글자 P를 이용해요. n개 중에서 r개를 뽑아서 줄을 세우는 걸 _nP_r이라고 합니다. 엔피알이라고 읽으세요. P는 대문자로 쓰고 n과 r은 소문자로 쓰는데 크기를 조금 작게 써요.

총 다섯 장의 카드 중에서 세 장을 뽑는 건 ₅P₃이라고 쓰고 오피삼이라고 읽는 거죠.

n가지 중에서 r개를 뽑아 줄을 세우는 경우를 볼까요?

1. 첫 번째로 뽑을 때는 n개 중 한 개를 뽑을 수 있어요. n가지
2. 두 번째로 뽑을 때는 ①에서 뽑은 한 개를 제외한 (n - 1) 개중 하나를 뽑을 수 있어요. (n - 1)가지
3. 세 번째로 뽑을 때는 ①, ②에서 뽑은 걸 제외한 (n - 2) 개중에서 하나를 뽑을 수 있어요. (n - 2) 가지

그럼 r번째로 뽑을 때는 어떨까요? r번째로 뽑을 때는 ①, ②, …, (r - 1)에서 뽑은 걸 제외한 n - (r - 1)개 중에서 하나를 뽑을 수 있어요. n - (r - 1)가지가 되지요.

여기서 r은 개수에요. 그러니까 당연히 0보다 커야겠죠? 그리고 n개 중에서 뽑는 거니까 n보다 클 수는 없어요. n보다 작거나 같지요. 0 < r ≤ n

서로 다른 n개에서 r개를 순서대로 고르는 순열의 수는

(단, 0 < r ≤ n)

_nP_r은 n부터 1씩 줄여가면서 r개의 숫자를 곱해서 구할 수 있어요.

_{(n + 1)}P₃ = 24을 만족하는 n을 구하여라.

_{(n + 1)}P₃ = 24
(n + 1)n(n - 1) = 24
n(n² - 1) = 24
n³ - n - 24 = 0

n에 관한 삼차방정식에요. 조립제법을 이용해서 해를 구해보면 n = 3이 나오네요.

무한도전 일곱 멤버(박명수, 정준하, 유재석, 정형돈, 길, 노홍철, 하하)의 자리 배치를 다시 하려고 한다. 유재석이 가운데인 네 번째 자리에 오도록 자리를 배치할 때 경우의 수를 구하여라.

유재석이 네 번째에 고정되어야 하는군요.

부분집합의 개수를 구할 때 특정 원소를 포함하는 부분집합의 개수를 어떻게 구했나요? 그 원소를 뺀 나머지 원소들의 부분집합을 구한 다음에 거기에 특정 원소를 집어넣으면 되는 거였어요. 즉, 특정 원소를 포함한 부분집합의 개수 = 특정 원소를 포함하지 않는 부분집합의 개수였었죠?

마찬가지로 유재석을 뺀 나머지 여섯 명의 자리 배치를 한 후에 네 번째 자리에 유재석을 끼워 넣고 나머지를 한 자리씩 뒤로 미루면 돼요. 유재석이 없을 때의 경우의 수와 같다는 거지요.

유재석을 뺀 나머지 6명의 자리 배치를 해볼까요? 6명 중에서 6명을 모두 뽑아야 해요. 뽑고 싶지 않은 멤버가 있어도 하차시키지 말고 다 뽑아야 해요.

6명의 멤버 중 6명을 순서대로 뽑아서 줄을 세우는 거니까 ₆P₆이네요. 6부터 1씩 줄이면서 6개의 숫자를 곱하는 거지요.

₆P₆ = 6 × 5 × 4 × 3 × 2 × 1 = 720

720가지 방법이 있군요. 자리분양 특집 한 번 더 해야겠어요.

함께 보면 좋은 글

합의 법칙, 곱의 법칙
경우의 수 공식 - 대표 뽑기
경우의 수 공식 - 한 줄 세우기
경우의 수, 합의 법칙, 곱의 법칙