조합

최근 수정 시각: (5년 전)
중복조합에서 넘어옴
분류
목차
1. 개요2. 중복 조합3. 조합의 성질4. 예시5. 관련 문서

1. 개요 [편집]

∣S∣=n|S|=n인 집합 SS에서 rr-부분집합의 개수이며, 이를 nn개에서 rr개를 택하는 조합(組合)이라고 한다. 이 조합은 순열과 다른 개념으로 순서 차이가 중요하다.
기호로는 nCr{}_n\mathrm C_r[1], C(n, r) C(n, \ r), (nr)\dbinom nr등이 있다. 여기서 C는 영어 combination의 머리글자이다. 한국의 고등학교 과정에서는 nCr{}_n\mathrm C_r이 쓰이지만 세계적으로는 (nr)\dbinom nr이 많이 쓰인다. [2]

순열과 마찬가지로 뭔가 거창한 정의가 붙었지만 실상은 초등학교에서부터 풀어온 경우의 수를 좀 더 수학적으로 나타낸 것뿐이다. 다만 계산하는 것은 조금 더 까다로워졌다. 계산하는 공식을 예시를 통해 유도해보자. 33명중에서 대표 22명을 뽑는 상황을 가정하면, 순열을 쓸 경우 3P2=3×2=6{}_3\mathrm P_2=3\times2=6이 되는데, 순열은 '33명중에서 대표 22명을 뽑아서 순서대로 나열하는 경우의 수'이므로 '나열하는 조작'을 배제해주면 되고 같은 것이 있는 경우의 순열과 비슷하게, 22명의 대표가 같으므로 2!2!로 나눠주면 된다. 따라서, (32)=3P22!\dbinom 3 2=\dfrac{{}_3\mathrm P_2}{2!}임을 알 수 있다. 일반적인 경우는 다음과 같다.
nCr=nPrr!=n!(n−r)!r!=Γ(n+1)Γ(n−r+1)Γ(r+1)=1r!∏i=0r−1(n−i)=n(n−1)(n−2)⋯⋯(n−r+1)r!\displaystyle {}_n\mathrm C_r=\frac{{}_n\mathrm P_r}{r!}=\frac{n!}{(n-r)!r!} = \frac{\Gamma(n + 1)}{\Gamma(n - r + 1) \Gamma(r + 1)} = \frac 1{r!} \prod_{i=0}^{r-1} \left( n-i \right) = \frac{n \left( n-1 \right) \left( n-2 \right) \cdots\cdots \left( n-r+1 \right)}{r!}

순열과 마찬가지로 조합 역시 팩토리얼 및 감마 함수로 정의할 수 있기 때문에 r=0r=0이어도 무방하다.

2. 중복 조합 [편집]

조합과 마찬가지로 nn개의 원소에서 rr개를 순서에 상관없이 뽑는데, 중복을 허락할 때의 가짓수이다. 기호로는 ( ⁣ ⁣(nr) ⁣ ⁣)\left(\!\!\dbinom{n}{r}\!\!\right)을 쓰며, 한국과 일본에서는 nHr{}_n\mathrm H_r도 통한다.[3] H\mathrm H라는 기호는 동차 단항식(Homogeneous monomial) 또는 동차곱(Homogeneous product)의 'Homogeneous'에서 딴 것이다.#

