"중복조합의 공식 H(n,r)=C(n+r-1,r)"의 두 판 사이의 차이
둘러보기로 가기
검색하러 가기
Pythagoras0 (토론 | 기여) |
|||
| (사용자 4명의 중간 판 39개는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
| − | + | ==개요== | |
| − | + | * 중복조합 | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | * 중복조합 | ||
** 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것 | ** 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것 | ||
** 1과 2에서 세 개를 취하는 중복조합은 111, 112, 122, 222의 네 가지가 있음. | ** 1과 2에서 세 개를 취하는 중복조합은 111, 112, 122, 222의 네 가지가 있음. | ||
| − | + | * n개 중에서 r개를 선택하는 중복조합의 개수를 <math>_n H_r=\textstyle\left\langle{n\atop r}\right\rangle</math> 로 나타낸다. | |
| − | * | + | * 변수의 개수가 <math>n</math>이고, 차수가 <math>d</math>인 [[동차다항식(Homogeneous polynomial)]]이 이루는 벡터공간의 차원은 <math>_n H_d</math>이며, 중복조합의 H는 homogeneous에서 온 것이다 |
| + | * <math>n</math>차원 벡터공간 <math>V</math>에 대하여 [[대칭곱 (symmetric power)과 대칭텐서|대칭곱]] <math>\operatorname{Sym}^d V</math>의 차원은 <math>_n H_d</math>로 주어진다 | ||
| − | + | ==조합과의 비교== | |
| − | |||
| − | |||
| − | |||
| − | |||
* 조합은 여러 개의 원소 중에서 몇 개를 순서에 관계없이 뽑아내는 것 | * 조합은 여러 개의 원소 중에서 몇 개를 순서에 관계없이 뽑아내는 것 | ||
* 가령 1,2,3,4 네 개의 수 가운데서 세 개씩 뽑아 모은 조합은 123, 124, 134, 234 의 네 가지 | * 가령 1,2,3,4 네 개의 수 가운데서 세 개씩 뽑아 모은 조합은 123, 124, 134, 234 의 네 가지 | ||
| − | * n개 중에서 r개를 선택하는 조합의 | + | * n개 중에서 r개를 선택하는 조합의 개수를 <math>_n C_r = {n\choose r} </math>로 표현함 |
| − | * 즉, <math>_4 C_3 = {4\choose 3} =4</math> 가 됨. | + | * 즉, <math>_4 C_3 = {4\choose 3} =4</math> 가 됨. |
| − | * 일반적으로 <math>_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}</math> 공식을 통해 구할수 있음. | + | * 일반적으로 <math>_n C_r = {n\choose r} = {{n!} \over {r!(n - r)!}}</math> 공식을 통해 구할수 있음. |
| − | + | ||
| − | + | ||
| − | + | ==중복조합의 공식 증명 1== | |
| − | * 증명의 아이디어를 이해하기 위해, | + | * 중복조합의 공식:<math>_n H_r=_{n+r-1}C_{r}</math> |
| − | * 1,2,3,4 중에서 뽑는 것으로 하면, 중복해서 두 개를 뽑는 방법은 다음과 같이 열 가지가 있음. | + | |
| + | * 증명의 아이디어를 이해하기 위해, <math>_4 H_2</math>의 예를 들어보자 | ||
| + | * 1,2,3,4 중에서 뽑는 것으로 하면, 중복해서 두 개를 뽑는 방법은 다음과 같이 열 가지가 있음. | ||
** 11,12,13,14,22,23,24,33,34,44 | ** 11,12,13,14,22,23,24,33,34,44 | ||
| − | * 이제 이 중복조합에서 첫번째 것은 내버려 두고, 두번째 수에 1을 더하면 다음과 같은 결과를 얻음. | + | * 이제 이 중복조합에서 첫번째 것은 내버려 두고, 두번째 수에 1을 더하면 다음과 같은 결과를 얻음. |
** 12,13,14,15,23,24,25,34,35,45 | ** 12,13,14,15,23,24,25,34,35,45 | ||
** 이것은 1부터 5까지 중에서 2개를 선택하는 방법과 같아짐. | ** 이것은 1부터 5까지 중에서 2개를 선택하는 방법과 같아짐. | ||
| − | * 그러므로, | + | * 그러므로, <math>_4 H_2=_5 C_2</math> |
| − | * 또다른 예. | + | * 또다른 예. <math>2 H_3</math>의 계산. |
| − | * 1,2 중에서 세 | + | * 1,2 중에서 세 가지를 택하는 중복조합은 다음과 같음. |
** 111,112,122,222 | ** 111,112,122,222 | ||
| − | * 위에서 한 것처럼 첫번째 것은 내버려 두고, 두번째 것에 1, 세번째 것에 2를 더해 보면, 다음을 얻게 됨 | + | * 위에서 한 것처럼 첫번째 것은 내버려 두고, 두번째 것에 1, 세번째 것에 2를 더해 보면, 다음을 얻게 됨 |
** 123,124,134,234 | ** 123,124,134,234 | ||
** 이 경우는 1,2,3,4 중에서 세 개를 뽑는 조합과 일치함. | ** 이 경우는 1,2,3,4 중에서 세 개를 뽑는 조합과 일치함. | ||
| − | * 그러므로, | + | * 그러므로, <math>_2 H_3=_4 C_3</math> |
| − | |||
* 특정한 조합과 특정한 중복조합 사이에 [[일대일대응]]이 존재하는 것을 보이는 것임. | * 특정한 조합과 특정한 중복조합 사이에 [[일대일대응]]이 존재하는 것을 보이는 것임. | ||
| − | + | ==중복조합의 공식 증명 2== | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | * n=4, r=18 인 경우 | |
| + | * 집합을 <math>\{a,b,c,d\}</math> 로 두자. | ||
| + | * a가 6개, b가 2개, c가 3개, d가 7개 있는 경우를 아래처럼 나타내자.:<math>\{a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d \}</math>:<math>\bullet \bullet \bullet \bullet \bullet \bullet \mid \bullet \bullet \mid \bullet \bullet \bullet \mid \bullet \bullet \bullet \bullet \bullet \bullet \bullet </math> | ||
| + | * 그림에서 점과 막대를 다 합하여 총 4+18-1=21 개가 있는데, 이 21개의 위치에서 18개를 선택하여 a,b,c,d를 배열하는 중복조합과 일대일대응된다. | ||
| − | + | ||
| − | + | ||
| − | + | ==생성함수== | |
| − | |||
| − | |||
| − | |||
| − | |||
* [[생성함수]] | * [[생성함수]] | ||
| − | * | + | * 한 개의 원소에서 얻어지는 중복조합 <math>\{ \{\}, \{x\}, \{x,x\}, \{x,x,x\}, ... \}</math> 의 생성함수는 <math>S = 1 + x + x^2 + x^3 + \cdots = 1 + xS</math>로부터 <math>S=1/(1-x)</math> |
| − | + | * 두 개의 경우는 | |
| − | * | + | :<math> |
| − | + | (1-x)^{-1}(1-y)^{-1}=1+(x+y)+(x^2+xy+y^2)+(x^3+x^2y+xy^2+y^3)+\cdots | |
| − | * n개의 원소에서 | + | </math> |
| − | + | * 따라서 | |
| + | :<math> | ||
| + | \frac{1}{(1-x)^2}=\sum_{r=0}^{\infty} \textstyle\left\langle{2\atop r}\right\rangle x^r | ||
| + | </math> | ||
| + | * n개의 원소에서 r개를 뽑는 중복조합의 생성함수는 다음과 같이 주어진다 | ||
| + | :<math> | ||
| + | \begin{aligned} | ||
| + | \frac{1}{(1-x)^n}&=\sum_{r=0}^{\infty} \textstyle\left\langle{n\atop r}\right\rangle x^r \\ | ||
| + | {}&=1+nx+\frac{n(n+1)}{2!}x^2+\frac{n(n+1)(n+2)}{3!}x^3+\cdots | ||
| + | \end{aligned} | ||
| + | </math> | ||
* [[이항급수와 이항정리]] 항목 참조 | * [[이항급수와 이항정리]] 항목 참조 | ||
| − | + | ==부정방정식에의 응용== | |
| − | + | * 자연수 r에 대하여, 다음 부정방정식의 <math>x_i \geq 0</math>인 정수해의 개수를 구해보자:<math>x_0+x_1+x_2+\cdots+x_n=r</math> | |
| + | * 해의 개수는 n+1개의 원소를 가지고 r개를 뽑는 중복조합의 수와 같다. 즉, 해의 개수는 다음과 같다:<math>_{n+1} H_r=_{n+r}C_{r}=_{n+r}C_{n}</math> | ||
| + | * [[프로베니우스 디오판투스 방정식과 동전 바꾸기 문제 (coin exchange problem)|프로베니우스 디오판투스 방정식]] | ||
| − | |||
| − | |||
| − | |||
| − | + | ==메모== | |
<math>\sum_{k}\left\langle \begin{matrix} 3 \\ 4 \end{matrix} \right\rangle x^k</math> | <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> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | < | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | ==관련된 항목들== | |
| − | + | * [[이항계수와 조합]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | * [[이항계수와 조합 | ||
* [[이항급수와 이항정리]] | * [[이항급수와 이항정리]] | ||
| + | * [[동차다항식(Homogeneous polynomial)]] | ||
| + | * [[완전 동차 대칭 다항식 (complete homogeneous symmetric polynomial)]] | ||
* [[q-이항정리]] | * [[q-이항정리]] | ||
* [[일대일대응]] | * [[일대일대응]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | ==매스매티카 파일 및 계산 리소스== | |
| + | * https://docs.google.com/file/d/0B8XXo8Tve1cxS1hEZ1p0MDNfMFU/edit | ||
| − | |||
| − | + | ==사전 형태의 자료== | |
* http://ko.wikipedia.org/wiki/ | * http://ko.wikipedia.org/wiki/ | ||
* http://en.wikipedia.org/wiki/Multiset | * http://en.wikipedia.org/wiki/Multiset | ||
| + | * http://mathworld.wolfram.com/Multichoose.html | ||
| + | * http://en.wikipedia.org/wiki/Bose–Einstein_statistics | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | [[분류:조합수학]] | |
| − | + | ==메타데이터== | |
| − | + | ===위키데이터=== | |
| − | * [ | + | * ID : [https://www.wikidata.org/wiki/Q864377 Q864377] |
| − | * [ | + | ===Spacy 패턴 목록=== |
| − | * [ | + | * [{'LEMMA': 'multiset'}] |
| − | * [ | + | * [{'LEMMA': 'bag'}] |
| + | * [{'LEMMA': 'mset'}] | ||
2021년 2월 17일 (수) 06:00 기준 최신판
개요
- 중복조합
- 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것
- 1과 2에서 세 개를 취하는 중복조합은 111, 112, 122, 222의 네 가지가 있음.
- n개 중에서 r개를 선택하는 중복조합의 개수를 \(_n H_r=\textstyle\left\langle{n\atop r}\right\rangle\) 로 나타낸다.
- 변수의 개수가 \(n\)이고, 차수가 \(d\)인 동차다항식(Homogeneous polynomial)이 이루는 벡터공간의 차원은 \(_n H_d\)이며, 중복조합의 H는 homogeneous에서 온 것이다
- \(n\)차원 벡터공간 \(V\)에 대하여 대칭곱 \(\operatorname{Sym}^d V\)의 차원은 \(_n H_d\)로 주어진다
조합과의 비교
- 조합은 여러 개의 원소 중에서 몇 개를 순서에 관계없이 뽑아내는 것
- 가령 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}\]
- 증명의 아이디어를 이해하기 위해, \(_4 H_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개를 선택하는 방법과 같아짐.
- 그러므로, \(_4 H_2=_5 C_2\)
- 또다른 예. \(2 H_3\)의 계산.
- 1,2 중에서 세 가지를 택하는 중복조합은 다음과 같음.
- 111,112,122,222
- 위에서 한 것처럼 첫번째 것은 내버려 두고, 두번째 것에 1, 세번째 것에 2를 더해 보면, 다음을 얻게 됨
- 123,124,134,234
- 이 경우는 1,2,3,4 중에서 세 개를 뽑는 조합과 일치함.
- 그러므로, \(_2 H_3=_4 C_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\}, ... \}\) 의 생성함수는 \(S = 1 + x + x^2 + x^3 + \cdots = 1 + xS\)로부터 \(S=1/(1-x)\)
- 두 개의 경우는
\[ (1-x)^{-1}(1-y)^{-1}=1+(x+y)+(x^2+xy+y^2)+(x^3+x^2y+xy^2+y^3)+\cdots \]
- 따라서
\[ \frac{1}{(1-x)^2}=\sum_{r=0}^{\infty} \textstyle\left\langle{2\atop r}\right\rangle x^r \]
- n개의 원소에서 r개를 뽑는 중복조합의 생성함수는 다음과 같이 주어진다
\[ \begin{aligned} \frac{1}{(1-x)^n}&=\sum_{r=0}^{\infty} \textstyle\left\langle{n\atop r}\right\rangle x^r \\ {}&=1+nx+\frac{n(n+1)}{2!}x^2+\frac{n(n+1)(n+2)}{3!}x^3+\cdots \end{aligned} \]
- 이항급수와 이항정리 항목 참조
부정방정식에의 응용
- 자연수 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\)
관련된 항목들
- 이항계수와 조합
- 이항급수와 이항정리
- 동차다항식(Homogeneous polynomial)
- 완전 동차 대칭 다항식 (complete homogeneous symmetric polynomial)
- q-이항정리
- 일대일대응
매스매티카 파일 및 계산 리소스
사전 형태의 자료
- http://ko.wikipedia.org/wiki/
- http://en.wikipedia.org/wiki/Multiset
- http://mathworld.wolfram.com/Multichoose.html
- http://en.wikipedia.org/wiki/Bose–Einstein_statistics
메타데이터
위키데이터
- ID : Q864377
Spacy 패턴 목록
- [{'LEMMA': 'multiset'}]
- [{'LEMMA': 'bag'}]
- [{'LEMMA': 'mset'}]