확률·통계중복조합#242

중복조합

Combinations with Repetition

중복조합은 서로 다른 n종류에서 같은 종류를 여러 번 골라도 되게 r개를 택하되 순서는 구별하지 않는 선택이다. 별 r개와 칸막이 n−1개의 배열로 그 수를 세고, 최소·최대 개수 조건과 방정식의 자연수해·음이 아닌 정수해, 함수의 개수에 적용한다.

읽는 시간
약 8분
선수 개념
조합중복순열

직관 — 담은 순서 대신 종류별 개수를 적는다

직관

세 종류의 차 봉지를 한 상자에 담는다고 하자. 어떤 종류를 먼저 넣었는지는 잊고, 종류마다 몇 봉지인지 주문서에 적는다. 한 종류를 여러 봉지 넣어도 되며 고르지 않은 종류에는 영을 적는다.

이 글의 주문과 분배 상황은 계산을 위해 만든 가상 예다. 종류는 구별하지만 같은 종류의 봉지는 구별하지 않고, 각 종류의 공급은 필요한 만큼 충분하다고 가정한다. 앞의 중복순열이 기록 순서를 셌다면, 여기서는 최종 구성만 센다.

이 셈은 방정식의 정수해, 같은 물건을 여러 사람에게 나누는 방법, 크기 순서가 정해진 함수의 개수를 셀 때 다시 나온다.

중복조합은 반복을 허용하고 선택 순서는 무시한다

중복조합은 서로 다른 nn종류에서 중복을 허용하여 rr개를 고르되 고르는 순서를 구별하지 않는 것이다. 종류별로 고른 개수는 0 이상이며 합이 rr이어야 한다. nn은 양의 정수이고 rr은 0 이상의 정수로 둔다.

세 종류 A, B, C에서 네 개를 고를 때 AACC와 CACA는 같은 구성이다. 둘 다 A 두 개, B 영 개, C 두 개다. 이 구성을 (2,0,2)(2,0,2)로 기록하자. 여기서 숫자의 자리는 A, B, C 순서로 고정한다.

x1+x2+⋯+xn=r,x1,…,xn은 0 이상의 정수.(1)x_1+x_2+\cdots+x_n=r,\qquad x_1,\ldots,x_n\text{은 0 이상의 정수}. \tag{1}
정의
기호이름원어뜻
nn종류의 수number of types구별하는 종류의 수, 양의 정수
rr선택 개수selection size모두 합쳐 고를 개수, 0 이상의 정수
xix_i종류별 개수multiplicityii번째 종류를 고른 개수
nHr{}_nH_r중복조합의 수combinations with repetition순서를 무시하고 반복 선택한 구성의 수
mCk{}_mC_k조합의 수binomial coefficient서로 다른 mm자리 중 kk자리를 고르는 수

교과서는 서로 다른 nn개에서 중복을 허용하여 rr개를 택하는 조합을 중복조합이라 하고, 그 수를 nHr{}_nH_r로 나타낸다. 이 글의 ‘nn종류’가 교과서의 ‘서로 다른 nn개’이며, 같은 것을 다시 고를 수 있다는 뜻이 ‘중복을 허용한다’이다. 식 (1)의 ‘0 이상의 정수’는 교과서의 ‘음이 아닌 정수’이고, 문제집은 식 (1)의 해의 개수를 ‘음이 아닌 정수해의 개수’ 또는 ‘순서쌍 (x1,…,xn)(x_1,\ldots,x_n)의 개수’로 묻는다.

식 (1)의 각 자리와 주문서의 칸은 서로 다른 종류를 나타낸다. 따라서 (2,0,2)(2,0,2)와 (0,2,2)(0,2,2)는 다른 구성이다. 선택한 봉지를 상자에 넣은 순서를 무시한다는 말이, 종류 이름까지 없앤다는 뜻은 아니다.

중복조합에서는 왜 별과 칸막이를 배열할까?

