중복조합

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

Main articles: Multiset and Stars and bars (combinatorics)

순열에서도 중복을 허락할 경우는 중복순열로 별도로 다루었습니다. 순열과 중복순열은 마찬가지로 서로 다른 n개 중에서 k개를 줄 세우지만, 순열에서는 k는 n보다 클 수 없습니다. 그러나 중복순열에서는 k는 제한이 없습니다. 예를 들어, 2개의 문자 a, b에 대해 순열에서는 2개까지 줄 세울 수 있지만, 중복순열에서는 중복을 허락해서 3개도 줄 세울 수 있습니다. 물론 결과는 다음과 같습니다:

\(\quad\)\(2\times 2 \times 2 \)

한편, 조합에서도 중복을 허락하는 중복조합이 있습니다. 예를 들어, 과일 가게에서 사과, 배 중에서 중복을 허락하여 3개를 살 때의 경우의 수와 같은 것이 중복조합의 문제입니다. 만약 사과를 a, 배를 b로 매핑하면, aaa, aab, abb, 그리고 bbb의 네 가지 경우가 있음을 쉽게 알 수 있습니다. 즉, 순서가 상관없으므로, 서로 구별되는 경우의 수는 과일의 개수를 통해 이루어집니다. 두 가지 중에 몇 개를 중복해서 고를 때, 먼저 a를 선택한다면, 항상 0개에서 k개까지 선택할 수 있으며, 반면에 b는 상대적으로 k개에서 0개까지, 종속적으로, 선택됩니다. 이항정리에서 같은 논리로 이용됩니다.

이것을 일반화하면,

정리 1: 서로 다른 2개를 중복을 허락해서 k개를 선택하는 경우의 수는, k + 1입니다.

좀 더 많은 경우를 생각해 보겠습니다.

분식집에서 김밥, 라면, 떡볶이 중에서 7개를 주문하는 방법의 수는 몇 가지일까요? 먼저, 앞에서 했던 것처럼, 김밥을 a, 라면을 b, 및 떡볶이를 c로 맵핑하면,

• a = 0에서, b와 c를 중복해서 7개 선택해야 하는 경우이므로, 정리 1에 의해서 8가지입니다. 이것을 순서쌍으로 표시하면 다음과 같습니다:
(0,0,7), (0,1,6), (0,2,5), (0,3,4), (0,4,3), (0,5,2), (0,6,1), (0,7,0)

• a = 1에서, b와 c를 중복해서 6개 선택해야 하는 경우이므로, 정리 1에 의해서 7가지 경우를 가지고, 순서쌍은 다음과 같습니다:
(1,0,6), (1,1,5), (1,2,4), (1,3,3), (1,4,2), (1,5,1), (1,6,1)

• a = 2에서, 같은 논리로 6가지 경우를 가지고, 순서쌍은 다음과 같습니다:
(2,0,5), (2,1,4), (2,2,3), (2,3,2), (2,4,1), (2,5,0)

• 이런 식으로 계속하면, 마지막은 a = 7에서, 같은 논리로 1가지의 경우의 수를 가지고, 순서쌍은 다음과 같습니다:
(7,0,0)

따라서, 경우의 수는, 8+7+6+5+4+3+2+1입니다.

이로부터 규칙을 찾으셨나요? 그렇습니다.

정리 2: 서로 다른 3개를 중복을 허락해서 k개를 선택하는 경우의 수는, 정리 1을 활용해서 다음과 같이 쓸 수 있습니다.

(k+1)+k+(k–1)+(k–2)+...+2+1

다음으로, 서로 다른 4개를 중복을 허락해서 k개를 선택하는 경우의 수는 정리 2를 활용해서, 예를 들어, 정리 3 같은 것을 역시 만들 수 있을지도 모르겠습니다.

게다가, 이런 식으로 계속해서, 서로 다른 n개를 중복을 허락해서 k개를 선택하는 경우의 수를 역시 구할 수 있을지도 모르겠습니다.

만약 이 방법이 일반화가 가능하고 다른 방법이 발견되기 전이라면, 의미를 가질 수 있습니다. 어쨌든, 보다 간편하게 이용할 수 있는 방법이 이미 알려져 있기 때문에, 이 방법을 일반화할 필요가 없을 것으로 보입니다. 물론 다른 방법으로 일반화를 시도해 볼 수도 있으며, 교육적인 목적에서, 사고의 폭을 넓히는 과정으로 이해될 수 있습니다.

