최은진의 노베부터 시작하는 확통 20 – 06강 중복조합

중복조합

서로다른 n개에서 중복을 허락하고 r개를 뽑는 경우의 수: ^nH_r

^2H_4 = ^{2+4-1}C_4 = ^5C_4 = 5
5는 두가지 ‘종류’ 중 한 개의 구분, 그중에 뽑는 4가지. = ^{n+r-1}C_r

=> 서로 다른 2개에서 중복을 허락하여 4개를 택하는 중복조합의 수 ^2H_4 = 4개의 과일과 (2-1)개의 막대를 일렬로 나열하는 경우의 수 = (4+2-1)개의 자리에서 4개의 과일을 놓을 자리 4개를 선택하는 조합의 수 ^{(2+4-1)}C_4 = ^5C_4

문제: 1,2,3,4의 번호가 적힌 카드 4장의 카드 중에서 중복을 허락하여 2장의 카드를 택하는 경우의 수를 구하시오
^4H_2 = ^5C_2 = 10

문제: 자연수 r에 대하여 ^3H_r = ^7C_2일때 ^5H_r의 값을 구하시오
126

중복조합 대표유형
(1)선택
ex) 서로다른 4개 피자중 중복 허락해서 5개를 선택

만약 중복조합이 이해 안되면, a+b+c+d… = 선택개수 의 식으로 생각해도 됨.

(2) 분배
ex) 같은 종류 음료 7개 중 서로다른 세 사람에게 나눠주는 방법

문제: 축구공, 농구공, 배구공 중에서 4개의 공을 선택하는 방법의 수를 구하시오. (단, 각 종류의 공은 4개 이상씩 있고, 같은 종류의 공은 서로 구별하지 않는다.)
-> 중복이 된다. 선택의 문제. 즉, ^3H4 = ^6C_2 = 15

문제: 1부터 10까지 숫자가 각각 하나씩 적힌 10개의 상자가 있다. 똑같은 구슬 3개를 상자에 넣는 방법의 수를 구하시오. (단, 각 상자에 들어가는 구슬의 개수는 제한이 없다.)
-> 분배유형! a+b+…. = 3 이런 식으로 모델링 하면 좋음. 즉, ^10H_3 = ^12C_3 = 220

방정식의 해의 개수 구하기
– 중복조합 중 분배 유형 문제는 ‘방정식의 해의 개수를 구하는 문제’ 로 바꿔 생각하라.
– 적어도 하나씩은 받아야 한다면 미리 하나씩 주고 시작.
1) 방정식 x+y+z=r (r은 자연수)에서
(1) 음이 아닌 정수해의 개수는 ^3H_r
(2) 양의 정수해의 개수는 $latex ^3H_{r-3} (단 r >= 3)
2) (a+b+c)^r를 전개했을 떄 서로 다른 항의 개수는 ^3H_r

문제: 방정식 x+y+z = 17에 대하여 다음 해의 개수를 구하시오
1) 음이 아닌 정수해: ^3H_17 = ^19C_2 = 171
2) 양의 정수해: 하나씩 주고 함. 즉, x’+y’+z’ = 14로 계산.

CMU MSSM 21' 재학중. AI기반 습관관리 서비스 유라임 (urhy.me) 대표. 전 금융권 소프트웨어/데이터 엔지니어. 대학원 생활, 실리콘벨리, 유라임 이야기를 주로 씁니다. 데이터과학과 시각화, 대용량 아키텍처, 스타트업에 관심이 많습니다.

Translate »