조합

원문 보기: https://dawoum.duckdns.org/wiki/조합

Main article: Combination

순열은 서로 다른 n개 중에 k개를 줄 세우는 경우의 수입니다. 줄 세운다는 것은 위치에 따라 다른 경우이기 때문에 곱의 법칙을 적용할 수 있음을 의미합니다.

역시, 어떤 것을 선택할 때에도, 선택한 각각이 서로 다를 것을 의미할 때에는 순열에서와 마찬가지로 곱의 법칙을 적용할 수 있습니다. 예를 들어, 서로 다른 30명의 학생 중에서 반장, 부반장, 총무 1명씩 3명을 선택할 때에는, 각각, 임원의 명칭이 다르기 때문에, 곱의 법칙을 적용하는 순열로 해석할 수 있습니다. 아래와 같이 표현할 수 있습니다:

\(\quad P(30,3) = 30\times 29 \times 28\)

반면에, 서로 다른 30명의 학생 중에서 대의원을 3명 선택할 때에는 뽑히는 순서는 상관이 없습니다. 대의원은 대의원1, 대의원2, 대의원3과 같은 구별이 없기 때문입니다. 즉, 최종적으로 선택된 3명의 사람이 누구로 구성되었는지에 따라 다른 경우가 됩니다. 이와 같이 순서가 중요하지 않은 응용을 다루는 것이 조합입니다. 그 결과는 조합을 의미하는 영어 단어 Combination의 머리글자를 따서 다음과 같이 표시할 수 있습니다:

\(\quad C(30,3)\) 또는 \(_{30}C_3\)

이를 일반화해서,

서로 다른 \(n\)개에서, 순서를 고려하지 않고, \(k\)개를 선택하는 조합을 아래와 같이 나타냅니다:
\(\quad C(n,k)\) 또는 \(_nC_k\)

조합의 계산

순열은 곱의 법칙의 특수한 경우이기 때문에, 곱의 법칙으로 계산을 합니다. 그럼 조합은 어떻게 계산해야 할까요?

서로 다른 30명 중에서 1등, 2등, 3등을 뽑는 퀴즈 게임을 한다고 가정해 보겠습니다. 최종 목표는 30명 중에서 1,2,3등을 정하는 것입니다. 이것을 두 단계로 나누어서 진행해 보면, 다음과 같습니다.

• 예선 : 먼저 1등, 2등, 3등을 할 3명을 뽑습니다 : \(C(30,3)\)
• 결선: 예선에서 뽑힌 3명에 등수를 매깁니다 : \(3!\)

즉, 직접 1등, 2등, 3등을 뽑는 것과 예선, 결선을 거치는 것은 같은 결과를 가져옵니다. 식으로 표현하자면, 다음과 같습니다:

\(\quad P(30,3) = C(30,3) \times 3! \)

이를 일반화하면,

\(\quad P(n,k) = C(n,k) \times k! \)

조합의 식으로 변형이 가능하고, 또는 팩토리얼만의 식으로 바꿀 수도 있습니다:

\(\quad \displaystyle C(n,k)=\frac{P(n,k)}{k!}=\frac{n!}{k!(n-k)!}\) (단, \(0 \le k \le n\))

한편, 다른 경우를 생각해 보겠습니다. 

서로 다른 30명 중에서 야외 청소를 할 27명을 선택하는 경우를 생각해 보십시오. 아마도 대부분의 사람들은 30명 중에 27명을 선택하지 않을 것입니다. 왜냐하면, 30명 중에 야외 청소를 할 27명을 선택하는 것보다는 30명 중에 청소하지 않을 3명을 뽑는 것이 더 간단하고 편하기 때문입니다. 즉,

\(\quad C(30,27)=C(30,3)\).

이를 일반화하면, 서로 다른 n개 중에서 k개를 선택하는 것은 n–k개를 선택하는 것과 경우의 수가 같습니다. 즉,

\(\quad C(n,k)=C(n,n-k)\) (단, \(0 \le k \le n\))

계산에서도 선택하는 개수가 적은 것이 보다 쉽습니다.