그럼, 서로 다른 종류가 많아지고, 중복을 허락해서 선택해야 할 개수가 많아지면, 어떻게 계산할까요?

조합은, 순열을 조합과 선택한 개수의 (전체) 순열로부터 바꾼 식으로 계산을 했습니다. 중복조합은 별과 막대 방법을 이용합니다. 보통 고등학교 교과서에서 중복조합이라고 이르는 것은 별과 막대에서 정리 2에 해당합니다.

이전 예제로 생각했던, 분식집에서 김밥, 라면, 떡볶이를 7개를 주문하는 방법의 수를 별과 막대 방법으로 구해보겠습니다.

앞에 7개의 그릇(별)이 놓여 있다고 가정합니다. 여기에 김밥, 라면, 떡볶이를 채움으로써 서로 구별을 합니다. 주문을 할 때, 개수를 표시하기 위해서 막대를 이용하는데, 종류가 3가지이므로, 막대는 2개가 필요합니다. 즉, 여기까지 김밥, 여기까지 라면, 나머지는 자연스럽게 떡볶이를 담는 것으로 주문할 것인데, 단어 여기에 막대를 놓습니다.

예를 들어, 김밥 4, 라면 1, 떡볶이 2개는 어떻게 표시할까요?

그럼, 김밥 4, 라면 0, 떡볶이 3개는 어떻게 표시할까요?

반대로 다음 그림은 어떻게 주문을 하는 걸까요?

첫 번째 막대 앞에 별이 없고, 두 번째 막대 앞에도 별이 없습니다. 즉, 김밥 0, 라면 0, 떡볶이 7을 주문한 것입니다.

이 경우의 수를 기호로 \(_3H_7\)로 나타내거나, 또는,

\(\quad\)\(\displaystyle\left(\!\!\binom{3}{7}\!\!\right)\).

이것을 계산하는 방법은 위의 그림에서 처럼, 서로 다른 3가지를 구별하기 위한 막대 3–1=2개와 담을 그릇(별) 7개가 필요하고, 그중에 어느 위치에 별을 둘 것인지를 정하는 조합으로 해석할 수 있습니다. 즉,

\(\quad\)\(\displaystyle \left(\!\!\binom{3}{7}\!\!\right)=\binom{9}{7}=\binom{9}{2}=\frac{9!}{2!7!}\).

또는 \(C(9,2)\)는 전체 9개 중에 막대 2개를 둘 위치를 정하는 것으로, 또는, 마지막 식은 같은 것이 있는 순열로 해석한 것으로 볼 수 있습니다.

서로 다른 n개에서 중복을 허락하여 k개를 선택하는 중복조합의 경우의 수는

\(\quad\)\(\displaystyle _nH_k=\left(\!\!\binom{n}{k}\!\!\right)=C(n+k-1,k)=C(n+k-1,n-1)=\frac{(n+k-1)!}{k!(n-1)!}\)

자연수 해

방정식 \(x+y+z=7\)에 대하여 음이 아닌 정수해의 개수는 몇 개일까요? 이것은 위에서 소개한 것과 동일합니다. 즉, 서로 다른 세 문자를 중복해서 선택할 때, 선택하는 횟수가 정수해가 되는 것으로 생각하면, 전체 7번 선택할 수 있는 중복조합과 같습니다.

\(\quad\)\(\displaystyle \left(\!\!\binom{3}{7}\!\!\right)=\binom{9}{7}=\binom{9}{2}=\frac{9!}{2!7!}\)

반면에 양의 정수해(또는 자연수해)의 개수는 몇 개일까요? 이것을 해석하는 방법은 크게 2가지가 있습니다.

먼저 별과 막대 방법에서 정리 1을 이용할 수 있습니다. 정리 2와 정리 1의 차이는 정리 1에서는 막대가 제일 앞에나 제일 끝에 올 수 없습니다. 그리고 막대끼리 이웃할 수 없습니다. 이때에는 중복조합으로 나타내지 않고, 7개의 별 사이는 6개가 존재하고, 3개로 구분하기 위해서 막대는 2개가 필요합니다. 따라서,

\(\quad\)\(C(6,2)\).

