분류
1. 개요
기호로는 [math({}_nmathrm C_r)][1], [math( C(n, r))], [math(dbinom nr)]등이 있다. 여기서 C는 영어 combination의 머리글자이다. 한국의 고등학교 과정에서는 [math({}_nmathrm C_r)]이 쓰이지만 세계적으로는 [math(dbinom nr)]이 많이 쓰인다. [2]
순열과 마찬가지로 뭔가 거창한 정의가 붙었지만 실상은 초등학교에서부터 풀어온 경우의 수를 좀 더 수학적으로 나타낸 것뿐이다. 다만 계산하는 것은 조금 더 까다로워졌다. 계산하는 공식을 예시를 통해 유도해보자. [math(3)]명중에서 대표 [math(2)]명을 뽑는 상황을 가정하면, 순열을 쓸 경우 [math({}_3mathrm P_2=3times2=6)]이 되는데, 순열은 '[math(3)]명중에서 대표 [math(2)]명을 뽑아서 순서대로 나열하는 경우의 수'이므로 '나열하는 조작'을 배제해주면 되고 같은 것이 있는 경우의 순열과 비슷하게, [math(2)]명의 대표가 같으므로 [math(2!)]로 나눠주면 된다. 따라서, [math(dbinom 3 2=dfrac{{}_3mathrm P_2}{2!})]임을 알 수 있다. 일반적인 경우는 다음과 같다.
순열과 마찬가지로 뭔가 거창한 정의가 붙었지만 실상은 초등학교에서부터 풀어온 경우의 수를 좀 더 수학적으로 나타낸 것뿐이다. 다만 계산하는 것은 조금 더 까다로워졌다. 계산하는 공식을 예시를 통해 유도해보자. [math(3)]명중에서 대표 [math(2)]명을 뽑는 상황을 가정하면, 순열을 쓸 경우 [math({}_3mathrm P_2=3times2=6)]이 되는데, 순열은 '[math(3)]명중에서 대표 [math(2)]명을 뽑아서 순서대로 나열하는 경우의 수'이므로 '나열하는 조작'을 배제해주면 되고 같은 것이 있는 경우의 순열과 비슷하게, [math(2)]명의 대표가 같으므로 [math(2!)]로 나눠주면 된다. 따라서, [math(dbinom 3 2=dfrac{{}_3mathrm P_2}{2!})]임을 알 수 있다. 일반적인 경우는 다음과 같다.
[math(displaystyle {}_nmathrm C_r=frac{{}_nmathrm 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) cdotscdots left( n-r+1 right)}{r!})]
|
2. 중복 조합
조합과 마찬가지로 [math(n)]개의 원소에서 [math(r)]개를 순서에 상관없이 뽑는데, 중복을 허락할 때의 가짓수이다. 기호로는 [math(left(!!dbinom{n}{r}!!right))]을 쓰며, 한국과 일본에서는 [math({}_nmathrm H_r)]도 통한다.[3] [math(mathrm H)]라는 기호는 동차 단항식(Homogeneous monomial) 또는 동차곱(Homogeneous product)의 'Homogeneous'에서 딴 것이다.#
중복 조합의 가짓수를 실제로 구하려고 해보면 순열이나 위의 조합과는 다르게 훨씬 복잡함을 알 수 있다.[4]종류의 원소에서 특정 원소를 고르지 않는 경우까지 포함하기 때문이다. 이를테면 A, B, C에서 중복을 허용하여 4개를 뽑는 경우의 수 중엔 AAAC처럼 B가 포함되지 않는 경우도 포함된다.] 계산공식을 유도하는 과정은 보통 "원"과 "막대기"를[5] 사용해서 설명한다. 예를 들어 숫자 [math(1)], [math(2)], [math(3)]중 중복을 허락하여 [math(5)]개를 뽑는 경우의 수를 생각해보자. 일단 [math(5)]개를 뽑으므로 원 [math(5)]개를 나란히 그린다. 이제 이 [math(5)]개의 원 사이에 막대기를 집어넣어 [math(3)]그룹으로 나누는데 이 '그룹'이 곧 주어진 원소의 종류 [math(boldsymbol n)]개를 의미한다. 이를테면 [math(11233 to 11/2/33)]으로, [math(11133 to 111//33)]으로 나타낼 수 있으므로, 특정 원소를 뽑지 않는 경우는 막대기가 중복되어 나열되는 경우로 간주할 수 있다. [math(3)]그룹으로 나누기 위해 필요한 막대기의 수는 [math((3-1) = 2)]개이고, 나눠진 각 그룹에 있는 원의 수를 각각 숫자 [math(1)], [math(2)], [math(3)]을 뽑는 개수라고하면 구하고자 하는 값이 나온다. 즉 총 가짓수는 [math(5)]개의 원과 [math(2)]개의 막대기를 나열하는 가짓수와 같고, 이는 [math(7)]개의 칸중 막대기를 그릴 [math(2)]개의 칸을 정하는 것과 동일하다. 즉, [math({}_{5+3-1}mathrm C_2= {}_7mathrm C_2)]가 답. 일반적인 경우는 다음과 같다.
중복 조합의 가짓수를 실제로 구하려고 해보면 순열이나 위의 조합과는 다르게 훨씬 복잡함을 알 수 있다.[4]종류의 원소에서 특정 원소를 고르지 않는 경우까지 포함하기 때문이다. 이를테면 A, B, C에서 중복을 허용하여 4개를 뽑는 경우의 수 중엔 AAAC처럼 B가 포함되지 않는 경우도 포함된다.] 계산공식을 유도하는 과정은 보통 "원"과 "막대기"를[5] 사용해서 설명한다. 예를 들어 숫자 [math(1)], [math(2)], [math(3)]중 중복을 허락하여 [math(5)]개를 뽑는 경우의 수를 생각해보자. 일단 [math(5)]개를 뽑으므로 원 [math(5)]개를 나란히 그린다. 이제 이 [math(5)]개의 원 사이에 막대기를 집어넣어 [math(3)]그룹으로 나누는데 이 '그룹'이 곧 주어진 원소의 종류 [math(boldsymbol n)]개를 의미한다. 이를테면 [math(11233 to 11/2/33)]으로, [math(11133 to 111//33)]으로 나타낼 수 있으므로, 특정 원소를 뽑지 않는 경우는 막대기가 중복되어 나열되는 경우로 간주할 수 있다. [math(3)]그룹으로 나누기 위해 필요한 막대기의 수는 [math((3-1) = 2)]개이고, 나눠진 각 그룹에 있는 원의 수를 각각 숫자 [math(1)], [math(2)], [math(3)]을 뽑는 개수라고하면 구하고자 하는 값이 나온다. 즉 총 가짓수는 [math(5)]개의 원과 [math(2)]개의 막대기를 나열하는 가짓수와 같고, 이는 [math(7)]개의 칸중 막대기를 그릴 [math(2)]개의 칸을 정하는 것과 동일하다. 즉, [math({}_{5+3-1}mathrm C_2= {}_7mathrm C_2)]가 답. 일반적인 경우는 다음과 같다.
[math(begin{aligned} {}_nmathrm 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) cdotscdots left( n+r-1 right)}{r!} end{aligned})]
|
이를 응용하여 배스킨라빈스의 [math(31)]가지 아이스크림을 중복을 허락하여 고를 경우(ex. 쿼터 크기에 엄마는 외계인×2, 체리 쥬빌레, 아몬드봉봉 등)고를 수 있는 총 경우의 수는 다음과 같이 구할 수 있다.
파인트([math(3)]가지): [math({}_{31}mathrm H_3 = {}_{3+31-1}mathrm C_3= {}_{33}mathrm C_3=5456)]가지.
쿼터([math(4)]가지): [math({}_{31}mathrm H_4 = {}_{4+31-1}mathrm C_4= {}_{34}mathrm C_4=46376)]가지.
패밀리([math(5)]가지): [math({}_{31}mathrm H_5 = {}_{5+31-1}mathrm C_5= {}_{35}mathrm C_5=324632)]가지.
하프갤런([math(6)]가지): [math({}_{31}mathrm H_6 = {}_{6+31-1}mathrm C_6= {}_{36}mathrm C_6=1947792)]가지.
반면에 중복을 허락하지 않을 경우엔 일반적인 조합과 같아진다.
파인트([math(3)]가지): [math({}_{31}mathrm C_3=4495)]가지.
쿼터([math(4)]가지): [math({}_{31}mathrm C_4=31465)]가지.
패밀리([math(5)]가지): [math({}_{31}mathrm C_5=169911)]가지.
하프갤런([math(6)]가지): [math({}_{31}mathrm C_6=736281)]가지.
참고하면 좋은 블로그
언뜻 보기에 조합의 특수한 경우로밖에 안 보이지만 사실 아주 중요한 성질이 있다. 부분곱으로 나타낸 중복 조합식의 [math(n)]에 [math(-n)]을 대입하면 다음과 같이 식이 변형되면서 조합에 관한 식으로 바뀐다.
[math(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 {}_nmathrm C_r)]
|
3. 조합의 성질
- [math(dbinom nr= dbinom n {n-r})]: [math(n)]개중 [math(r)]개를 뽑는 것은 [math(n)]개중 [math((n-r))]개의 뽑지 않을 것을 고르는 것과 가짓수가 같다. 직접 전개하여 증명할 수도 있다.
- [math(dbinom nr =dbinom {n-1}r +dbinom {n-1}{r-1})]: [math(n)]개중 한 개를 고정한다. 이제 [math(n)]개중 [math(r)]개를 뽑는 가짓수는 그 한 개가 있는 경우와 없는 경우 2가지로 나눠지고, 각각의 가짓수는 [math({}_{n-1}mathrm C_{r-1})], [math({}_{n-1}mathrm C_r)]이다. 역시 직접 전개하여 증명할 수도 있다.
- 이항정리 참조.
4. 예시
조합
남녀 각각 [math(5)]명 중에서 남자 [math(3)]명, 여자 [math(2)]명을 뽑아 원탁에 앉히는 가짓수는?
남자 [math(3)]명을 뽑는 수는 [math({}_5mathrm C_3=10)], 여자 [math(2)]명을 뽑는 수는 [math({}_5mathrm C_2=10)]. 곱의 법칙에 의해 전체 가짓수는 [math(10times10=100)]. 이 [math(5)]명을 원탁에 앉히므로, 원순열에 의해 [math(100timesleft(5-1right)!=2400)]
|
중복 조합
음이 아닌 정수 [math(x)], [math(y)], [math(z)]에 대해, [math(x+y+z leq 3)]를 만족시키는 순서쌍 [math((x, y, z))]의 수는?
주어진 식을 [math(x+y+z=3-n (0 le n le 3))]으로 나타내면 이는 곧 음이 아닌 정수 [math(x)], [math(y)], [math(z)], [math(n)]에 대해 [math(x+y+z+n=3)]을 만족하는 식이며, 순서쌍 [math((x, y, z, n))]을 고르는 경우와 같다. 이는 [math(4)]개중 중복을 허락하여 [math(3)]개를 뽑는 가짓수와 동일하다. 즉, 구하고자 하는 답은 [math({}_4mathrm H_3={}_6mathrm C_3=20)].
|
5. 관련 문서
[1] 여기에서 n의 위치는 r 자리를 빼고 C 앞이나 뒤, 위첨자 아래첨자 모두 가능하다.[2] 울프럼알파에서는 nCr도 인식한다.[3] 조합 기호를 이용해서 나타낼 수 있기 때문에 국가에 따라서는 따로 기호를 만들어 쓰지 않는 경우가 많고 별도의 기호가 있다 하더라도 국가마다 제각각이다.[4] 중복 순열보다도 훨씬 복잡한데, 서로 다른 [math(n)[5] 혹은 비슷한 다른 무언가. 칸막이라는 표현도 쓴다.[6] 엄밀히 따지면 [math({}_{-n}mathrm C_r = left( -1 right)^r {}_nmathrm H_r)[7] 사실 조합을 부분곱으로 나타낸 식을 보면 알겠지만 애초에 그 식에서는 [math(n)