각 종류의 개수를 같은 모양의 별로 바꾸고, 종류 사이에 칸막이를 하나씩 놓으면 구성을 잃지 않고 기록할 수 있기 때문이다. 세 종류라면 A와 B 사이, B와 C 사이의 칸막이 두 개만 필요하다. 맨 앞과 맨 뒤는 기록의 끝이므로 별도 칸막이를 놓지 않는다.

(2,0,2)(2,0,2)는 별 두 개, 칸막이 두 개, 별 두 개로 표시한다. 붙어 있는 두 칸막이 사이에 별이 없으므로 B는 0개다. (0,3,1)(0,3,1)은 첫 기호가 칸막이여서 A가 0개인 기록이다.

세 종류에서 네 개를 고른 두 구성. 별 네 개와 칸막이 두 개로 나타내며, 위의 인접한 칸막이는 B가 0개임을, 아래의 첫 칸막이는 A가 0개임을 뜻한다.
그림 1 세 종류에서 네 개를 고른 두 구성. 별 네 개와 칸막이 두 개로 나타내며, 위의 인접한 칸막이는 B가 0개임을, 아래의 첫 칸막이는 A가 0개임을 뜻한다. figures/stars_bars_mapping.py

그림 1을 거꾸로 읽을 수도 있다. 첫 칸막이 전의 별 수를 A, 두 칸막이 사이를 B, 마지막 칸막이 뒤를 C의 개수로 읽으면 원래 구성이 하나로 돌아온다. 서로 다른 구성이 같은 기록이 되지 않고, 별 네 개와 칸막이 두 개의 어떤 배열도 허용되는 구성 하나를 준다.

일반적으로 별은 rr개, 칸막이는 n−1n-1개다. 전체 n+r−1n+r-1자리 중 별이 놓일 rr자리를 고르면 나머지는 모두 칸막이가 된다. 따라서 조합으로 세면

nHr=n+r−1Cr=n+r−1Cn−1.(2){}_nH_r={}_{n+r-1}C_r={}_{n+r-1}C_{n-1}. \tag{2}

두 번째 식은 별의 자리를 고르는 것과 칸막이 자리를 고르는 것이 같은 배열을 정한다는 뜻이다. 별과 칸막이 각각을 같은 대상으로 보는 같은 것이 있는 순열로 세어도 (n+r−1)!/[r!(n−1)!](n+r-1)!/[r!(n-1)!]가 되어 식 (2)와 같다.

세 종류의 차를 네 봉지 고르는 예에서는

3H4=6C4=6C2=6×52×1=15.(3){}_3H_4={}_6C_4={}_6C_2=\frac{6\times5}{2\times1}=15. \tag{3}
세 종류에서 네 개를 고르는 구성 15가지를 모두 별과 칸막이로 적었다. 각 기록은 별 4개와 칸막이 2개로 이루어지고, 칸막이 두 개가 놓인 자리는 기록마다 다르다.
그림 2 세 종류에서 네 개를 고르는 구성 15가지를 모두 별과 칸막이로 적었다. 각 기록은 별 4개와 칸막이 2개로 이루어지고, 칸막이 두 개가 놓인 자리는 기록마다 다르다. figures/stars_bars_all.py

그림 2는 15가지 구성을 빠짐없이 적은 목록이다. 공급이 충분하므로 A 네 봉지만 고른 (4,0,0)(4,0,0)도 들어 있다. 다만 15라는 답의 근거는 이 목록이 아니라 앞의 짝짓기다. 어떤 nn, rr에서도 구성과 별·칸막이 배열이 하나씩 대응하므로 식 (2)가 성립한다.

중복조합은 중복순열·조합과 무엇이 다른가?

같은 것을 다시 고를 수 있는지, 고른 순서를 구별하는지의 두 기준으로 네 가지 셈이 나뉜다. 중복조합은 다시 고를 수 있고 순서는 구별하지 않는 칸이다. A, B, C에서 두 개를 고르면 네 셈의 답은 각각 6, 3, 9, 6이다.

