중복조합
개념
조합은 서로 다른 것에서 순서 없이 뽑는 것이었습니다. 여기서 같은 것을 여러 번 뽑아도 된다고 허용하면 중복조합이 됩니다. 예를 들어 세 종류의 붕어빵(팥·슈크림·피자) 중에서 5개를 살 때, 같은 맛을 몇 개든 골라도 되는 상황이 중복조합입니다.
서로 다른 \(n\)개에서 중복을 허용해 \(r\)개를 뽑는 중복조합의 수는
\[{}_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r\]
왜 \(n+r-1\)일까요? “무엇을 몇 개 뽑았는가”는 칸막이 \(n-1\)개로 종류를 나누고 공 \(r\)개를 늘어놓는 배열과 같습니다. 전체 \(n+r-1\)개 자리 중 공이 놓일 \(r\)자리를 고르는 문제가 되어 \({}_{n+r-1}\mathrm{C}_r\)입니다.
핵심은 공과 칸막이(●와 │) 로 바꿔 세는 것입니다. 종류가 \(n\)개면 칸막이는 \(n-1\)개, 뽑는 개수가 \(r\)개면 공은 \(r\)개입니다. 이 \(n+r-1\)개를 일렬로 놓는 방법 중 공의 자리를 고르면 되므로 \({}_{n+r-1}\mathrm{C}_r\)가지가 됩니다. 아래 앱에서 종류와 개수를 바꾸며 공-칸막이 그림과 그 수가 어떻게 변하는지 보세요.
만지며 배우기
#| '!! shinylive warning !!': |
#| shinylive does not work in self-contained HTML documents.
#| Please set `embed-resources: false` in your metadata.
#| standalone: true
#| viewerHeight: 620
from math import comb
from shiny import App, render, ui
ACCENT = "#2563eb"
app_ui = ui.page_sidebar(
ui.sidebar(
ui.input_slider("n", "붕어빵 종류 수 (n)", min=2, max=6, value=3, step=1),
ui.input_slider("r", "사는 개수 (r)", min=1, max=8, value=5, step=1),
width=250,
),
ui.card(
ui.card_header("공(●)과 칸막이(│) 로 바꿔 세기"),
ui.output_ui("diagram"),
),
ui.card(ui.output_ui("readout")),
fillable=True,
)
def server(input, output, session):
@render.ui
def diagram():
n, r = input.n(), input.r()
# 한 가지 예시 분배: 첫 종류에 몰아주고 나머지는 한 개씩 흩뿌리기
counts = [0] * n
for k in range(r):
counts[k % n] += 1
parts = []
for i, c in enumerate(counts):
balls = "".join(
f'<span style="color:{ACCENT}; font-size:1.4em;">●</span>'
for _ in range(c)
)
parts.append(balls if c else
'<span style="color:#d1d5db;">·</span>')
bar = ('<span style="color:#9ca3af; font-size:1.4em;'
' margin:0 6px;">│</span>')
row = bar.join(parts)
labels = " · ".join(f"{i+1}번 {c}개" for i, c in enumerate(counts))
return ui.HTML(
f'<div style="padding:1em 0.3em; letter-spacing:2px;">{row}</div>'
f'<div style="color:#6b7280; font-size:0.85em;">예시 분배: {labels}</div>'
)
@render.ui
def readout():
n, r = input.n(), input.r()
val = comb(n + r - 1, r)
return ui.HTML(
'<p class="hs-readline">'
f"{n}종류에서 중복을 허용해 {r}개를 고르는 방법은 "
f"nHr = (n+r-1)Cr = {n + r - 1}C{r} = <b>{val:,}가지</b>입니다. "
f"공 {r}개와 칸막이 {n - 1}개, 모두 {n + r - 1}개를 늘어놓고 "
f"그중 공이 놓일 {r}자리를 고르는 문제와 똑같습니다.</p>"
)
app = App(app_ui, server)중복조합은 조합 함수 comb 로 자리 수만 바꾸면 됩니다.
from math import comb
# 3종류 붕어빵에서 5개 사기 (중복 허용)
n, r = 3, 5
print(comb(n + r - 1, r)) # 7C5 = 21
# 비교: 서로 다른 3개에서 순서 없이 5개는 불가능하지만,
# 중복을 허용하면 21가지가 나온다.스스로 확인
중복조합 \({}_3\mathrm{H}_4 = {}_{3+4-1}\mathrm{C}_4 = {}_6\mathrm{C}_4 = 15\)가지입니다. 공 4개와 칸막이 2개, 모두 6개를 늘어놓고 공의 자리 4개를 고르는 것과 같습니다.
둘 다 같은 것을 다시 뽑을 수 있지만, 순서를 따지는지가 다릅니다. 중복순열 \({}_n\Pi_r = n^r\)는 뽑은 순서까지 구별하고, 중복조합 \({}_n\mathrm{H}_r\)는 “무엇을 몇 개” 만 보고 순서는 무시합니다. 그래서 같은 \(n,\,r\)이면 항상 \({}_n\mathrm{H}_r \le {}_n\Pi_r\)입니다.