조합: 두 판 사이의 차이

위키백과, 우리 모두의 백과사전.
내용 삭제됨 내용 추가됨
편집 요약 없음
편집 요약 없음
태그: m 모바일 웹
1번째 줄: 1번째 줄:
{{다른 뜻}}
{{다른 뜻}}


[[조합론]]에서, '''조합'''(組合, {{문화어|무이}}, {{llang|en|combination}})은 [[집합]]에서 일부 원소를 취해 [[부분집합]]을 만드는 방법을 말한다. 그 경우의 수는 [[이항계수]]이다.
[[조합론]]에서, '''조합'''(組合, {{문화어|무이}}, {{llang|en|combination}})은 [[집합]]에서 서로 다른 n개의 원소 중에서 순서와 상관없이 r개를 고르는 것이다. 그 경우의 수는 [[이항계수]]이다.
안녕하세요 선생님.
== n개의 원소의 k-조합 ==
== n개의 원소의 k-조합 ==
<math>n</math>개의 원소를 가지는 집합에서 <math>k</math>개의 부분집합을 고르는 조합의 경우의 수를 [[이항계수]]라 하며, <math>_{n}C_{k}\;</math>나<math>\; ^{n}C_{k}\;,\; C_{n,k}\;, C(n,k)\;,</math> 또는 <math>{n \choose k}</math>로 나타낸다. 기호 <math>\;C\;</math>는 콤비네이션이라고 읽기도 한다.
<math>n</math>개의 원소를 가지는 집합에서 <math>k</math>개의 부분집합을 고르는 조합의 경우의 수를 [[이항계수]]라 하며, <math>_{n}C_{k}\;</math>나<math>\; ^{n}C_{k}\;,\; C_{n,k}\;, C(n,k)\;,</math> 또는 <math>{n \choose k}</math>로 나타낸다. 기호 <math>\;C\;</math>는 콤비네이션이라고 읽기도 한다.

2020년 1월 6일 (월) 18:40 판

조합론에서, 조합(組合, 문화어: 무이, 영어: combination)은 집합에서 서로 다른 n개의 원소 중에서 순서와 상관없이 r개를 고르는 것이다. 그 경우의 수는 이항계수이다.

n개의 원소의 k-조합

개의 원소를 가지는 집합에서 개의 부분집합을 고르는 조합의 경우의 수를 이항계수라 하며, 또는 로 나타낸다. 기호 는 콤비네이션이라고 읽기도 한다.

그 값은 이다.

예를 들어, 10개 중에서 3개를 뽑는 경우의 수는 이다.

성질

증명: n명중 B라는 사람을 우선 빼놓고 생각하자. 그렇다면

n명중 A그룹에 들어갈 k명을 고르는 가짓수 = B를 무조건 A그룹에 포함하는 경우 + B를 무조건 배제하는 경우 = n-1명 중 k-1명 선정 + n-1명 중 k명 선정을 하는 가짓수이다.

중복조합

중복조합(重複組合, combination with repetition)은 서로 다른 개의 원소에서 중복을 허락하여 개를 뽑는 경우의 수이다. 이는 크기가 인 집합에서, 크기가 중복집합을 고를 수 있는 가짓수와 같다. 기호로는 또는 nHk로 표기하며, 그 값은 nHk = k+(n-1)Ck 이다.

예를 들어, 세개의 문자 A,B,C에서 중복을 허용하여 5개를 뽑는 경우의 수는 3H5 = 7C5 = 21이므로 21가지가 된다.

성질

중복조합에서 다음이 성립한다.



단,

공식 유도

모든 경우를 직접 나열하는 방법으로 중복조합의 공식을 유도할 수도 있으나, 여기서는 다른 방법으로 설명한다. 중복조합 개의 원소들을 순서에 상관없이 나열하는 것이므로, 개의 빈칸에 중복을 허용하여 개의 원소를 넣는 개수를 구하는 문제로 생각할 수 있다. 여기에 가지의 경우로 구분할 수 있는 원소들을 순서에 상관없이 집어 넣어야 하므로, 개의 칸막이를 두고 가지 경우를 임의의 순서로 배열한다고 할 수 있다.

예를 들어 칸막이 기호를 /로 나타낸다면, 위의 예제에서 "A B B B C"는 "A / B B B / C"에 해당하고 "A B C C C"는 "A / B / C C C"에 해당한다.

물론 칸막이 사이에 아무 원소도 없을 수도 있는데, 이것은 그 원소가 선택되지 않은 경우에 해당한다. 예를 들어 위의 예제에서 "A A A C C"는 "A A A / / C C"에 해당하고 "B B C C C"는 "/ B B / C C C"에 해당한다.

이제 중복조합의 문제는 원래 문자가 들어갈 개의 빈칸과 개의 칸막이가 들어갈 빈칸을 모두 합한 개의 빈칸에서, 칸막이가 들어갈 개의 칸을 선택하는 문제로 변형되었다. 결국 중복조합의 경우의 수 nHk = n+k-1Cn-1이 된다. 한편, 이항계수의 성질에서 nHk = n+k-1Ck이 된다.

외부 링크

같이 보기