세 종류에서 두 개순서를 구별한다순서를 구별하지 않는다
다시 고를 수 없다순열 3P2=6{}_3P_2=6조합 3C2=3{}_3C_2=3
다시 고를 수 있다중복순열 3Π2=9{}_3\Pi_2=9중복조합 3H2=6{}_3H_2=6
A, B, C에서 두 개를 고르는 순열·조합(위)과 중복순열·중복조합(아래)의 결과를 모두 적었다. 같은 문자를 두 번 고른 AA, BB, CC는 중복을 허용한 아래 두 칸에만 있다.
그림 3 A, B, C에서 두 개를 고르는 순열·조합(위)과 중복순열·중복조합(아래)의 결과를 모두 적었다. 같은 문자를 두 번 고른 AA, BB, CC는 중복을 허용한 아래 두 칸에만 있다. figures/counting_four_ways.py

그림 3의 위아래를 비교하면 중복을 허용할 때 AA, BB, CC가 더해진다. 왼쪽과 오른쪽을 비교하면 순서를 지울 때 AB와 BA가 하나로 합쳐진다. 그런데 중복순열의 9개에서 AA는 한 번, AB는 AB와 BA로 두 번 나타난다. 그래서 중복조합의 수는 조합처럼 한 수로 나누어 구할 수 없고, 별과 칸막이처럼 구성을 직접 세는 방법이 필요하다.

중복조합에서 각 종류를 하나 이상 고르면 어떻게 바꿀까?

먼저 각 종류를 하나씩 확보한 뒤 남은 개수를 자유롭게 배분하면 된다. 세 종류를 합하여 여덟 봉지 고르되 모두 한 봉지 이상 담는다고 하자. x1,x2,x3≥1x_1,x_2,x_3\ge1이고 합이 8이므로, x1+x2+x3=8x_1+x_2+x_3=8을 만족하는 자연수 x1,x2,x3x_1,x_2,x_3의 순서쌍을 세는 문제다. yi=xi−1y_i=x_i-1로 놓으면

y1+y2+y3=8−3=5,y1,y2,y3≥0.(4)y_1+y_2+y_3=8-3=5,\qquad y_1,y_2,y_3\ge0. \tag{4}

각 xix_i는 정수이므로 yiy_i도 정수다. 원래 구성에서 하나씩 빼는 방법과 새 구성에 하나씩 더하는 방법이 서로 되돌린다. 따라서 바뀐 구성만 세면 된다.

3H5=7C2=7×62=21.(5){}_3H_5={}_7C_2=\frac{7\times6}{2}=21. \tag{5}
세 종류를 각각 한 개 이상 고르는 조건의 변환. 위의 (3, 1, 4)에서 각 칸의 강조된 한 개씩을 빼면 아래 (2, 0, 3)이 된다. 아래의 어느 구성에도 한 개씩 더해 원래 조건으로 돌아갈 수 있다.
그림 4 세 종류를 각각 한 개 이상 고르는 조건의 변환. 위의 (3, 1, 4)에서 각 칸의 강조된 한 개씩을 빼면 아래 (2, 0, 3)이 된다. 아래의 어느 구성에도 한 개씩 더해 원래 조건으로 돌아갈 수 있다. figures/minimum_one_shift.py

그림 4는 이 변환의 한 예다. 일반적으로 nn종류를 모두 하나 이상 고르려면 우선 r≥nr\ge n이어야 한다. r<nr<n이면 필요한 최소 개수에도 못 미쳐 0가지다. r≥nr\ge n일 때 남은 r−nr-n개에 식 (2)를 적용하면 nHr−n=r−1Cn−1{}_nH_{r-n}={}_{r-1}C_{n-1}가지이고, 이것이 x1+⋯+xn=rx_1+\cdots+x_n=r의 자연수해의 개수다.

최소 개수가 종류마다 달라도 같은 방법을 쓴다. x≥2x\ge2, y≥1y\ge1이면 두 개와 한 개를 먼저 빼고 남은 개수를 나눈다.

중복조합에 최대 개수가 있으면 왜 따로 세야 할까?

