Composition
정의[편집 | 원본 편집]
- [math]\displaystyle{ a_i,i=1,2,\cdots,k }[/math]를 전체 합이 [math]\displaystyle{ n }[/math]인 음이 아닌 정수들이라 가정하자. 이 때, [math]\displaystyle{ k }[/math]짝(ordered k-tuple) [math]\displaystyle{ \left(a_1,a_2,\cdots,a_k\right) }[/math]를 [math]\displaystyle{ k }[/math] 부분으로 만든 [math]\displaystyle{ n }[/math]의 약한 구성(Weak Composition)이라 정의한다.
뭔가 거창한 설명이 붙었지만, 한국에서 중복조합이라 부르는 것과 동일하다. 약한 구성의 수를 구하는 방법을 통해 이게 왜 중복조합이 되는지 살펴보자.
- [math]\displaystyle{ n }[/math]의 [math]\displaystyle{ k }[/math] 부분 약한 구성의 수는 부정방정식 [math]\displaystyle{ a_1+a_2+\cdots+a_k=n }[/math]의 음이 아닌 정수해 쌍의 수와 같다. 이는 곧 [math]\displaystyle{ k }[/math]개의 서로 다른 물체 [math]\displaystyle{ a_1,a_2,\cdots,a_k }[/math] 중에서 각각의 물체를 중복을 허락해서 몇 번 뽑을 건지 결정하는 것과 같다. 이제, [math]\displaystyle{ n }[/math]개의 별과 [math]\displaystyle{ k-1 }[/math]개의 막대기가 있다고 가정하자. 이 별들을 막대기를 사용해서 총 [math]\displaystyle{ k }[/math]의 무리로 쪼갤 수 있는데, [math]\displaystyle{ i }[/math]번째 무리에 속한 별들의 수를 [math]\displaystyle{ a_i }[/math]에 대응시키면 구하고자 하는 순서쌍이 나온다. 즉, 전체 가짓수는 [math]\displaystyle{ n }[/math]개의 별과 [math]\displaystyle{ k-1 }[/math]개의 막대기를 일렬로 나열하는 방법의 수이고, 이는 곧 [math]\displaystyle{ \binom{n+k-1}{k-1} }[/math]이 된다.
한편, 중복조합의 정의는 다음과 같다.
- [math]\displaystyle{ n }[/math]개 중에 [math]\displaystyle{ k }[/math]개를 순서에 상관없이, 중복을 허락하여 뽑는 것을 중복조합이라 부르며, 기호로는 [math]\displaystyle{ _nH_k }[/math]로 나타낸다. 이 값은 [math]\displaystyle{ \binom{n+k-1}{k} }[/math]와 동일함을 위와 같은 방법으로 보일 수 있다.
이제, 약한 구성의 수를 중복조합 기호로 나타내면 [math]\displaystyle{ _kH_n }[/math]임을 쉽게 알 수 있다. 결과적으론 [math]\displaystyle{ k }[/math]개 중에 중복을 허락하여 [math]\displaystyle{ n }[/math]개를 뽑는 가짓 수와 동일하기 때문. 만약 중복조합 문제를 많이 풀어본 학생이라면 부정방정식이 튀어나온 순간 바로 중복조합이라는 것을 눈치 챘을 것이다.
한국에서 쓰는 약한 구성의 기호인 [math]\displaystyle{ _kH_n }[/math]는 출처를 알 수 없는 정체불명의 기호이다(...). 책에 따라서는 [math]\displaystyle{ \left(\!\binom{k}{n}\!\right) }[/math]로 표기하는 경우도 있으나, 일반적으로는 그냥 조합으로 풀어서 쓴다. 또한 주의할 것은, 약한 구성은 [math]\displaystyle{ n }[/math]을 [math]\displaystyle{ k }[/math]개로 구성하는 것이고, 중복조합은 [math]\displaystyle{ n }[/math]개 중에 [math]\displaystyle{ k }[/math]개를 뽑는 다는 것으로, [math]\displaystyle{ n }[/math]과 [math]\displaystyle{ k }[/math]의 위치가 서로 반대이다. 중복조합이나 약한 구성이나 결국 같은 것이므로, 자기에게 맞는 정의를 사용하자. 괜히 틀리지말고(...)
영미권에서는 약한 구성을 설명할 때 위 풀이처럼 별과 막대기를 사용해서 설명하는 경우가 흔하다. 따라서 약한 구성을 Stars and bars라는 별명으로 부르는 경우가 많다. 영위백 문서도 있을 정도.
약한 구성의 수는 중복집합(Multiset)의 개수와 동일하다. 중복집합이란, 집합에서 중복되는 원소를 지우지 않고 표기 해주는 집합을 나타내는데 (순서는 여전히 상관 없다), 이는 곧 중복을 허락하여 원소를 뽑는 것과 동일하기 때문. [math]\displaystyle{ \left(\!\binom{k}{n}\!\right) }[/math] 기호도 원래는 중복집합을 나타내는 기호이다.
강한 구성[편집 | 원본 편집]
위에서 계속 약한 구성이라 표기했는데, 약한 구성이 있으면 강한 구성이 있는 법. 정의는 거의 동일하다.
- [math]\displaystyle{ a_i,i=1,2,\cdots,k }[/math]를 전체 합이 [math]\displaystyle{ n }[/math]인 양의 정수들이라 가정하자. 이 때, [math]\displaystyle{ k }[/math]짝(ordered k-tuple) [math]\displaystyle{ \left(a_1,a_2,\cdots,a_k\right) }[/math]를 [math]\displaystyle{ k }[/math] 부분으로 만든 [math]\displaystyle{ n }[/math]의 강한 구성 (Strong Composition)이라 정의한다.
음이 아닌 정수에서 양의 정수로 바뀐 것 뿐으로, 각 정수에서 1씩 빼주면 약한 구성과 완벽히 동일해진다. 즉, 강한 구성의 수는 [math]\displaystyle{ \binom{n+k-1-k}{k-1}=\binom{n-1}{k-1} }[/math]. 중복조합 기호를 사용해서 나타내면 [math]\displaystyle{ _kH_{n-k} }[/math]이다. 여기서는 약한 구성과 강한 구성을 엄격하게 구분했지만, 그냥 구성이라하면 보통 강한 구성을 가리키고, 약한 구성은 약한 구성이라고 따로 표기해준다.
예시[편집 | 원본 편집]
음이 아닌 정수 [math]\displaystyle{ x, y, z }[/math]에 대해, [math]\displaystyle{ x+y+z \leq 3 }[/math]를 만족시키는 순서쌍 [math]\displaystyle{ \left(x, y, z\right) }[/math]의 수는? 만약 [math]\displaystyle{ x,y,z }[/math]가 양의 정수라면?
- [math]\displaystyle{ x+y+z=n }[/math]를 만족시키는 음이 아닌 정수의 순서쌍 [math]\displaystyle{ \left(x,y,z\right) }[/math]의 수는 3개중 중복을 허락하여 n개를 뽑는 가짓 수와 동일하다. 즉, 구하고자 하는 답은 [math]\displaystyle{ _3H_0+_3H_1+_3H_2+_3H_3=_2C_0+_3C_1+_4C_2+_5C_3=1+3+6+10=20 }[/math]. 만약 [math]\displaystyle{ x,y,z }[/math]가 양수라면, [math]\displaystyle{ x-1,y-1,z-1 }[/math]은 음이 아닌 정수가 된다. 따라서, 원래 부등식에서 3을 빼주면 음이 아닌 정수의 순서쌍을 찾는 문제와 동일해진다. 이 경우, [math]\displaystyle{ x+y+z\leq0 }[/math]이 되어 한 가지 순서쌍밖에 없음을 쉽게 알 수 있다.