더블릿
30 계단 | 옥 상 | 제출 현황 | Ranking | FAQs | 오류보고 | QandA | 푼   후 | 자유게시판 |
 
중복 조합
삭제 | 편집 | 답글
중복 조합 문제 정의.

n 개에서 r 개를 중복을 허락해서 뽑는 방법의 수  이라 하자.

그러면 

  

예를 들어 , 

1,2,3 세 개의 구슬이 있는 주머니에서 중복을 허락하여 5 개를 뽑는 경우의 수는?



공식이 이렇게 나오는 이유는 (오래된 정석 책 참조)

1,2 에서 3 개를 중복을 허락하여 뽑는 방법은 

  • 1 , 1  , 1
  • 1 , 1 , 2
  • 1 , 2 , 2
  • 2 , 2 , 2

이 수의 두번째에 1 을 더하고  , 세번째 수에 2 을 더하면 

  • 1 , 2 , 3
  • 1, 2 ,  4
  • 1 , 3 , 4
  • 2 , 3,  4

가 되어어 4 개의 수에 3 개를 뽑는 조합의 수와 같다 

조금 더 생각해 봐야 겠습니다.
 
2011-09-29 15:35 , testid
삭제 | 편집 | 답글
저는 중복조합을 다음과 같이 이해했습니다.


1,2,3 3개의 공간과 그것들로 채울 5개가 있습니다.

칸막이까지 포함해서 총 7개를 일렬로 배치합니다. 

그 중, 칸막이의 종류는 동일, 1,2,3으로 채울 5개의 종류는 동일하므로  을 나누어 줍니다.


칸막이의 위치도 순열로 처리한다면, (1,1,1) (1,1,2) 와 같이 모든 경우를 세는 것을 간단히 피할 수 있더라구요.
 
2011-09-29 18:15 , pl0892029
삭제 | 편집 | 답글
칸막이로 이 개념을 설명하시다니 대단 하세요.

아직 잘 이해가 되진  않지만 이해 한 후 문서 마무리 하겠습니다. 
 
2011-09-29 20:56 , testid
[previous]