최대 개수는 먼저 빼낼 개수가 정해지지 않아 식 (2)를 바로 쓸 수 없기 때문이다. 대신 경우를 나누거나, 조건을 어긴 구성을 전체에서 뺀다. 세 종류 중 세 개를 고르되 A는 최대 한 개인 예는 7가지다.

경우를 나누면 A가 0개일 때 B, C의 개수는 (0,3),(1,2),(2,1),(3,0)(0,3),(1,2),(2,1),(3,0)의 4가지다. A가 1개일 때는 (0,2),(1,1),(2,0)(0,2),(1,1),(2,0)의 3가지여서 합이 7이다.

전체에서 빼는 방법은 ‘A가 2개 이상’이라는 반대 조건이 최소 개수라는 점을 이용한다. A를 먼저 두 개 넣으면 남은 한 개를 세 종류에 나누므로 3H1=3{}_3H_1=3가지다. 제한 없는 3H3=5C3=10{}_3H_3={}_5C_3=10에서 이를 빼면

3H3−3H1=10−3=7.(6){}_3H_3-{}_3H_1=10-3=7. \tag{6}
x_1+x_2+x_3=3을 만족하는 0 이상의 정수해 10개를 (x_1, x_2) 평면의 점으로 찍고 (x_1, x_2, x_3)를 적었다. 점선 왼쪽의 채운 점 7개가 x_1≤1을 만족하고, 오른쪽의 빈 점 3개는 x_1≥2인 구성이다.
그림 5 x1+x2+x3=3x_1+x_2+x_3=3을 만족하는 0 이상의 정수해 10개를 (x1,x2)(x_1, x_2) 평면의 점으로 찍고 (x1,x2,x3)(x_1, x_2, x_3)를 적었다. 점선 왼쪽의 채운 점 7개가 x1≤1x_1\le1을 만족하고, 오른쪽의 빈 점 3개는 x1≥2x_1\ge2인 구성이다. figures/upper_cap_lattice.py

그림 5의 빈 점 3개가 식 (6)에서 빼는 구성이다. 상한이 여러 종류에 걸리면 어긴 경우끼리 겹칠 수 있다. 그때는 포함배제의 원리로 겹쳐 뺀 구성을 보정한다.

중복조합으로 부등식의 해와 함수의 개수를 센다

부등식은 남는 양을 새 변수로 두어 식 (1)의 꼴로 바꾸고, 크기 순서가 정해진 함수는 함숫값의 구성만 고르면 된다. 둘 다 순서 없이 반복을 허용한 선택이기 때문이다.

0 이상의 정수 x,yx,y가 x+y≤3x+y\le3을 만족하는 순서쌍 (x,y)(x,y)를 세어 보자. 남는 양 w=3−x−yw=3-x-y도 0 이상의 정수이고, (x,y)(x,y)가 정해지면 ww가 하나로 정해진다.

x+y≤3⟺x+y+w=3, w≥0.(7)x+y\le3\quad\Longleftrightarrow\quad x+y+w=3,\ w\ge0. \tag{7}

따라서 해는 3H3=10{}_3H_3=10개다. 그림 5의 점에서 (x1,x2)(x_1,x_2)를 (x,y)(x,y)로 읽으면 이 해 10개가 되고, 세 번째 수 x3x_3이 남는 양 ww다.

집합 X={1,2,3}X=\{1,2,3\}에서 Y={1,2,3,4}Y=\{1,2,3,4\}로 가는 함수 ff 중 f(1)≤f(2)≤f(3)f(1)\le f(2)\le f(3)인 것을 세어 보자. YY의 원소를 중복을 허용해 세 개 고르면, 작은 것부터 f(1),f(2),f(3)f(1),f(2),f(3)에 놓는 방법은 하나뿐이다. 예를 들어 2, 2, 4를 고르면 f(1)=2f(1)=2, f(2)=2f(2)=2, f(3)=4f(3)=4다.

