"중복조합의 공식 H(n,r)=C(n+r-1,r)"의 두 판 사이의 차이

2009년 12월 7일 (월) 12:14 판

중복조합
- 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것
- 1과 2에서 세 개를 취하는 중복조합은 111, 112, 122, 222의 네 가지가 있음.
- n개 중에서 r개를 선택하는 중복조합의 개수를 이라고 쓰자. \(_n C_r = {n\choose r} \)즉, H(2,3)=4.
  H(2,3) = C(2+3-1,3)=C(4,3)=4 임을 확인할 수 있다.
중복조합의 공식

증명의 아이디어를 이해하기 위해, H(4,2)의 예를 들어보자
1,2,3,4 중에서 뽑는 것으로 하면, 중복해서 두 개를 뽑는 방법은 다음과 같이 열 가지가 있음.
- 11,12,13,14,22,23,24,33,34,44
이제 이 중복조합에서 첫번째 것은 내버려 두고, 두번째 수에 1을 더하면 다음과 같은 결과를 얻음.
- 12,13,14,15,23,24,25,34,35,45
- 이것은 1부터 5까지 중에서 2개를 선택하는 방법과 같아짐.
그러므로, H(4,2)=C(5,2)

또다른 예. H(2,3)의 계산.
1,2 중에서 세 가지를 택하는 중복조합은 다음과 같음.
- 111,112,122,222
위에서 한 것처럼 첫번째 것은 내버려 두고, 두번째 것에 1, 세번째 것에 2를 더해 보면, 다음을 얻게 됨
- 123,124,134,234
- 이 경우는 1,2,3,4 중에서 세 개를 뽑는 조합과 일치함.
그러므로, H(2,3)=C(4,3)

@@ 1번째 줄: / 1번째 줄: @@
-<h5>간단한 소개</h5>
+<h5>개요</h5>
-*  조합<br>
-** 여러 개의 원소 중에서 몇 개를 순서에 관계없이 뽑아내는 것
-** 가령 1,2,3,4 네 개의 수 가운데서 세 개씩 뽑아 모은 조합은 123, 124, 134, 234 의 네 가지
-** n개 중에서 r개를 선택하는 조합의 개수를  <math>_n C_r = {n\choose r} </math>로 표현함
-**  즉, <math>_4 C_3 = {4\choose 3} =4</math> 가 됨.<br>
-**  일반적으로 <math>_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}</math> 공식을 통해 구할수 있음.<br>  <br>
 *  중복조합<br>
 ** 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것
@@ 12번째 줄: / 6번째 줄: @@
 ** n개 중에서 r개를 선택하는 중복조합의 개수를 이라고 쓰자. <math>_n C_r = {n\choose r} </math>즉, H(2,3)=4.<br> H(2,3) = C(2+3-1,3)=C(4,3)=4 임을 확인할 수 있다.
 * 중복조합의 공식
+<h5>조합과의</h5>
@@ 55번째 줄: / 57번째 줄: @@
 <h5>관련된 다른 주제들</h5>
-* [[search?q=%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98&parent id=2611580|이항계수]]
+* [[이항계수와 조합|이항계수]][[#]]
-* [[#]]
+* [[일대일대응]]