파스칼의 삼각형

조합을 사용하는 식에서 자주 응용되는 식은 파스칼의 규칙 또는 파스칼의 항등식입니다.

\(C(n,k)=C(n-1,k-1)+C(n-1,k)\) (단, \(1 \le k \le n-1\))

이 표현에서 앞의 숫자가 같고, 뒤의 숫자가 하나 차이 날 때, 앞의 숫자는 1 증가하고, 뒤의 숫자는 큰 수와 같은 조합으로 나타내어집니다.

이 표현을 조합으로 표현하면 다음과 같습니다:

서로 다른 \(n\)개에서 \(k\)개를 선택하는 조합의 수는
\(\quad\)(특정한 1개를 선택해 두고, 나머지 \(n–1\)개에서 \(k–1\)개를 선택하는 조합의 수)
\(\quad\)+ (특정한 1개를 제외하고, 나머지 \(n–1\)개에서 \(k\)개를 선택하는 조합의 수)

위의 두 경우 외에는 다른 방식으로 주어진 표현을 만족하는 경우가 없으므로, 두 식의 결과는 같은 값을 가집니다.

어쨌든, 조합이 많이 발생하는 식을 간단하게 표현하면, 이항계수와 연관이 있던지, 또는 파스칼의 삼각형의 표현을 이용하던지 2가지 중에 하나일 가능성이 매우 높습니다. 예를 들어,

\(\quad C(10,0)+C(10,1)+C(10,2)+\cdots+C(10,9)+C(10,10)=2^{10}\)

\(\quad C(4,0)+C(4,1)+C(5,2)+C(6,3)+C(7,4)+C(8,5)+C(9,6)=C(10,6)\)

첫 번째 식은 조합에서 서로 다른 n이 10개로 같습니다. 이와 같이 앞의 숫자가 같은 경우에는, 주로 이항계수의 성질에 의해 쉽게 구해집니다.

두 번째 식은 앞의 두 개의 식이

\(\quad\)\(C(4,0)+C(4,1)=C(5,1)\) 이 결과를 다음 식과 함께
\(\quad\)\(C(5,1)+C(5,2)=C(6,2)\) 이 결과를 다음 식과 함께
\(\quad\)\(C(6,2)+C(6,3)=C(7,3)\) 이런 식으로 진행하면,
\(\quad\)\(C(10,6)\).

즉, 앞의 숫자가 1씩 증가하는 경우에는 파스칼의 항등식을 고려해 볼 수 있습니다.

증가함수, 감소함수의 개수

함수의 개수에서 여러 가지 함수의 개수를 구하는 것을 알아보았습니다. 순열과 조합을 배우고 나면, 만드는 방법이 달라지지는 않지만, 순열과 조합을 나타내는 기호를 사용할 수 있습니다.

두 집합 \(X=\{1,2,3\}, Y=\{2,4,6,8,10\}\)에서 다음 함수의 개수를 구하시오.

• 함수: \(5\times 5\times 5 = _5\Pi_3 = 5^3\) : 중복순열
• 일대일 대응: 0
• 일대일 함수: \(5\times 4 \times 3 = P(5,3)\) : 순열
• 항등함수: 0
• 상수함수: 5
• 증가함수 또는 감소함수: \(C(5,3)\)

증가함수 또는 감소함수의 개수는 당연히 정의역의 개수보다 공역의 개수가 같거나 많을 때 만들 수 있습니다. 공역에서 정의역의 개수만큼 선택을 한 후에, 대응 관계는 이미 1로 유일하게 정해져 있기 때문에, 즉, 증가함수일 때에는 증가하는 방향으로 연결, 또는 감소함수일 경우에는 감소하는 방향으로 연결하는 1가지뿐입니다. 따라서, 전체 경우의 수는 조합 × 1 이므로 조합의 개수와 같습니다.

조금 더 응용할 수도 있습니다.

예를 들어 두 집합 \(X=\{1,2,3,4,5\}, Y=\{1,2,3,4,5,6,7,8,9,10\}\)에서 다음 두 조건을 만족하는 함수의 개수를 구하시오.

