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

수학노트
둘러보기로 가기 검색하러 가기
12번째 줄: 12번째 줄:
 
** 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것
 
** 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것
 
** 1과 2에서 세 개를 취하는 중복조합은 111, 112, 122, 222의 네 가지가 있음.
 
** 1과 2에서 세 개를 취하는 중복조합은 111, 112, 122, 222의 네 가지가 있음.
−
* n개 중에서 r개를 선택하는 중복조합의 개수를 <math>\textstyle\left\langle{n\atop r}\right\rangle</math>이라고 쓰자. <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 임을 확인할 수 있다.
+
* n개 중에서 r개를 선택하는 중복조합의 개수를 <math>_n H_r=\textstyle\left\langle{n\atop r}\right\rangle</math> 로 나타낸다.
  
 
 
 
 
30번째 줄: 30번째 줄:
 
 
 
 
  
−
<h5>중복조합의 공식</h5>
+
<h5>중복조합의 공식 증명 1</h5>
  
 
*  중복조합의 공식<br><math>_n H_r=_{n+r-1}C_{r}</math><br>
 
*  중복조합의 공식<br><math>_n H_r=_{n+r-1}C_{r}</math><br>
56번째 줄: 56번째 줄:
 
 
 
 
  
−
<h5>예2</h5>
+
<h5>중복조합의 공식 증명 2</h5>
  
−
examples of multiset computation
+
* n=4, r=18 인 경우
 +
* 집합을  <math>\{a,b,c,d\}</math> 로 두자.
 +
*  a가 6개, b가 2개, c가 3개, d가 7개 있는 경우를 아래처럼 나타내자.<br><math>\{a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d \}</math><br><math>\bullet \bullet \bullet \bullet \bullet \bullet \mid \bullet \bullet \mid \bullet \bullet \bullet \mid \bullet \bullet \bullet \bullet \bullet \bullet \bullet </math><br>
 +
* 그림에서 점과 막대를 다 합하여 총 4+18-1=21 개가 있는데, 이 21개의 위치에서 18개를 선택하여 a,b,c,d를 배열하는 중복조합과 일대일대응된다.
  
−
(n=4, k=18)
+
 
−
 
 
−
set \{a,b,c,d}
 
−
 
 
−
multiset \{<em>a</em>, <em>a</em>, <em>a</em>, <em>a</em>, <em>a</em>, <em>a</em>, <em>b</em>, <em>b</em>, <em>c</em>, <em>c</em>, <em>c</em>, <em>d</em>, <em>d</em>, <em>d</em>, <em>d</em>, <em>d</em>, <em>d</em>, <em>d</em> \} (6 <em>a</em>s, 2 <em>b</em>s, 3 <em>c</em>s, 7 <em>d</em>s) in this form: 
 
−
 
 
−
: <math>\bullet \bullet \bullet \bullet \bullet \bullet \mid \bullet \bullet \mid \bullet \bullet \bullet \mid \bullet \bullet \bullet \bullet \bullet \bullet \bullet </math>
 
  
 
 
 
 
73번째 줄: 70번째 줄:
  
 
* [[생성함수]]
 
* [[생성함수]]
−
* multiset generating function
 
 
* { {}, {x}, {x,x}, {x,x,x}, ... } gives S = 1 + x + x2 + x3 + ... = 1 + xS which is formally S=1/(1-x)
 
* { {}, {x}, {x,x}, {x,x,x}, ... } gives S = 1 + x + x2 + x3 + ... = 1 + xS which is formally S=1/(1-x)
 
* (1 − <em>x</em>)<sup>−1</sup>·(1 − <em>y</em>)<sup>−1</sup> = 1 + (<em>x</em> + <em>y</em>) + (<em>x</em><sup>2</sup> + <em>x·y</em> + <em>y</em><sup>2</sup>) +(<em>x</em><sup>3</sup> + <em>x</em><sup>2</sup><em>·y</em> + <em>x</em><em>y</em><sup>2</sup>+<em>y</em><sup>3</sup>)+...
 
* (1 − <em>x</em>)<sup>−1</sup>·(1 − <em>y</em>)<sup>−1</sup> = 1 + (<em>x</em> + <em>y</em>) + (<em>x</em><sup>2</sup> + <em>x·y</em> + <em>y</em><sup>2</sup>) +(<em>x</em><sup>3</sup> + <em>x</em><sup>2</sup><em>·y</em> + <em>x</em><em>y</em><sup>2</sup>+<em>y</em><sup>3</sup>)+...
89번째 줄: 85번째 줄:
 
*  자연수 r에 대하여, 다음 부정방정식의  <math>x_i \geq 0</math>인 정수해의 개수를 구해보자<br><math>x_0+x_1+x_2+\cdots+x_n=r</math><br>
 
*  자연수 r에 대하여, 다음 부정방정식의  <math>x_i \geq 0</math>인 정수해의 개수를 구해보자<br><math>x_0+x_1+x_2+\cdots+x_n=r</math><br>
 
*  해의 개수는 n+1개의 원소를 가지고 r개를 뽑는 중복조합의 수와 같다. 즉, 해의 개수는 다음과 같다<br><math>_{n+1} H_r=_{n+r}C_{r}=_{n+r}C_{n}</math><br>
 
*  해의 개수는 n+1개의 원소를 가지고 r개를 뽑는 중복조합의 수와 같다. 즉, 해의 개수는 다음과 같다<br><math>_{n+1} H_r=_{n+r}C_{r}=_{n+r}C_{n}</math><br>
−
 
−
 
 
−
 
−
<math>\sum_{k}\left\langle        \begin{matrix}  3  \\  4        \end{matrix}    \right\rangle  x^k</math>
 
−
 
