조합

분류

이산수학

이 문서는 수학 용어를 다룹니다. 집단의 일종 중 민법의 규율에 대한 내용은 조합(민법) 문서

, 서구 역사속 단체에 대한 내용은 길드 문서

참고하십시오.

이산수학
Discrete Mathematics

[ 펼치기 · 접기 ]

이론
기본 대상	수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열	등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합	경우의 수(공식) · 순열(완전순열 · 염주순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프	수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타
P-NP 문제^미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설^미해결 · 콜라츠 추측^미해결 · 시행착오 (예상과 확인) · 불 논리 · 브라에스 역설
관련 문서
논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학

1. 개요

2. 상세

3. 다양한 표기 기호

4. 중복 조합

5. 조합의 성질

6. 예시

7. 관련 문서

1 . 개요[편집]

組合 / binomial coefficient

조합이란 [math(n)]개의 원소를 갖는 집합에서 [math(r)]개의 원소를 선택하는 것 혹은 선택의 결과로 정의된다.

어떤 순서로 원소를 선택했는지는 중요하지 않기에 순열(permutation)과는 다른 개념이다.[1]

집합의 크기^{원소의 개수}가 [math(n)]인 집합 [math(S)]에 대해[2]가 갖는 [math(r)]-부분집합[3]의 개수는 이항계수(binomial coefficient)와 같으며, 각 부분집합을 [math(n)]개에서 [math(r)]개를 택하는 조합(combination)이라고 한다.

순열과 마찬가지로 뭔가 거창한 정의가 붙었지만 실상은 초등학교에서부터 풀어온 경우의 수를 좀 더 수학적으로 나타낸 것뿐이다. 다만 계산하는 것은 조금 더 까다로워졌다. 계산하는 공식을 예시를 통해 유도해보자. [math(3)]명중에서 대표 [math(2)]명을 뽑는 상황을 생각하면[4], 순열을 쓸 경우 [math(\rm{}_3P_2=3\times2=6)]이 되는데, 순열의 경우의 수는 '[math(3)]명중에서 대표 [math(2)]명을 뽑아서 순서대로 나열하는 경우의 수'이므로 '나열하는 조작'을 배제해주면 되고, 같은 것이 있는 경우의 순열과 비슷하게 [math(2)]명의 대표가 같으므로 [math(2!)]로 나눠주면 된다. 따라서 [math(\rm\dbinom 3 2=\dfrac{{}_3P_2}{2!})]임을 알 수 있다. 일반적인 경우는 다음과 같다.

[math(\begin{aligned}\displaystyle {}_n{\rm C}_r&=\frac{{}_n{\rm P}_r}{r!}=\frac1{r!}\frac{n!}{(n-r)!} = \frac 1{r!} \prod_{i=0}^{r-1}(n-i) = \frac{n(n-1)( n-2) \cdots\cdots (n-r+1)}{r!} \\ &= \frac{\Gamma(n+1)}{\Gamma(n-r+1) \Gamma(r+1)}\end{aligned})]

좀 더 쉽게 말하면, [math(r)]개의 원소를 갖는 어떤 조합 (어떤 [math(r)]-부분 집합)에서의 가능한 순열의 수가 [math(r!)]이고, 각 조합(다른 조합은 다른 원소 구성을 가진다.)의 모든 순열의 경우를 다 더한 결과가 [math(n)]개에서 [math(r)]개를 선택하는 순열의 경우의 수이기에 위 수식의 첫번째 등식이 성립한다.
순열과 마찬가지로 조합 역시 팩토리얼 및 감마 함수로 정의할 수 있기 때문에 [math(r=0)]이어도 무방하다.

3 . 다양한 표기 기호[편집]

[math(n)]개의 원소를 갖는 집합에서 [math(r)]개의 원소를 선택하는 경우의 수를 의미하는, 이항계수는 기호는 다음이 대표적이다.
특히 [math(\rm C)]를 쓰는 방식에서는 영어 combination의 머리글자를 쓴다.

[math({}_n{\rm C}_r)][5]
대표적인 표기법이다. 실제로 [math(n)]의 위치는 [math(r)] 자리를 빼고 [math(\rm C)] 앞이나 뒤, 위첨자 아래첨자 모두 가능하나, n이 앞의 위첨자로 쓰는 일은 드물다.
[math(C(n,\,r))]
[math(\dbinom nr)]

한국의 고등학교 과정에서는 [math({}_n{\rm C}_r)]이 쓰이지만 세계적으로는 [math(\dbinom nr)]이 많이 쓰인다.[6] 참고로 수학 스택익스체인지에 올라온 질문글 답변에 따르면 [math(\dbinom nr)]가 여러 개의 조합식을 써냈을 때 가독성이 가장 좋다고 한다. 다만 1×2 행렬과 혼동할 여지가 있어 행렬 쪽은 보통 대괄호를 쓴다.

[math(C(n,\,r))] 은 n choose r 이라고 읽는다.

4 . 중복 조합[편집]

重複組合 / multiset coefficient

조합과 마찬가지로 [math(n)]개의 원소에서 [math(r)]개를 순서에 상관없이 뽑는데, 중복을 허락할 때의 가짓수이다. 기호로는 [math(\left(\!\!\dbinom{n}{r}\!\!\right))] 또는 [math(M(n,\,r))], [math((\varphi))]#을 쓰며, 한국과 일본에서는 [math({}_n{\rm H}_r)]도 통한다.[7] [math(\rm H)]라는 기호는 동차 단항식(homogeneous monomial) 또는 동차곱(homogeneous product)의 'homogeneous'에서 딴 것이다.# 집합론에서 중복집합을 다룰 때에도 등장한다.[8]

중복 조합의 가짓수를 실제로 구하려고 해보면 순열이나 위의 조합과는 다르게 훨씬 복잡함을 알 수 있다.[9] 계산공식을 유도하는 과정은 보통 "원([math(●)])"과 "막대기([math(|)])"를[10] 사용해서 설명한다. 예를 들어 숫자 [math(1)], [math(2)], [math(3)]중 중복을 허락하여 [math(5)]개를 뽑는 경우의 수를 생각해보자. 일단 [math(5)]개를 뽑으므로 원 [math(5)]개를 나란히 그린다([math(●●●●●)]). 이제 이 [math(5)]개의 원 사이에 막대기를 집어넣어 [math(3)]그룹으로 나누는데 이 '그룹'이 곧 주어진 원소의 종류 [math(\boldsymbol n)]개를 의미한다. 이를테면 [math(11233 \to ●●|●|●●)], [math(11133 \to ●●●||●●)], [math(22223 \to |●●●●|●)]으로 나타낼 수 있으므로, 특정 원소를 뽑지 않는 경우는 막대기가 중복되어 나열되는 경우로 간주할 수 있다. [math(3)]그룹으로 나누기 위해 필요한 막대기의 수는 [math((3-1) = 2)]개이고, 나눠진 각 그룹에 있는 원의 수를 각각 숫자 [math(1)], [math(2)], [math(3)]을 뽑는 개수라고하면 구하고자 하는 값이 나온다. 즉 총 가짓수는 [math(5)]개의 원과 [math(2)]개의 막대기를 나열하는 가짓수와 같고, 이는 [math(7)]개의 칸중 막대기를 그릴 [math(2)]개의 칸을 정하는 것과 동일하다.[11] 즉, [math(\rm{}_{5+3-1}C_2= {}_7C_2)]가 답. 일반적인 경우는 다음과 같다.

[math(\begin{aligned}{}_n{\rm H}_r &= {}_{r+(n-1)}{\rm C}_r = {}_{n+r-1}{\rm C}_{n-1} \\ &= \frac{(n+r-1)!}{(n-1)!r!} = \frac1{r!} \prod_{i=0}^{r-1}(n+i) = \frac{n(n+1)(n+2) \cdots\cdots (n+r-1)}{r!} \\ &= \frac{\Gamma(n+r)}{\Gamma(n) \Gamma(r+1)} \end{aligned})]

하강 계승(순열)으로 정의되는 조합과 비슷하게, 상승 계승을 이용하면 조합을 이용한 정의보다 더 깔끔한 정의가 가능하다.

[math({}_n{\rm H}_r = \dfrac{n^{\overline r}}{r!})]

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

파인트([math(3)]가지): [math(\rm{}_{31}H_3 = {}_{3+31-1}C_3= {}_{33}C_3=5456)]가지.
쿼터([math(4)]가지): [math(\rm{}_{31}H_4 = {}_{4+31-1}C_4= {}_{34}C_4=46376)]가지.
패밀리([math(5)]가지): [math(\rm{}_{31}H_5 = {}_{5+31-1}C_5= {}_{35}C_5=324632)]가지.
하프갤런([math(6)]가지): [math(\rm{}_{31}H_6 = {}_{6+31-1}C_6= {}_{36}C_6=1947792)]가지.

반면에 중복을 허락하지 않을 경우엔 일반적인 조합과 같아진다.
파인트([math(3)]가지): [math(\rm{}_{31}C_3=4495)]가지.
쿼터([math(4)]가지): [math(\rm{}_{31}C_4=31465)]가지.
패밀리([math(5)]가지): [math(\rm{}_{31}C_5=169911)]가지.
하프갤런([math(6)]가지): [math(\rm{}_{31}C_6=736281)]가지.

언뜻 보기에 조합의 특수한 경우로밖에 안 보이지만 사실 아주 중요한 성질이 있다. 부분곱으로 나타낸 중복 조합식의 [math(n)]에 [math(-n)]을 대입하면 다음과 같이 식이 변형되면서 조합에 관한 식으로 바뀐다.

[math(\displaystyle {}_{-n}{\rm H}_r = \frac 1{r!} \prod_{i=0}^{r-1}(-n+i) = \frac{(-1)^r}{r!} \prod_{i=0}^{r-1}(n-i) = (-1)^r {}_n{\rm C}_r)]

이를 달리 표현하면 중복 조합은 조합에서 [math(n)]이 음수인 경우로 볼 수 있고[12] [math(n)]의 범위를 모든 정수로 확장[13]해주는 성질이 있음을 알 수 있다.

5 . 조합의 성질[편집]

[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)]개중 한 개를 고정, A라고 한다. 이제 [math(n)]개중 [math(r)]개를 뽑는 가짓수는 A를 뽑는 경우와 뽑지 않는 2가지로 나눠지고, 각각의 가짓수는 [math({}_{n-1}{\rm C}_{r-1})], [math({}_{n-1}{\rm C}_r)]이다. 역시 직접 전개하여 증명할 수도 있다. 이를 고등학교 교육과정에서는 '포함 배제의 원리'라고 한다.
이항정리 참조.
- [math(p \in {\mathbb P})]이고 [math(r \in {\mathbb Z}_p)]인 경우, [math(\dbinom pr = \begin{cases} 1 & \left(\dbinom pr = 1\right) \\ 0 & \left(\dbinom pr > 1\right) \end{cases})]

