중복조합의 공식 H(n,r)=C(n+r-1,r)

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

• 중복조합의 공식 H(n,r) =C(n+r-1,r)

 

 

개요

• 중복조합
  
  • 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것
  • 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 임을 확인할 수 있다.
• 중복조합의 공식
  \(_n H_r=_{n+r-1}C_{r}\)
  

 

 

조합과의 비교

• 조합은 여러 개의 원소 중에서 몇 개를 순서에 관계없이 뽑아내는 것
• 가령 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)!}}\) 공식을 통해 구할수 있음.
  

 

 

예

• 증명의 아이디어를 이해하기 위해, 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)

• 특정한 조합과 특정한 중복조합 사이에 일대일대응이 존재하는 것을 보이는 것임.

 

 

 

 

 

 

재미있는 사실

 

• Math Overflow http://mathoverflow.net/search?q=
• 네이버 지식인 http://kin.search.naver.com/search.naver?where=kin_qna&query=

 

 

역사

 

• http://www.google.com/search?hl=en&tbs=tl:1&q=
• 수학사연표
•  

 

 

 

 

관련된 항목들

 

• 이항계수
• 일대일대응

 

 

수학용어번역

• 단어사전 http://www.google.com/dictionary?langpair=en%7Cko&q=
• 발음사전 http://www.forvo.com/search/
• 대한수학회 수학 학술 용어집
  
  • http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
• 남·북한수학용어비교
• 대한수학회 수학용어한글화 게시판

 

 

사전 형태의 자료

• http://ko.wikipedia.org/wiki/
• http://en.wikipedia.org/wiki/
• http://www.wolframalpha.com/input/?i=
• NIST Digital Library of Mathematical Functions
• The On-Line Encyclopedia of Integer Sequences
  
  • http://www.research.att.com/~njas/sequences/?q=

 

 

관련논문

• http://www.jstor.org/action/doBasicSearch?Query=
• http://www.ams.org/mathscinet
• http://dx.doi.org/

 

 

관련도서

• 도서내검색
  
  • http://books.google.com/books?q=
  • http://book.daum.net/search/contentSearch.do?query=
• 도서검색
  
  • http://books.google.com/books?q=
  • http://book.daum.net/search/mainSearch.do?query=
  • http://book.daum.net/search/mainSearch.do?query=

 

 

관련기사

• 네이버 뉴스 검색 (키워드 수정)
  
  • http://news.search.naver.com/search.naver?where=news&x=0&y=0&sm=tab_hty&query=
  • http://news.search.naver.com/search.naver?where=news&x=0&y=0&sm=tab_hty&query=
  • http://news.search.naver.com/search.naver?where=news&x=0&y=0&sm=tab_hty&query=

 

 

블로그

• 구글 블로그 검색
  
  • http://blogsearch.google.com/blogsearch?q=
• 네이버 오늘의과학
• 수학동아
• Mathematical Moments from the AMS
• BetterExplained