문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 조합 (문단 편집) == 중복 조합 == {{{+1 [[重]][[複]][[組]][[合]] / multiset coefficient}}} 조합과 마찬가지로 [math(n)]개의 원소에서 [math(r)]개를 순서에 상관없이 뽑는데, '''중복을 허락할 때'''의 가짓수이다. 기호로는 [math(\left(\!\!\dbinom{n}{r}\!\!\right))] 또는 [math(M(n,\,r))], [math((\varphi))][[https://arxiv.org/pdf/2105.06908.pdf|#]]을 쓰며, 한국과 일본에서는 [math({}_n{\rm H}_r)]도 통한다.[* 조합 기호를 이용해서 나타낼 수 있기 때문에 국가에 따라서는 따로 기호를 만들어 쓰지 않는 경우가 많고 별도의 기호가 있다 하더라도 국가마다 제각각이다.] [math(\rm H)]라는 기호는 동차 단항식(homogeneous monomial) 또는 동차곱(homogeneous product)의 'homogeneous'에서 딴 것이다.[[https://orbi.kr/bbs/board.php?bo_table=united&wr_id=4410969|#]] [[집합론]]에서 [[중복집합]]을 다룰 때에도 등장한다.[* 여기서는 '''중복집합(계)수'''로 부르는 것이 일반적이다.] 중복 조합의 가짓수를 실제로 구하려고 해보면 [[순열]]이나 위의 조합과는 다르게 훨씬 복잡함을 알 수 있다.[* [[순열#s-2|중복 순열]]보다도 훨씬 복잡한데, 서로 다른 [math(n)]종류의 원소에서 '''특정 원소를 고르지 않는 경우'''까지 포함하기 때문이다. 이를테면 A, B, C에서 중복을 허용하여 4개를 뽑는 경우의 수 중엔 AAAC처럼 B가 포함되지 않는 경우도 포함된다.] 계산공식을 유도하는 과정은 보통 "원([math(●)])"과 "막대기([math(|)])"를[* 혹은 비슷한 다른 무언가. 칸막이라는 표현도 쓴다.] 사용해서 설명한다. 예를 들어 숫자 [math(1)], [math(2)], [math(3)]중 중복을 허락하여 [math(5)]개를 뽑는 경우의 수를 생각해보자. 일단 [math(5)]개를 뽑으므로 원 [math(5)]개를 나란히 그린다([math(●●●●●)]). 이제 이 [math(5)]개의 원 사이에 막대기를 집어넣어 [math(3)]그룹으로 나누는데 '''이 '그룹'이 곧 주어진 원소의 종류 [math(\boldsymbol n)]개'''를 의미한다. 이를테면 [math(11233 \to ●●|●|●●)], [math(11133 \to ●●●||●●)], [math(22223 \to |●●●●|●)]으로 나타낼 수 있으므로, 특정 원소를 뽑지 않는 경우는 막대기가 중복되어 나열되는 경우로 간주할 수 있다. [math(3)]그룹으로 나누기 위해 필요한 막대기의 수는 [math((3-1) = 2)]개이고, 나눠진 각 그룹에 있는 원의 수를 각각 숫자 [math(1)], [math(2)], [math(3)]을 뽑는 개수라고하면 구하고자 하는 값이 나온다. 즉 총 가짓수는 [math(5)]개의 원과 [math(2)]개의 막대기를 나열하는 가짓수와 같고, 이는 [math(7)]개의 칸중 막대기를 그릴 [math(2)]개의 칸을 정하는 것과 동일하다.[* [math(7)]개의 칸중 막대기를 그리지 않을 [math(5)]개의 칸을 정하는 것으로 생각할 수도 있다.] 즉, [math(\rm{}_{5+3-1}C_2= {}_7C_2)]가 답. 일반적인 경우는 다음과 같다. ||[math(\begin{aligned}{}_n{\rm H}_r &= {}_{r+(n-1)}{\rm C}_r = {}_{n+r-1}{\rm C}_{n-1} \\ &= \frac{(n+r-1)!}{(n-1)!r!} = \frac1{r!} \prod_{i=0}^{r-1}(n+i) = \frac{n(n+1)(n+2) \cdots\cdots (n+r-1)}{r!} \\ &= \frac{\Gamma(n+r)}{\Gamma(n) \Gamma(r+1)} \end{aligned})] || 하강 계승(순열)으로 정의되는 조합과 비슷하게, [[상승 계승]]을 이용하면 조합을 이용한 정의보다 더 깔끔한 정의가 가능하다. || [math({}_n{\rm H}_r = \dfrac{n^{\overline r}}{r!})] || 이를 응용하여 [[배스킨라빈스]]의 [math(31)]가지 아이스크림을 '''중복을 허락하여''' 고를 경우(ex. 쿼터 크기에 엄마는 외계인×2, 체리 쥬빌레, 아몬드봉봉 등)고를 수 있는 총 경우의 수는 다음과 같이 구할 수 있다. 파인트([math(3)]가지): [math(\rm{}_{31}H_3 = {}_{3+31-1}C_3= {}_{33}C_3=5456)]가지. 쿼터([math(4)]가지): [math(\rm{}_{31}H_4 = {}_{4+31-1}C_4= {}_{34}C_4=46376)]가지. 패밀리([math(5)]가지): [math(\rm{}_{31}H_5 = {}_{5+31-1}C_5= {}_{35}C_5=324632)]가지. 하프갤런([math(6)]가지): [math(\rm{}_{31}H_6 = {}_{6+31-1}C_6= {}_{36}C_6=1947792)]가지. 반면에 중복을 허락하지 않을 경우엔 일반적인 조합과 같아진다. 파인트([math(3)]가지): [math(\rm{}_{31}C_3=4495)]가지. 쿼터([math(4)]가지): [math(\rm{}_{31}C_4=31465)]가지. 패밀리([math(5)]가지): [math(\rm{}_{31}C_5=169911)]가지. 하프갤런([math(6)]가지): [math(\rm{}_{31}C_6=736281)]가지. 언뜻 보기에 조합의 특수한 경우로밖에 안 보이지만 사실 아주 중요한 성질이 있다. 부분곱으로 나타낸 중복 조합식의 [math(n)]에 [math(-n)]을 대입하면 다음과 같이 식이 변형되면서 조합에 관한 식으로 바뀐다. || [math(\displaystyle {}_{-n}{\rm H}_r = \frac 1{r!} \prod_{i=0}^{r-1}(-n+i) = \frac{(-1)^r}{r!} \prod_{i=0}^{r-1}(n-i) = (-1)^r {}_n{\rm C}_r)] || 이를 달리 표현하면 중복 조합은 조합에서 [math(n)]이 음수인 경우로 볼 수 있고[* 엄밀히 따지면 [math({}_{-n}{\rm C}_r = (-1)^r {}_n{\rm H}_r)]] [math(n)]의 범위를 모든 정수로 확장[* 사실 조합을 부분곱으로 나타낸 식을 보면 알겠지만 애초에 그 식에서는 [math(n)]이 '''복소수'''여도 상관이 없다. [[테일러 급수/목록#s-3|테일러 급수의 예]] 문서 참조]해주는 성질이 있음을 알 수 있다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기