중복 조합의 가짓수를 실제로 구하려고 해보면 순열이나 위의 조합과는 다르게 훨씬 복잡함을 알 수 있다.[4] 계산공식을 유도하는 과정은 보통 "원"과 "막대기"를[5] 사용해서 설명한다. 예를 들어 숫자 11, 22, 33중 중복을 허락하여 55개를 뽑는 경우의 수를 생각해보자. 일단 55개를 뽑으므로 원 55개를 나란히 그린다. 이제 이 55개의 원 사이에 막대기를 집어넣어 33그룹으로 나누는데 이 '그룹'이 곧 주어진 원소의 종류 n\boldsymbol n개를 의미한다. 이를테면 11233→11/2/3311233 \to 11/2/33으로, 11133→111//3311133 \to 111//33으로 나타낼 수 있으므로, 특정 원소를 뽑지 않는 경우는 막대기가 중복되어 나열되는 경우로 간주할 수 있다. 33그룹으로 나누기 위해 필요한 막대기의 수는 (3−1)=2(3-1) = 2개이고, 나눠진 각 그룹에 있는 원의 수를 각각 숫자 11, 22, 33을 뽑는 개수라고하면 구하고자 하는 값이 나온다. 즉 총 가짓수는 55개의 원과 22개의 막대기를 나열하는 가짓수와 같고, 이는 77개의 칸중 막대기를 그릴 22개의 칸을 정하는 것과 동일하다. 즉, 5+3−1C2=7C2{}_{5+3-1}\mathrm C_2= {}_7\mathrm C_2가 답. 일반적인 경우는 다음과 같다.
nHr=r+(n−1)Cr=n+r−1Cn−1=(n+r−1)!(n−1)!r!=Γ(n+r)Γ(n)Γ(r+1)=1r!∏i=0r−1(n+i)=n(n+1)(n+2)⋯⋯(n+r−1)r!\begin{aligned} {}_n\mathrm H_r &= {}_{r+(n-1)}\mathrm C_r = {}_{n+r-1}\mathrm C_{n-1} \\ &= \frac{(n+r-1)!}{(n-1)!r!} = \frac{\Gamma(n+r)}{\Gamma(n) \Gamma(r+1)} = \frac 1{r!} \prod_{i=0}^{r-1} \left( n+i \right) = \frac{n \left( n+1 \right) \left( n+2 \right) \cdots\cdots \left( n+r-1 \right)}{r!} \end{aligned}

이를 응용하여 배스킨라빈스의 3131가지 아이스크림을 중복을 허락하여 고를 경우(ex. 쿼터 크기에 엄마는 외계인×2, 체리 쥬빌레, 아몬드봉봉 등)고를 수 있는 총 경우의 수는 다음과 같이 구할 수 있다.

파인트(33가지): 31H3=3+31−1C3=33C3=5456{}_{31}\mathrm H_3 = {}_{3+31-1}\mathrm C_3= {}_{33}\mathrm C_3=5456가지.
쿼터(44가지): 31H4=4+31−1C4=34C4=46376{}_{31}\mathrm H_4 = {}_{4+31-1}\mathrm C_4= {}_{34}\mathrm C_4=46376가지.
패밀리(55가지): 31H5=5+31−1C5=35C5=324632{}_{31}\mathrm H_5 = {}_{5+31-1}\mathrm C_5= {}_{35}\mathrm C_5=324632가지.
하프갤런(66가지): 31H6=6+31−1C6=36C6=1947792{}_{31}\mathrm H_6 = {}_{6+31-1}\mathrm C_6= {}_{36}\mathrm C_6=1947792가지.

반면에 중복을 허락하지 않을 경우엔 일반적인 조합과 같아진다.
파인트(33가지): 31C3=4495{}_{31}\mathrm C_3=4495가지.
쿼터(44가지): 31C4=31465{}_{31}\mathrm C_4=31465가지.
패밀리(55가지): 31C5=169911{}_{31}\mathrm C_5=169911가지.
하프갤런(66가지): 31C6=736281{}_{31}\mathrm C_6=736281가지.

참고하면 좋은 블로그

언뜻 보기에 조합의 특수한 경우로밖에 안 보이지만 사실 아주 중요한 성질이 있다. 부분곱으로 나타낸 중복 조합식의 nn에 −n-n을 대입하면 다음과 같이 식이 변형되면서 조합에 관한 식으로 바뀐다.
−nHr=1r!∏i=0r−1(−n+i)=(−1)rr!∏i=0r−1(n−i)=(−1)rnCr\displaystyle {}_{-n}\mathrm H_r = \frac 1{r!} \prod_{i=0}^{r-1} \left( -n+i \right) = \frac{\left( -1 \right)^r}{r!} \prod_{i=0}^{r-1} \left( n-i \right) = \left( -1 \right)^r {}_n\mathrm C_r
이를 달리 표현하면 중복 조합은 조합에서 nn이 음수인 경우로 볼 수 있고[6] nn의 범위를 모든 정수로 확장[7]해주는 성질이 있음을 알 수 있다.

