순열과 조합 - 조합의 활용
조합에 대해서 공부했으니까 이번에는 조합의 활용에 대해서 공부해보죠.
순열은 뽑는 순서가 중요하고 조합은 뽑는 순서는 상관이 없어요. 활용 문제는 주관식으로 나오니까 문제를 읽고 뽑는 순서가 중요한지 중요하지 않은지를 잘 파악해야 해요. 뽑을 때 꼭 뽑아야 하는 게 있는지 뽑으면 안 되는 게 있는지도 영향을 주니까 그 부분도 주의해야 하고요.
그리고 뽑기 문제가 아닐 때도 조합을 이용해서 풀어야 하는 경우가 있어요. 이런 문제는 순열과 조합의 활용이라고 알아채기가 매우 어렵습니다. 따라서 유형을 잘 익혀두세요.
조합의 활용
한 반의 학생 수가 30명일 때 다음을 구하여라.
(1) 반장 1명, 부반장 1명을 뽑는 경우의 수를 구하여라.
(2) 주번 2명을 뽑는 경우의 수를 구하여라.
(1)번은 총 2명을 뽑는데, 한 명은 반장, 한 명은 부반장이에요. 반장과 부반장을 뽑을 때는 순서가 중요해요. 뽑히는 순서에 따라 역할이 달라지니까요. 그럼 순열로 풀어야 하죠?
30명 중에 두 명을 뽑는 거니까 30P2 = 30 × 29 = 870(가지)
(2)번은 30명 중에서 2명을 뽑는데, 둘 다 주번이라서 역할이 같아요. 뽑히는 순서가 중요하지 않죠. 조합으로 풀어야 해요.
30C2 = 30 × 29 ÷ 2 = 435(가지)
수정이는 라면을 끓여 먹으려고 한다. 라면, 수프, 물, 떡, 달걀, 치즈, 만두, 파, 김치의 9가지 재료 중 라면, 수프, 물을 포함하여 5가지를 선택해서 라면을 끓인다고 할 때, 라면을 끓일 수 있는 경우의 수를 구하여라.
여기서 선택할 때 순서를 중요하지 않죠? 그러니까 조합을 이용해서 경우의 수를 구해야 해요.
9가지 중의 5가지를 선택해서 라면을 끓일 수 있어요. 그러니까 9C5인 것 같죠?
하지만 라면, 수프, 물의 세 가지는 꼭 포함해야 해요. 그렇다면 수정이가 실제로 선택할 수 있는 건 라면, 수프, 물의 세 가지를 제외한 떡, 달걀, 치즈, 만두, 파, 김치의 6가지 중 2가지예요. 그러니까 전체 재료의 수와 선택할 수 있는 재료의 수 모두에서 3을 빼줘야 해요.
9C5 → 9 - 3C5 - 3 = 6C2
위 식의 -3에서 3은 라면, 수프, 물을 의미해요.
부분집합의 개수 구하기에서 특정한 원소 k개를 반드시 포함하는 부분집합의 개수를 구했어요. 이때 특정한 원소 k개를 제외한 원소를 이용해서 부분집합을 구하고 그 특정한 원소를 부분집합에 넣어주는 방법을 이용했었죠? 즉, (특정한 원소 k개를 반드시 포함하는 부분집합의 개수 ) = (특정한 원소 k개를 포함하지 않는 부분집합의 개수 )라는 거죠.
여기서도 같아요. 어떤 항목을 반드시 포함되어야 할 때는 그 항목을 뺀 그 나머지를 이용해서 경우의 수를 구하는 거죠. (특정한 항목을 반드시 포함하는 경우의 수) = (특정한 항목을 제외한 경우의 수)예요.
수정이는 라면을 끓여 먹으려고 한다. 라면, 수프, 물, 떡, 달걀, 치즈, 만두, 파, 김치의 9가지 재료 중 라면, 수프, 물을 포함하여 5가지를 선택해서 라면을 끓인다고 할 때, 라면을 끓일 수 있는 경우의 수를 구하여라. (단, 달걀과 치즈 중 적어도 하나는 넣어야 한다.)
문제를 살짝 바꿨어요. 나머지는 다 똑같고 달걀과 치즈 중 적어도 하나는 넣어야 해요. 달걀과 치즈 둘 다를 넣어도 되고, 달걀만 넣거나 치즈만 넣어도 괜찮아요.
이런 문제도 부분집합의 개수 구하기에서 했어요. 특정한 원소 k개 중 적어도 한 개를 포함하는 부분집합의 개수를 구하는 거였죠. 이때는 (전체 부분집합의 개수) - (특정한 원소 k개를 포함하지 않는 부분집합의 개수)를 이용해서 구했어요.
치즈도 없고 달걀도 없는 조리 방법의 수는 처음부터 라면과 치즈가 선택 목록에 없었다고 생각하면 쉽게 구할 수 있어요. 떡, 만두, 파, 김치의 4가지 중에서 2가지를 선택하는 방법의 수와 같죠.
그리고 전체 라면 조리법 수에서 달걀과 치즈가 둘 다 없는 라면 조리법 수를 빼면 둘 중 적어도 하나를 포함하는 조리법 수를 구할 수 있어요.
전체 라면의 조리 방법 개수는 위에서 구한 것처럼 9 - 3C5 - 3 = 6C2 = 15
치즈도 없고 달걀도 없는 라면의 조리 방법 수 = 6 - 2C2 = 4C2 = 6
라면, 수프, 물은 반드시 포함하고 치즈와 달걀 중 적어도 하나는 포함하는 라며 조립법 수 = 15 - 6 = 9
전체 n가지 중 r가지를 선택할 때
p가지를 반드시 포함해야 하는 경우의 수 = n - pCr - p
p가지 중 적어도 하나를 포함해야 하는 경우의 수 = (전체 경우의 수) - (p가지를 포함하지 않는 경우의 수) = nCr - n - pCr
다음 그림에서 사각형의 총 개수를 구하여라.
보통 이런 형태의 문제는 어떻게 풀었나요?
사각형 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개씩을 골라야 하니까 곱의 법칙을 이용해야겠네요.
5C2 × 4C2 = 10 × 6 = 60
조합을 이용하니까 더 쉽게 풀 수 있죠?
일직선 위에 있지 않은 서로 다른 n개의 점에서 두 점을 잇는 직선의 개수 = nC2
일직선 위에 있지 않은 서로 다른 n개의 점에서 세 점을 잇는 삼각형의 개수 = nC3
가로 m개의 선과 세로 n개의 선이 만나서 생기는 사각형의 개수 = mC2 × nC2
직선은 서로 다른 두 점을 연결하면 생겨요. 따라서 두 점의 개수를 구하는 방법과 직선의 개수는 같아요. 삼각형은 서로 다른 세 점을 연결하면 생기니까 세 점의 개수를 구하는 방법의 개수와 삼각형의 개수가 같고요. 마지막 사각형의 개수는 위 예제에서 했던 거예요.
함께 보면 좋은 글
순열과 조합 - 조합이란
순열과 조합 - 조합의 성질
순열과 조합 - 순열이란
순열과 조합 - 순열2. 팩토리얼(factorial), 계승