구성 편집하기

{{+1|Composition}}

== 정의 ==
:<math>a_i,i=1,2,\cdots,k</math>를 전체 합이 <math>n</math>인 음이 아닌 [[정수]]들이라 가정하자. 이 때, <math>k</math>짝(ordered k-tuple) <math>\left(a_1,a_2,\cdots,a_k\right)</math>를 <math>k</math> 부분으로 만든 <math>n</math>의 '''약한 구성'''(Weak Composition)이라 정의한다.
뭔가 거창한 설명이 붙었지만, 한국에서 중복조합이라 부르는 것과 동일하다. 약한 구성의 수를 구하는 방법을 통해 이게 왜 중복조합이 되는지 살펴보자.
:<math>n</math>의 <math>k</math> 부분 약한 구성의 수는 부정방정식 <math>a_1+a_2+\cdots+a_k=n</math>의 음이 아닌 정수해 쌍의 수와 같다. 이는 곧 <math>k</math>개의 서로 다른 물체 <math>a_1,a_2,\cdots,a_k</math> 중에서 각각의 물체를 중복을 허락해서 몇 번 뽑을 건지 결정하는 것과 같다. 이제, <math>n</math>개의 별과 <math>k-1</math>개의 막대기가 있다고 가정하자. 이 별들을 막대기를 사용해서 총 <math>k</math>의 무리로 쪼갤 수 있는데, <math>i</math>번째 무리에 속한 별들의 수를 <math>a_i</math>에 대응시키면 구하고자 하는 순서쌍이 나온다. 즉, 전체 가짓수는 <math>n</math>개의 별과 <math>k-1</math>개의 막대기를 일렬로 나열하는 방법의 수이고, 이는 곧 <math>\binom{n+k-1}{k-1}</math>이 된다.
한편, 중복조합의 정의는 다음과 같다.
:<math>n</math>개 중에 <math>k</math>개를 순서에 상관없이, 중복을 허락하여 뽑는 것을 중복조합이라 부르며, 기호로는 <math>_nH_k</math>로 나타낸다. 이 값은 <math>\binom{n+k-1}{k}</math>와 동일함을 위와 같은 방법으로 보일 수 있다.
이제, 약한 구성의 수를 중복조합 기호로 나타내면 <math>_kH_n</math>임을 쉽게 알 수 있다. 결과적으론 <math>k</math>개 중에 중복을 허락하여 <math>n</math>개를 뽑는 가짓 수와 동일하기 때문. 만약 중복조합 문제를 많이 풀어본 학생이라면 부정방정식이 튀어나온 순간 바로 중복조합이라는 것을 눈치 챘을 것이다.

한국에서 쓰는 약한 구성의 기호인 <math>_kH_n</math>는 출처를 알 수 없는 정체불명의 기호이다(...). 책에 따라서는 <math>\left(\!\binom{k}{n}\!\right)</math>로 표기하는 경우도 있으나, 일반적으로는 그냥 [[조합]]으로 풀어서 쓴다. 또한 주의할 것은, 약한 구성은 <math>n</math>을 <math>k</math>개로 구성하는 것이고, 중복조합은 <math>n</math>개 중에 <math>k</math>개를 뽑는 다는 것으로, <math>n</math>과 <math>k</math>의 위치가 서로 반대이다. 중복조합이나 약한 구성이나 결국 같은 것이므로, 자기에게 맞는 정의를 사용하자. 괜히 틀리지말고(...)

영미권에서는 약한 구성을 설명할 때 위 풀이처럼 별과 막대기를 사용해서 설명하는 경우가 흔하다. 따라서 약한 구성을 Stars and bars라는 별명으로 부르는 경우가 많다. 영위백 문서도 있을 정도.

약한 구성의 수는 [[중복집합]](Multiset)의 개수와 동일하다. 중복집합이란, 집합에서 중복되는 원소를 지우지 않고 표기 해주는 집합을 나타내는데 (순서는 여전히 상관 없다), 이는 곧 중복을 허락하여 원소를 뽑는 것과 동일하기 때문. <math>\left(\!\binom{k}{n}\!\right)</math> 기호도 원래는 중복집합을 나타내는 기호이다.

== 강한 구성 ==
위에서 계속 약한 구성이라 표기했는데, 약한 구성이 있으면 강한 구성이 있는 법. 정의는 거의 동일하다.
:<math>a_i,i=1,2,\cdots,k</math>를 전체 합이 <math>n</math>인 양의 [[정수]]들이라 가정하자. 이 때, <math>k</math>짝(ordered k-tuple) <math>\left(a_1,a_2,\cdots,a_k\right)</math>를 <math>k</math> 부분으로 만든 <math>n</math>의 '''강한 구성 (Strong Composition)'''이라 정의한다.
음이 아닌 정수에서 양의 정수로 바뀐 것 뿐으로, 각 정수에서 1씩 빼주면 약한 구성과 완벽히 동일해진다. 즉, 강한 구성의 수는 <math>\binom{n+k-1-k}{k-1}=\binom{n-1}{k-1}</math>. 중복조합 기호를 사용해서 나타내면 <math>_kH_{n-k}</math>이다. 여기서는 약한 구성과 강한 구성을 엄격하게 구분했지만, 그냥 구성이라하면 보통 강한 구성을 가리키고, 약한 구성은 약한 구성이라고 따로 표기해준다.

== 예시 ==
음이 아닌 정수 <math>x, y, z</math>에 대해, <math>x+y+z \leq 3</math>를 만족시키는 순서쌍 <math>\left(x, y, z\right)</math>의 수는? 만약 <math>x,y,z</math>가 양의 정수라면?
:<math>x+y+z=n</math>를 만족시키는 음이 아닌 정수의 순서쌍 <math>\left(x,y,z\right)</math>의 수는 3개중 중복을 허락하여 n개를 뽑는 가짓 수와 동일하다. 즉, 구하고자 하는 답은 <math>_3H_0+_3H_1+_3H_2+_3H_3=_2C_0+_3C_1+_4C_2+_5C_3=1+3+6+10=20</math>. 만약 <math>x,y,z</math>가 양수라면, <math>x-1,y-1,z-1</math>은 음이 아닌 정수가 된다. 따라서, 원래 부등식에서 3을 빼주면 음이 아닌 정수의 순서쌍을 찾는 문제와 동일해진다. 이 경우, <math>x+y+z\leq0</math>이 되어 한 가지 순서쌍밖에 없음을 쉽게 알 수 있다.

== 관련 문서 ==
*[[경우의 수]]
*[[순열]]
*[[조합]]

[[분류:조합론]]