3. 조합의 성질 [편집]

  1. (nr)=(nn−r)\dbinom nr= \dbinom n {n-r}: nn개중 rr개를 뽑는 것은 nn개중 (n−r)(n-r)개의 뽑지 않을 것을 고르는 것과 가짓수가 같다. 직접 전개하여 증명할 수도 있다.
  2. (nr)=(n−1r)+(n−1r−1)\dbinom nr =\dbinom {n-1}r +\dbinom {n-1}{r-1}: nn개중 한 개를 고정한다. 이제 nn개중 rr개를 뽑는 가짓수는 그 한 개가 있는 경우와 없는 경우 2가지로 나눠지고, 각각의 가짓수는 n−1Cr−1{}_{n-1}\mathrm C_{r-1}, n−1Cr{}_{n-1}\mathrm C_r이다. 역시 직접 전개하여 증명할 수도 있다.
  3. 이항정리 참조.

4. 예시 [편집]

조합
남녀 각각 55명 중에서 남자 33명, 여자 22명을 뽑아 원탁에 앉히는 가짓수는?
남자 33명을 뽑는 수는 5C3=10{}_5\mathrm C_3=10, 여자 22명을 뽑는 수는 5C2=10{}_5\mathrm C_2=10. 곱의 법칙에 의해 전체 가짓수는 10×10=10010\times10=100. 이 55명을 원탁에 앉히므로, 원순열에 의해 100×(5−1)!=2400100\times\left(5-1\right)!=2400

중복 조합
음이 아닌 정수 xx, yy, zz에 대해, x+y+z≤3x+y+z \leq 3를 만족시키는 순서쌍 (x, y, z)(x, \ y, \ z)의 수는?
주어진 식을 x+y+z=3−n (0≤n≤3)x+y+z=3-n \ (0 \le n \le 3)으로 나타내면 이는 곧 음이 아닌 정수 xx, yy, zz, nn에 대해 x+y+z+n=3x+y+z+n=3을 만족하는 식이며, 순서쌍 (x, y, z, n)(x, \ y, \ z, \ n)을 고르는 경우와 같다. 이는 44개중 중복을 허락하여 33개를 뽑는 가짓수와 동일하다. 즉, 구하고자 하는 답은 4H3=6C3=20{}_4\mathrm H_3={}_6\mathrm C_3=20.

5. 관련 문서 [편집]

[1] 여기에서 n의 위치는 r 자리를 빼고 C 앞이나 뒤, 위첨자 아래첨자 모두 가능하다.[2] 울프럼알파에서는 nCr도 인식한다.[3] 조합 기호를 이용해서 나타낼 수 있기 때문에 국가에 따라서는 따로 기호를 만들어 쓰지 않는 경우가 많고 별도의 기호가 있다 하더라도 국가마다 제각각이다.[4] 중복 순열보다도 훨씬 복잡한데, 서로 다른 nn종류의 원소에서 특정 원소를 고르지 않는 경우까지 포함하기 때문이다. 이를테면 A, B, C에서 중복을 허용하여 4개를 뽑는 경우의 수 중엔 AAAC처럼 B가 포함되지 않는 경우도 포함된다.[5] 혹은 비슷한 다른 무언가. 칸막이라는 표현도 쓴다.[6] 엄밀히 따지면 −nCr=(−1)rnHr{}_{-n}\mathrm C_r = \left( -1 \right)^r {}_n\mathrm H_r[7] 사실 조합을 부분곱으로 나타낸 식을 보면 알겠지만 애초에 그 식에서는 nn이 복소수여도 상관이 없다. 테일러 급수의 예 문서 참조

라이선스를 별도로 명시하지 않은 문서는 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다.
기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.

문서의 기여자는 역사 탭에서 확인할 수 있습니다.
접두어의 N: - 나무위키 사용자, R: - 리그베다 위키의 사용자를 뜻합니다.
자세한 사항은 나무위키에서 동일한 문서의 역사를 참고하시기 바랍니다.