4H3=6C3=6×5×43×2×1=20.(8){}_4H_3={}_6C_3=\frac{6\times5\times4}{3\times2\times1}=20. \tag{8}

같은 값을 허용하지 않는 f(1)<f(2)<f(3)f(1)<f(2)<f(3)이면 서로 다른 세 값을 고르는 조합이라 4C3=4{}_4C_3=4가지다. 다항식 (a+b+c)4(a+b+c)^4를 전개해 정리했을 때의 서로 다른 항 apbqcsa^pb^qc^s도 p+q+s=4p+q+s=4인 지수의 구성이므로 3H4=15{}_3H_4=15개다. 이때 각 항의 계수는 이 글에서 구하지 않는다.

핵심

중복조합은 nn종류에서 반복을 허용해 rr개를 순서 없이 고른 구성이며, 종류 사이의 경계인 칸막이 n−1n-1개와 별 rr개의 배열에 하나씩 대응하므로 nHr=n+r−1Cr{}_nH_r={}_{n+r-1}C_r이다.

중복조합에서 고르는 개수 r이 종류 수 n보다 커도 되나요?

그렇다. 중복조합은 같은 종류를 다시 고를 수 있으므로 rr이 nn보다 커도 된다. 세 종류에서 네 개를 고르는 3H4=15{}_3H_4=15가 그 예이고, 조합에서는 서로 다른 세 개 중 네 개를 고를 수 없어 0가지다.

중복조합에서 종류가 하나이거나 아무것도 고르지 않으면요?

종류가 하나인 중복조합은 그 종류로 필요한 개수를 채우는 방법 하나이고, 양의 종류 수에서 0개를 고르는 구성도 빈 구성 하나다. 식 (2)에서 각각 rCr=1{}_rC_r=1, n−1C0=1{}_{n-1}C_0=1로 확인할 수 있다.

중복조합은 같은 물건을 여러 사람에게 나누는 문제에도 쓰나요?

같은 물건을 구별되는 사람에게 나누고 각 사람의 개수만 기록한다면 중복조합으로 셀 수 있다. 같은 봉지 4개를 세 사람에게 0개도 허용해 나누는 문제는 세 종류에서 네 개를 고르는 식 (3)과 같은 15가지다. 물건 자체가 서로 다르면 누가 어떤 물건을 받는지도 구별해야 하므로 다른 문제다.

중복조합의 흔한 오해

  • 순서를 없애려면 중복순열의 수를 선택 개수의 계승으로 나누면 된다 — 그림 3에서 3Π2=9{}_3\Pi_2=9를 2!2!로 나누면 4.5로 정수조차 아니다. 구성마다 중복순열에 나타나는 횟수가 1번 또는 2번으로 달라서, 한 수로 나누면 실제 중복조합의 수 6을 얻지 못한다.
  • 빈 종류가 있어도 칸막이를 별 사이의 서로 다른 틈에만 놓는다 — 그렇게 놓으면 양끝과 인접 칸막이를 금지하여 0개인 종류를 빠뜨린다. 그림 1의 두 구성 모두 빈 종류를 포함하므로 별과 칸막이 전체 자리에서 골라야 한다.
  • nHr에서 n과 r은 바꾸어 써도 된다 — 같은 봉지 4개를 세 사람에게 나누면 종류(받는 사람) 수가 3, 고를 개수가 4이므로 3H4=15{}_3H_4=15다. 바꾸어 쓴 4H3=6C3=20{}_4H_3={}_6C_3=20은 네 종류에서 세 개를 고르는 다른 문제의 답이다.

직접 해보기

