조합: 두 판 사이의 차이
Wandookong1729 (토론 | 기여) 잔글편집 요약 없음 태그: m 모바일 앱 iOS 앱 편집 |
잔글 Wandookong1729(토론)의 23770980판 편집을 되돌림 |
||
4번째 줄: | 4번째 줄: | ||
== 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>는 콤비네이션이라고 읽기도 한다. |
||
그 값은 <math> {n choose k} = |
그 값은 <math> {n \choose k} = \frac{P(n,k)}{k!} = \frac{n!}{k! \cdot (n-k)!}</math>이다. |
||
예를 들어, 10개 중에서 3개를 뽑는 경우의 수는 <math>{10 choose 3}= |
예를 들어, 10개 중에서 3개를 뽑는 경우의 수는 <math>{10 \choose 3}=\frac{10!}{3!\cdot 7!} = \frac{10\cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120</math>이다. |
||
=== 성질 === |
=== 성질 === |
||
* <math>{n choose k} = {n choose n-k}</math> |
* <math>{n \choose k} = {n \choose n-k}</math> |
||
{| class="wikitable collapsible collapsed" |
{| class="wikitable collapsible collapsed" |
||
|- |
|- |
||
! 증명 |
! 증명 |
||
|- |
|- |
||
| <math>{n choose k} = |
| <math>{n \choose k} = \frac{n!}{k! \cdot (n-k)!} = \frac{n!}{(n-k)! \cdot [n-(n-k)]!} = {n \choose n-k}</math> |
||
</br>이 성질을 직관적으로 보일 수도 있다. n명 중 A그룹에 들어갈 k명을 뽑는 가짓수는 n명중 A그룹에 들어가지 않을 n-k명을 뽑는 가짓수와 동일하다. |
</br>이 성질을 직관적으로 보일 수도 있다. n명 중 A그룹에 들어갈 k명을 뽑는 가짓수는 n명중 A그룹에 들어가지 않을 n-k명을 뽑는 가짓수와 동일하다. |
||
|} |
|} |
||
* <math>{n choose k} = {{n-1} choose {k-1}} + {{n-1} choose k}</math> |
* <math>{n \choose k} = {{n-1} \choose {k-1}} + {{n-1} \choose k}</math> |
||
증명: n명중 B라는 사람을 우선 빼놓고 생각하자. 그렇다면 |
증명: n명중 B라는 사람을 우선 빼놓고 생각하자. 그렇다면 |
||
: n명중 A그룹에 들어갈 k명을 고르는 가짓수 = B를 무조건 A그룹에 포함하는 경우 + B를 무조건 배제하는 경우 = n-1명 중 k-1명 선정 + n-1명 중 k명 선정을 하는 가짓수이다. |
: n명중 A그룹에 들어갈 k명을 고르는 가짓수 = B를 무조건 A그룹에 포함하는 경우 + B를 무조건 배제하는 경우 = n-1명 중 k-1명 선정 + n-1명 중 k명 선정을 하는 가짓수이다. |
||
: 2015년 개정 고등수학 교육과정에서 행렬은 빠졌다고 한다. |
|||
== 중복조합 == |
== 중복조합 == |
2019년 3월 8일 (금) 00:36 판
조합론에서, 조합(組合, 문화어: 무이, 영어: combination)은 집합에서 일부 원소를 취해 부분집합을 만드는 방법을 말한다. 그 경우의 수는 이항계수이다.
n개의 원소의 k-조합
개의 원소를 가지는 집합에서 개의 부분집합을 고르는 조합의 경우의 수를 이항계수라 하며, 나 또는 로 나타낸다. 기호 는 콤비네이션이라고 읽기도 한다.
그 값은 이다.
예를 들어, 10개 중에서 3개를 뽑는 경우의 수는 이다.
성질
증명 |
---|
|
증명: n명중 B라는 사람을 우선 빼놓고 생각하자. 그렇다면
- n명중 A그룹에 들어갈 k명을 고르는 가짓수 = B를 무조건 A그룹에 포함하는 경우 + B를 무조건 배제하는 경우 = n-1명 중 k-1명 선정 + n-1명 중 k명 선정을 하는 가짓수이다.
- 2015년 개정 고등수학 교육과정에서 행렬은 빠졌다고 한다.
중복조합
중복조합(重複組合, 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이 된다.
외부 링크
- “Combination”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. “Combination”. 《Wolfram MathWorld》 (영어). Wolfram Research.