−
<math>\sum_{k} \textstyle\left\langle{n\atop k}\right\rangle x^k</math>
 
−
 
−
http://en.wikipedia.org/wiki/Multiset
 
−
 
−
[http://en.wikipedia.org/wiki/Bose%E2%80%93Einstein_statistics http://en.wikipedia.org/wiki/Bose–Einstein_statistcs]
 
−
 
−
 
 
  
 
 
 
 
130번째 줄: 114번째 줄:
  
 
<h5 style="line-height: 3.428em; margin: 0px; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">메모</h5>
 
<h5 style="line-height: 3.428em; margin: 0px; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">메모</h5>
 +
 +
<math>\sum_{k}\left\langle        \begin{matrix}  3  \\  4        \end{matrix}    \right\rangle  x^k</math>
 +
 +
<math>\sum_{k} \textstyle\left\langle{n\atop k}\right\rangle x^k</math>
 +
 +
 
  
 
 
 
 
163번째 줄: 153번째 줄:
 
* http://ko.wikipedia.org/wiki/
 
* http://ko.wikipedia.org/wiki/
 
* http://en.wikipedia.org/wiki/Multiset
 
* http://en.wikipedia.org/wiki/Multiset
−
 
−
 
 
  
 
* [http://en.wikipedia.org/wiki/Bose%E2%80%93Einstein_statistics http://en.wikipedia.org/wiki/Bose–Einstein_statistics]
 
* [http://en.wikipedia.org/wiki/Bose%E2%80%93Einstein_statistics http://en.wikipedia.org/wiki/Bose–Einstein_statistics]

2011년 1월 22일 (토) 12:41 판

이 항목의 스프링노트 원문주소

 

 

개요
  • 중복조합
    • 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것
    • 1과 2에서 세 개를 취하는 중복조합은 111, 112, 122, 222의 네 가지가 있음.
  • n개 중에서 r개를 선택하는 중복조합의 개수를 \(_n H_r=\textstyle\left\langle{n\atop r}\right\rangle\) 로 나타낸다.

 

 

조합과의 비교
  • 조합은 여러 개의 원소 중에서 몇 개를 순서에 관계없이 뽑아내는 것
  • 가령 1,2,3,4 네 개의 수 가운데서 세 개씩 뽑아 모은 조합은 123, 124, 134, 234 의 네 가지
  • n개 중에서 r개를 선택하는 조합의 개수를  \(_n C_r = {n\choose r} \)로 표현함
  • 즉, \(_4 C_3 = {4\choose 3} =4\) 가 됨.
  • 일반적으로 \(_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}\) 공식을 통해 구할수 있음.

 

 

중복조합의 공식 증명 1
  • 중복조합의 공식
    \(_n H_r=_{n+r-1}C_{r}\)
  • 증명의 아이디어를 이해하기 위해, 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)
  • 특정한 조합과 특정한 중복조합 사이에 일대일대응이 존재하는 것을 보이는 것임.

 

 

중복조합의 공식 증명 2
  • n=4, r=18 인 경우
  • 집합을  \(\{a,b,c,d\}\) 로 두자.
  • a가 6개, b가 2개, c가 3개, d가 7개 있는 경우를 아래처럼 나타내자.
    \(\{a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d \}\)
    \(\bullet \bullet \bullet \bullet \bullet \bullet \mid \bullet \bullet \mid \bullet \bullet \bullet \mid \bullet \bullet \bullet \bullet \bullet \bullet \bullet \)
  • 그림에서 점과 막대를 다 합하여 총 4+18-1=21 개가 있는데, 이 21개의 위치에서 18개를 선택하여 a,b,c,d를 배열하는 중복조합과 일대일대응된다.

 

 

생성함수
  • 생성함수
  • { {}, {x}, {x,x}, {x,x,x}, ... } gives S = 1 + x + x2 + x3 + ... = 1 + xS which is formally S=1/(1-x)
  • (1 − x)−1·(1 − y)−1 = 1 + (x + y) + (x2 + x·y + y2) +(x3 + x2·y + xy2+y3)+...
  • (1 − x)−2 = 1 + (x + x) + (x2 + x·x + x2) + ...
  • n개의 원소에서 k개를 뽑는 중복조합의 생성함수는 다음과 같이 주어진다
    \(\frac{1}{(1-x)^n}=\sum_{k=0}^{\infty}\textstyle\left\langle{n\atop k}\right\rangle x^k\)
    \(=\sum_{k=0}^{\infty}\frac{(n)_k}{k!}x^k=1+nx+\frac{n(n+1)}{2!}x^2+\frac{n(n+1)(n+2)}{3!}x^3+\cdots\)

 

 

부정방정식에의 응용
  • 자연수 r에 대하여, 다음 부정방정식의  \(x_i \geq 0\)인 정수해의 개수를 구해보자
    \(x_0+x_1+x_2+\cdots+x_n=r\)
  • 해의 개수는 n+1개의 원소를 가지고 r개를 뽑는 중복조합의 수와 같다. 즉, 해의 개수는 다음과 같다
    \(_{n+1} H_r=_{n+r}C_{r}=_{n+r}C_{n}\)

 

 

재미있는 사실

 

 

 

역사

 

 

 

메모

\(\sum_{k}\left\langle \begin{matrix} 3 \\ 4 \end{matrix} \right\rangle x^k\)

\(\sum_{k} \textstyle\left\langle{n\atop k}\right\rangle x^k\)

 

 

 

관련된 항목들

 

 

수학용어번역

 

 

사전 형태의 자료

 

 

관련논문

 

 

관련도서

 

 

관련기사

 

 

블로그
원본 주소 "https://wiki.mathnt.net/index.php?title=중복조합의_공식_H(n,r)%3DC(n%2Br-1,r)&oldid=18619"