다음 주문과 분배는 모두 가상이며, 별도 제한이 없으면 공급은 충분하다.

  1. 음이 아닌 정수 x,y,zx,y,z에 대하여 x+y+z≤6x+y+z\le6을 만족하는 순서쌍 (x,y,z)(x,y,z)는 몇 개인가?
  2. 네 종류를 모두 한 봉지 이상 포함하여 여덟 봉지를 고르면 몇 가지인가?
  3. 정수 x,y,zx,y,z가 x+y+z=7x+y+z=7, x≥2x\ge2, y≥1y\ge1, z≥0z\ge0을 만족하는 순서쌍 (x,y,z)(x,y,z)는 몇 개인가?
  4. A, B, C, D 네 종류에서 네 개를 고르되 A는 최대 한 개까지 고를 수 있다. 몇 가지인가?
  5. 집합 {1,2,3}\{1,2,3\}에서 {1,2,3,4,5,6}\{1,2,3,4,5,6\}으로 가는 함수 ff 중 f(1)≤f(2)≤f(3)f(1)\le f(2)\le f(3)인 것은 몇 개인가? f(1)<f(2)<f(3)f(1)<f(2)<f(3)이면 몇 개인가?
답과 풀이
  1. 남는 양 w=6−x−y−z≥0w=6-x-y-z\ge0을 두면 x+y+z+w=6x+y+z+w=6이다. 4H6=9C6=9C3=9×8×7/(3×2×1)=84{}_4H_6={}_9C_6={}_9C_3=9\times8\times7/(3\times2\times1)=84개다.
  2. 각 종류에 하나씩 확보하면 8−4=48-4=4개가 남는다. 4H4=7C3=7×6×5/(3×2×1)=35{}_4H_4={}_7C_3=7\times6\times5/(3\times2\times1)=35가지다.
  3. u=x−2u=x-2, v=y−1v=y-1로 두면 u+v+z=4u+v+z=4이고 모두 0 이상의 정수다. 3H4=6C2=15{}_3H_4={}_6C_2=15개다. 역으로 x=u+2x=u+2, y=v+1y=v+1로 돌아가므로 해를 잃거나 더하지 않는다.
  4. 제한 없는 선택은 4H4=7C3=35{}_4H_4={}_7C_3=35가지다. A가 2개 이상인 선택은 A를 먼저 두 개 넣고 남은 두 개를 네 종류에 나누므로 4H2=5C2=10{}_4H_2={}_5C_2=10가지다. 35−10=2535-10=25가지다.
  5. 함숫값 세 개를 여섯 수에서 중복을 허용해 고르면 작은 것부터 놓는 방법이 하나뿐이다. 6H3=8C3=8×7×6/(3×2×1)=56{}_6H_3={}_8C_3=8\times7\times6/(3\times2\times1)=56개다. 같은 값을 허용하지 않으면 6C3=20{}_6C_3=20개다.

더 읽기

영상 노트

영상 노트
  • 00:00 차 봉지의 선택 순서를 지우고 종류별 주문서만 남긴다.
  • 00:30 그림 1의 별과 칸막이를 양방향으로 읽고 빈 종류를 확인한다.
  • 01:05 전체 자리에서 별의 자리를 선택해 식 (2)를 유도하고, 식 (3)의 15가지를 그림 2의 목록과 맞춘다.
  • 01:50 그림 3의 네 칸을 비교하며 9를 2로 나눌 수 없는 이유를 짚는다.
  • 02:30 그림 4에서 하나씩 빼며 식 (4)를 만든 뒤 식 (5)의 경우의 수를 구한다.
  • 03:10 그림 5의 빈 점 세 개를 빼서 식 (6)의 상한 조건을 센다.
  • 03:50 식 (7)의 남는 양과 식 (8)의 함숫값 고르기로 활용 문제를 푼다.

지도에서의 위치

순열확률·통계조합확률·통계중복순열확률·통계중복조합지금 이 페이지
선수 개념
이 페이지
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 교과서 정의·기호 연결, 15가지 구성 전체 열거, 순열·조합·중복순열·중복조합 비교, 상한 조건의 여사건 풀이와 포함배제 연결, 부등식의 정수해·함수의 개수·전개식의 항의 개수 활용, r이 n보다 큰 경우 질문, n과 r을 바꾸는 오해 추가, 교과서 용어(음이 아닌 정수해·자연수해·순서쌍) 연결, 연습을 새 유형 5문항으로 교체 (에이전트 수정, 그림 2→5)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림