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

수학노트
http://bomber0.myid.net/ (토론)님의 2009년 2월 1일 (일) 17:52 판
둘러보기로 가기 검색하러 가기
간단한 소개
  • 조합
    • 여러 개의 원소 중에서 몇 개를 순서에 관계없이 뽑아내는 경우의 수
    • 가령 1,2,3,4 네 개의 수 가운데서 세 개씩 뽑아 모은 조합은 123, 124, 134, 234 의 네 가지
    • n개 중에서 r개를 선택하는 조합의 개수를 C(n,r) 이라고 표현. 즉, C(4,3)=4
  • 중복 조합
    • 동일한 것의 중복을 허용하는 조합
    • 1과 2에서 세 개를 취하는 중복 조합은 111, 112, 122, 222의 네 가지가 있다. n개 중에서 r개를 선택하는 중복조합의 개수를 H(n,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 로 변한다.
그러므로, H(2,3)=C(4,3)

 

 

 

재미있는 사실

 

 

관련된 단원

 

 

관련된 다른 주제들

 

관련도서 및 추천도서

 

 

관련된 고교수학 또는 대학수학

 

 

참고할만한 자료