• (가) 집합 \(X\)의 임의의 두 원소 \(x_1, x_2\)에 대하여 \(x_1 < x_2\)이면 \(f(x_1) > f(x_2)\)
• (나) \(f(3)=4\)

(가)는 감소함수를 나타내고, (나)는 정의역의 원소 3은 공역 4에 대응함을 나타냅니다. 이 두 사실은 3보다 작은 정의역의 원소 1,2는 4보다 큰 공역의 원소 5,6,7,8,9,10 중에 2개와 대응해야 하고, 3보다 큰 정의역의 원소 4,5는 4보다 작은 공역의 원소 1,2,3 중에 2개와 대응을 해야 함을 의미합니다. 따라서

\(\quad\)\(C(6,2)\times C(3,2)\)

도형과 조합

주어진 점을 연결해서 만들 수 있는 직선, 삼각형, 사각형, 등은 선택하는 점의 순서에 상관없이 같은 도형을 나타내기 때문에, 조합으로 구할 수 있습니다.

예를 들어, 그림과 같이 반원 위에 10개의 점이 있을 때, 두 점을 연결하여 만들 수 있는 직선의 개수는 몇 개일까요? 직선은 서로 다른 2점을 연결했을 때 1개를 만들 수 있습니다. 그러나 그림처럼 지름 위에 놓인 5개의 점으로는 1개의 직선만을 그릴 수 있습니다. 따라서

\(\quad\)\(C(10,2)-C(5,2)+1\)

지름 위의 5개로 그릴 수 있는 모든 직선을 제외하지만, 지름 자체의 직선 1개는 더해져야 합니다.

반면에 세 점을 연결하여 만들 수 있는 삼각형의 개수는 몇 개일까요? 삼각형은 같은 직선 위에 있지 않은 세 점을 연결했을 때 1개를 만들 수 있습니다. 그러나 같은 직선 위에 있는 세 점은 삼각형을 그릴 수 없습니다. 따라서

\(\quad\)\(C(10,3)-C(5,3)\)

응용예제

응용예제1

5명의 학생이 각각 빨간색 티셔츠와 파란색 티셔츠 중 한 가지를 골라 입고 일렬로 놓인 5개의 의자에 한 명씩 앉으려고 한다.

빨간색 티셔츠를 고른 학생이 2명 이상이면서 빨간색 티셔츠를 고른 학생끼리는 서로 이웃하지 않도록 앉는 경우의 수는? (단, 빨간색 티셔츠와 파란색 티셔츠는 각각 충분히 많고, 같은 색의 티셔츠끼리는 서로 구별하지 않는다.)

응용예제2

어느 세 점도 같은 직선 위에 있지 않는 4개의 점 \(\mathrm{P,Q,R,S}\)가 있다. 선분 3개를 그어 점 4개를 연결하는 방법의 수를 구하면? (단, 연결 순서는 무시한다.)

응용예제3

두 집합 \(X=\{1,2,3,4,5,6\}\), \(Y=\{0,1,2,3,4,5,6,7,8,9\}\)에 대하여 다음 각 조건을 만족하는 함수 \(f\)의 개수를 각각 구하시오.

조건-(가)

• \(f(1) < f(3)\)
• \(f(2)-f(4) \ge 3\)

조건-(나)

• \(x_1<x_2\)이면 \(f(x_1) < f(x_2)\) (단, \(x_1,x_2 \in X\))
• \(f(2) \times f(5)\)의 값은 홀수

응용예제4

숫자 1, 2, 3이 적혀있는 빨간 공 3개와 숫자 4, 5, 6, 7이 적혀있는 파란 공 4개에 대해 다음 조건을 만족시키도록 모든 공을 일렬로 배열하는 경우의 수는?

\(\quad\)(ㄱ) 같은 색의 공은 숫자가 커질수록 오른쪽으로 나열한다.

\(\quad\)(ㄴ) 숫자 2가 적힌 빨간 공은 숫자 5가 적힌 파란 공보다 왼쪽에 나열한다.