직관 — 담은 순서 대신 종류별 개수를 적는다
세 종류의 차 봉지를 한 상자에 담는다고 하자. 어떤 종류를 먼저 넣었는지는 잊고, 종류마다 몇 봉지인지 주문서에 적는다. 한 종류를 여러 봉지 넣어도 되며 고르지 않은 종류에는 영을 적는다.
이 글의 주문과 분배 상황은 계산을 위해 만든 가상 예다. 종류는 구별하지만 같은 종류의 봉지는 구별하지 않고, 각 종류의 공급은 필요한 만큼 충분하다고 가정한다. 앞의 중복순열이 기록 순서를 셌다면, 여기서는 최종 구성만 센다.
이 셈은 방정식의 정수해, 같은 물건을 여러 사람에게 나누는 방법, 크기 순서가 정해진 함수의 개수를 셀 때 다시 나온다.
중복조합은 반복을 허용하고 선택 순서는 무시한다
중복조합은 서로 다른 종류에서 중복을 허용하여 개를 고르되 고르는 순서를 구별하지 않는 것이다. 종류별로 고른 개수는 0 이상이며 합이 이어야 한다. 은 양의 정수이고 은 0 이상의 정수로 둔다.
세 종류 A, B, C에서 네 개를 고를 때 AACC와 CACA는 같은 구성이다. 둘 다 A 두 개, B 영 개, C 두 개다. 이 구성을 로 기록하자. 여기서 숫자의 자리는 A, B, C 순서로 고정한다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 종류의 수 | number of types | 구별하는 종류의 수, 양의 정수 | |
| 선택 개수 | selection size | 모두 합쳐 고를 개수, 0 이상의 정수 | |
| 종류별 개수 | multiplicity | 번째 종류를 고른 개수 | |
| 중복조합의 수 | combinations with repetition | 순서를 무시하고 반복 선택한 구성의 수 | |
| 조합의 수 | binomial coefficient | 서로 다른 자리 중 자리를 고르는 수 |
교과서는 서로 다른 개에서 중복을 허용하여 개를 택하는 조합을 중복조합이라 하고, 그 수를 로 나타낸다. 이 글의 ‘종류’가 교과서의 ‘서로 다른 개’이며, 같은 것을 다시 고를 수 있다는 뜻이 ‘중복을 허용한다’이다. 식 (1)의 ‘0 이상의 정수’는 교과서의 ‘음이 아닌 정수’이고, 문제집은 식 (1)의 해의 개수를 ‘음이 아닌 정수해의 개수’ 또는 ‘순서쌍 의 개수’로 묻는다.
식 (1)의 각 자리와 주문서의 칸은 서로 다른 종류를 나타낸다. 따라서 와 는 다른 구성이다. 선택한 봉지를 상자에 넣은 순서를 무시한다는 말이, 종류 이름까지 없앤다는 뜻은 아니다.
중복조합에서는 왜 별과 칸막이를 배열할까?
각 종류의 개수를 같은 모양의 별로 바꾸고, 종류 사이에 칸막이를 하나씩 놓으면 구성을 잃지 않고 기록할 수 있기 때문이다. 세 종류라면 A와 B 사이, B와 C 사이의 칸막이 두 개만 필요하다. 맨 앞과 맨 뒤는 기록의 끝이므로 별도 칸막이를 놓지 않는다.
는 별 두 개, 칸막이 두 개, 별 두 개로 표시한다. 붙어 있는 두 칸막이 사이에 별이 없으므로 B는 0개다. 은 첫 기호가 칸막이여서 A가 0개인 기록이다.
figures/stars_bars_mapping.py그림 1을 거꾸로 읽을 수도 있다. 첫 칸막이 전의 별 수를 A, 두 칸막이 사이를 B, 마지막 칸막이 뒤를 C의 개수로 읽으면 원래 구성이 하나로 돌아온다. 서로 다른 구성이 같은 기록이 되지 않고, 별 네 개와 칸막이 두 개의 어떤 배열도 허용되는 구성 하나를 준다.
일반적으로 별은 개, 칸막이는 개다. 전체 자리 중 별이 놓일 자리를 고르면 나머지는 모두 칸막이가 된다. 따라서 조합으로 세면
두 번째 식은 별의 자리를 고르는 것과 칸막이 자리를 고르는 것이 같은 배열을 정한다는 뜻이다. 별과 칸막이 각각을 같은 대상으로 보는 같은 것이 있는 순열로 세어도 가 되어 식 (2)와 같다.
세 종류의 차를 네 봉지 고르는 예에서는
figures/stars_bars_all.py그림 2는 15가지 구성을 빠짐없이 적은 목록이다. 공급이 충분하므로 A 네 봉지만 고른 도 들어 있다. 다만 15라는 답의 근거는 이 목록이 아니라 앞의 짝짓기다. 어떤 , 에서도 구성과 별·칸막이 배열이 하나씩 대응하므로 식 (2)가 성립한다.
중복조합은 중복순열·조합과 무엇이 다른가?
같은 것을 다시 고를 수 있는지, 고른 순서를 구별하는지의 두 기준으로 네 가지 셈이 나뉜다. 중복조합은 다시 고를 수 있고 순서는 구별하지 않는 칸이다. A, B, C에서 두 개를 고르면 네 셈의 답은 각각 6, 3, 9, 6이다.
| 세 종류에서 두 개 | 순서를 구별한다 | 순서를 구별하지 않는다 |
|---|---|---|
| 다시 고를 수 없다 | 순열 | 조합 |
| 다시 고를 수 있다 | 중복순열 | 중복조합 |
figures/counting_four_ways.py그림 3의 위아래를 비교하면 중복을 허용할 때 AA, BB, CC가 더해진다. 왼쪽과 오른쪽을 비교하면 순서를 지울 때 AB와 BA가 하나로 합쳐진다. 그런데 중복순열의 9개에서 AA는 한 번, AB는 AB와 BA로 두 번 나타난다. 그래서 중복조합의 수는 조합처럼 한 수로 나누어 구할 수 없고, 별과 칸막이처럼 구성을 직접 세는 방법이 필요하다.
중복조합에서 각 종류를 하나 이상 고르면 어떻게 바꿀까?
먼저 각 종류를 하나씩 확보한 뒤 남은 개수를 자유롭게 배분하면 된다. 세 종류를 합하여 여덟 봉지 고르되 모두 한 봉지 이상 담는다고 하자. 이고 합이 8이므로, 을 만족하는 자연수 의 순서쌍을 세는 문제다. 로 놓으면
각 는 정수이므로 도 정수다. 원래 구성에서 하나씩 빼는 방법과 새 구성에 하나씩 더하는 방법이 서로 되돌린다. 따라서 바뀐 구성만 세면 된다.
figures/minimum_one_shift.py그림 4는 이 변환의 한 예다. 일반적으로 종류를 모두 하나 이상 고르려면 우선 이어야 한다. 이면 필요한 최소 개수에도 못 미쳐 0가지다. 일 때 남은 개에 식 (2)를 적용하면 가지이고, 이것이 의 자연수해의 개수다.
최소 개수가 종류마다 달라도 같은 방법을 쓴다. , 이면 두 개와 한 개를 먼저 빼고 남은 개수를 나눈다.
중복조합에 최대 개수가 있으면 왜 따로 세야 할까?
최대 개수는 먼저 빼낼 개수가 정해지지 않아 식 (2)를 바로 쓸 수 없기 때문이다. 대신 경우를 나누거나, 조건을 어긴 구성을 전체에서 뺀다. 세 종류 중 세 개를 고르되 A는 최대 한 개인 예는 7가지다.
경우를 나누면 A가 0개일 때 B, C의 개수는 의 4가지다. A가 1개일 때는 의 3가지여서 합이 7이다.
전체에서 빼는 방법은 ‘A가 2개 이상’이라는 반대 조건이 최소 개수라는 점을 이용한다. A를 먼저 두 개 넣으면 남은 한 개를 세 종류에 나누므로 가지다. 제한 없는 에서 이를 빼면
figures/upper_cap_lattice.py그림 5의 빈 점 3개가 식 (6)에서 빼는 구성이다. 상한이 여러 종류에 걸리면 어긴 경우끼리 겹칠 수 있다. 그때는 포함배제의 원리로 겹쳐 뺀 구성을 보정한다.
중복조합으로 부등식의 해와 함수의 개수를 센다
부등식은 남는 양을 새 변수로 두어 식 (1)의 꼴로 바꾸고, 크기 순서가 정해진 함수는 함숫값의 구성만 고르면 된다. 둘 다 순서 없이 반복을 허용한 선택이기 때문이다.
0 이상의 정수 가 을 만족하는 순서쌍 를 세어 보자. 남는 양 도 0 이상의 정수이고, 가 정해지면 가 하나로 정해진다.
따라서 해는 개다. 그림 5의 점에서 를 로 읽으면 이 해 10개가 되고, 세 번째 수 이 남는 양 다.
집합 에서 로 가는 함수 중 인 것을 세어 보자. 의 원소를 중복을 허용해 세 개 고르면, 작은 것부터 에 놓는 방법은 하나뿐이다. 예를 들어 2, 2, 4를 고르면 , , 다.
같은 값을 허용하지 않는 이면 서로 다른 세 값을 고르는 조합이라 가지다. 다항식 를 전개해 정리했을 때의 서로 다른 항 도 인 지수의 구성이므로 개다. 이때 각 항의 계수는 이 글에서 구하지 않는다.
중복조합은 종류에서 반복을 허용해 개를 순서 없이 고른 구성이며, 종류 사이의 경계인 칸막이 개와 별 개의 배열에 하나씩 대응하므로 이다.
중복조합에서 고르는 개수 r이 종류 수 n보다 커도 되나요?
그렇다. 중복조합은 같은 종류를 다시 고를 수 있으므로 이 보다 커도 된다. 세 종류에서 네 개를 고르는 가 그 예이고, 조합에서는 서로 다른 세 개 중 네 개를 고를 수 없어 0가지다.
중복조합에서 종류가 하나이거나 아무것도 고르지 않으면요?
종류가 하나인 중복조합은 그 종류로 필요한 개수를 채우는 방법 하나이고, 양의 종류 수에서 0개를 고르는 구성도 빈 구성 하나다. 식 (2)에서 각각 , 로 확인할 수 있다.
중복조합은 같은 물건을 여러 사람에게 나누는 문제에도 쓰나요?
같은 물건을 구별되는 사람에게 나누고 각 사람의 개수만 기록한다면 중복조합으로 셀 수 있다. 같은 봉지 4개를 세 사람에게 0개도 허용해 나누는 문제는 세 종류에서 네 개를 고르는 식 (3)과 같은 15가지다. 물건 자체가 서로 다르면 누가 어떤 물건을 받는지도 구별해야 하므로 다른 문제다.
중복조합의 흔한 오해
- 순서를 없애려면 중복순열의 수를 선택 개수의 계승으로 나누면 된다 — 그림 3에서 를 로 나누면 4.5로 정수조차 아니다. 구성마다 중복순열에 나타나는 횟수가 1번 또는 2번으로 달라서, 한 수로 나누면 실제 중복조합의 수 6을 얻지 못한다.
- 빈 종류가 있어도 칸막이를 별 사이의 서로 다른 틈에만 놓는다 — 그렇게 놓으면 양끝과 인접 칸막이를 금지하여 0개인 종류를 빠뜨린다. 그림 1의 두 구성 모두 빈 종류를 포함하므로 별과 칸막이 전체 자리에서 골라야 한다.
- nHr에서 n과 r은 바꾸어 써도 된다 — 같은 봉지 4개를 세 사람에게 나누면 종류(받는 사람) 수가 3, 고를 개수가 4이므로 다. 바꾸어 쓴 은 네 종류에서 세 개를 고르는 다른 문제의 답이다.
직접 해보기
다음 주문과 분배는 모두 가상이며, 별도 제한이 없으면 공급은 충분하다.
- 음이 아닌 정수 에 대하여 을 만족하는 순서쌍 는 몇 개인가?
- 네 종류를 모두 한 봉지 이상 포함하여 여덟 봉지를 고르면 몇 가지인가?
- 정수 가 , , , 을 만족하는 순서쌍 는 몇 개인가?
- A, B, C, D 네 종류에서 네 개를 고르되 A는 최대 한 개까지 고를 수 있다. 몇 가지인가?
- 집합 에서 으로 가는 함수 중 인 것은 몇 개인가? 이면 몇 개인가?
답과 풀이
- 남는 양 을 두면 이다. 개다.
- 각 종류에 하나씩 확보하면 개가 남는다. 가지다.
- , 로 두면 이고 모두 0 이상의 정수다. 개다. 역으로 , 로 돌아가므로 해를 잃거나 더하지 않는다.
- 제한 없는 선택은 가지다. A가 2개 이상인 선택은 A를 먼저 두 개 넣고 남은 두 개를 네 종류에 나누므로 가지다. 가지다.
- 함숫값 세 개를 여섯 수에서 중복을 허용해 고르면 작은 것부터 놓는 방법이 하나뿐이다. 개다. 같은 값을 허용하지 않으면 개다.
더 읽기
- 지학사 2022 개정 고등 확률과 통계 교과서 — 「중복조합」 17–19쪽. 중복조합의 표기와 별·칸막이의 대응, 양의 정수 조건을 변환하는 과정을 확인했다.
- Discrete Mathematics: An Open Introduction — Counting Multisets — Oscar Levin, 4판, 3.5절. 같은 물건의 분배를 종류별 개수로 나타내는 설명과 빈 칸을 허용하는 막대·점 표현을 대조했다.
영상 노트
- 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)의 함숫값 고르기로 활용 문제를 푼다.
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 교과서 정의·기호 연결, 15가지 구성 전체 열거, 순열·조합·중복순열·중복조합 비교, 상한 조건의 여사건 풀이와 포함배제 연결, 부등식의 정수해·함수의 개수·전개식의 항의 개수 활용, r이 n보다 큰 경우 질문, n과 r을 바꾸는 오해 추가, 교과서 용어(음이 아닌 정수해·자연수해·순서쌍) 연결, 연습을 새 유형 5문항으로 교체 (에이전트 수정, 그림 2→5)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림