6 . 예시[편집]

조합

남녀 각각 [math(5)]명 중에서 남자 [math(3)]명, 여자 [math(2)]명을 뽑아 원탁에 앉히는 가짓수는?

남자 [math(3)]명을 뽑는 수는 [math(\rm{}_5C_3=10)], 여자 [math(2)]명을 뽑는 수는 [math(\rm{}_5C_2=10)]. 곱의 법칙에 의해 전체 가짓수는 [math(10\times10=100)]. 이 [math(5)]명을 원탁에 앉히므로, 원순열에 의해 [math(100\times\left(5-1\right)!=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(\rm{}_4H_3={}_6C_3=20)].

7 . 관련 문서[편집]

이 문서의 내용 중 전체 또는 일부는 2023-12-17 05:04:37에 나무위키 조합 문서에서 가져왔습니다.

[1] 순열(permutation)은 [math(n)]개의 원소를 갖는 집합에서 [math(r)]개의 원소를 선택하는 것 혹은 그 결과이지만 선택의 순서가 중요하다. 같은 원소들을 선택했더라도 선택의 순서가 다르다면 다른 순열이지만, 조합은 어떤 순서로 선택을 하던 같은 원소들만 선택했다면 같은 조합이다.[2] 이 때 [math(|S|=n)]라고 적는다.[3] [math(r)]개의 원소를 갖는 부분집합이라는 의미이다.[4] 어떤 순서로 사람들을 대표로 뽑는 지는 중요하지 않고,어떤 사람들을 대표로 뽑았는가가 중요하기 때문에 선택의 순서가 중요한 순열이 아니라 조합의 경우의 수를 계산해야 한다.[5] 대표적인 표기법이다. 실제로 [math(n)]의 위치는 [math(r)] 자리를 빼고 [math(\rm C)] 앞이나 뒤, 위첨자 아래첨자 모두 가능하나, n이 앞의 위첨자로 쓰는 일은 드물다. [6] 울프럼알파에서는 nCr도 인식한다.[7] 조합 기호를 이용해서 나타낼 수 있기 때문에 국가에 따라서는 따로 기호를 만들어 쓰지 않는 경우가 많고 별도의 기호가 있다 하더라도 국가마다 제각각이다.[8] 여기서는 중복집합(계)수로 부르는 것이 일반적이다.[9] 중복 순열보다도 훨씬 복잡한데, 서로 다른 [math(n)]종류의 원소에서 특정 원소를 고르지 않는 경우까지 포함하기 때문이다. 이를테면 A, B, C에서 중복을 허용하여 4개를 뽑는 경우의 수 중엔 AAAC처럼 B가 포함되지 않는 경우도 포함된다.[10] 혹은 비슷한 다른 무언가. 칸막이라는 표현도 쓴다.[11] [math(7)]개의 칸중 막대기를 그리지 않을 [math(5)]개의 칸을 정하는 것으로 생각할 수도 있다.[12] 엄밀히 따지면 [math({}_{-n}{\rm C}_r = (-1)^r {}_n{\rm H}_r)][13] 사실 조합을 부분곱으로 나타낸 식을 보면 알겠지만 애초에 그 식에서는 [math(n)]이 복소수여도 상관이 없다. 테일러 급수의 예 문서 참조

조합

분류

1. 개요[편집]

2. 상세[편집]

3. 다양한 표기 기호[편집]

4. 중복 조합[편집]

5. 조합의 성질[편집]

6. 예시[편집]

7. 관련 문서[편집]

관련 문서