이 문제를 조건을 만족하는 순열#이웃하지 않는 조건의 순열과 같은 것이 있는 순열을 연결해서 해석할 수도 있으며, 결과는 같습니다.

\(\quad\)\(\displaystyle \frac{7!}{7!}\times \frac{P(6,2)}{2!}\) : 별 7개를 줄 세우는 것 곱하기 6곳의 사이 중에 같은 막대 2개 줄 세우는 것

또는 치환을 이용해서 중복조합으로 만들 수 있습니다.

\(\quad\)\(x=x_1+1, y=y_1+1, z=z_1+1\)

여기서 \(x_1,y_1,z_1\)은 이제 음이 아닌 정수입니다. 따라서,

\(\quad\)\(\displaystyle\left(\!\!\binom{3}{4}\!\!\right)=\binom{6}{4}=\binom{6}{2}=\frac{6!}{2!4!}\)

이것은 적어도 1을 가져야 하기 때문에 미리 1개씩 주고 나머지 4개를 중복해서 선택하겠다는 의미입니다.

이 방법이 좀 더 응용을 갖는 경우는 다음과 같습니다.

철수, 영희, 영구에게 10개의 같은 빵을 나누어줄 예정이고, 적어도 2개씩은 받아야 합니다. 이때에는 2개씩 먼저 나누어 주고, 남는 4개를 다음과 같은 중복순열로 나누어줄 수 있습니다.

\(\quad\)\(\displaystyle\left(\!\!\binom{3}{4}\!\!\right)\).

비-감소 함수 또는 비-증가 함수

Main article: 함수의 개수

증가함수와 감소함수는 조합으로 구할 수 있었습니다. 그렇다면, 중복조합으로 구하는 것은 어떤 함수가 있을까요? 다음과 같은 것은 중복조합으로 구할 수 있습니다.

집합 \(X=\{1,2,3,4,5,6,7\}\)에서 집합 \(Y=\{1,2,3\}\)의로의 함수 중에서, 임의의 \(x_1, x_2 \in X\)에 대하여 \(x_1 < x_2\)이면 \(f(x_1) \le f(x_2)\)를 만족하는 함수의 개수는 몇 개일까요? 다른 용어로는 비-감소함수라고 불립니다.

이것은 위의 예에서 보았던, 김밥(1), 라면(2), 떡볶이(3)와 동일합니다. 여기까지 1, 여기까지 2, 나머지 3과 같은 방식입니다. 즉, 서로 다른 3개 중에 중복을 허락하여 7개를 선택하는 중복조합과 같습니다. 따라서, \(_3H_7\).

응용예제

응용예제1

방정식 \(x+y+z+w^2=9\)에 대해 비-음의 정수 \(x,y,z,w\)에 대한 해의 개수를 구하시오.

응용예제2

조건

\(\quad\)\( 1 \le a \le b \le c \le d \le 7\)

을 만족하는 자연수 \(a,b,c,d\)를 나열하여 네 자리 정수 \(abcd\)를 만들 때, 네 숫자 \(a,b,c,d\)의 곱을 \(N=a\times b \times c \times d\)라고 놓습니다. 이렇게 만들어진 모든 \(N\)의 곱은 \(2^x \times 3^y \times 5^z \times 7^w \)입니다. 이때, \(x+y+z+w\)의 값을 구하시오. (단, \(x,y,z,w\)는 자연수입니다.) 

응용예제3

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

\(\quad\)(ㄱ) \(f(1) \times f(4) = f(2) \times f(3)\)

\(\quad\)(ㄴ) 임의의 \(x_1 \in X,\;x_2 \in X\)에 대하여 \(x_1<x_2<4\)이면 \(f\left(x_1\right) < f\left(x_2\right)\)이고,

\(\quad\)\(\quad\)\(\;\; 4 \le x_1 < x_2\)이면 \(f\left(x_1\right) \le f\left(x_2\right)\)이다.

응용예제4

한 개의 주사위를 5번 던질 때 나오는 눈의 수를 차례대로 \(a,b,c,d,e\)라 하자. 다음 조건을 만족시키는 \(a,b,c,d,e\)의 모든 순서쌍 \(\{a,b,c,d,e\}\)의 개수를 구하시오.

\(\quad\)(ㄱ) \(a \le b \le c \le d \le e\)

\(\quad\)(ㄴ) \(ae = bd\)