순열과 조합
개념
서로 다른 \(n\)개에서 \(r\)개를 순서를 생각하여 뽑아 나열하는 것이 순열, 순서를 생각하지 않고 뽑기만 하는 것이 조합입니다. 순열의 수와 조합의 수는 다음과 같습니다.
\[{}_n\mathrm{P}_r = \frac{n!}{(n-r)!}, \qquad {}_n\mathrm{C}_r = \frac{n!}{r!\,(n-r)!} = \frac{{}_n\mathrm{P}_r}{r!}\]
반에서 반장·부반장을 뽑으면 누가 어느 자리인지 순서가 중요하니 순열 \({}_n\mathrm{P}_2\), 그냥 대표 2명을 뽑으면 순서가 없으니 조합 \({}_n\mathrm{C}_2\)입니다.
같은 \(r\)개를 뽑아도 순서를 매기는 방법이 \(r!\)가지이므로, 순열의 수는 조합의 수의 \(r!\)배입니다. 즉 \({}_n\mathrm{P}_r = {}_n\mathrm{C}_r \times r!\) 이 항상 성립합니다. 아래 앱에서 \(n\)과 \(r\)을 움직이며 두 수가 어떻게 변하는지, 그리고 이 관계식이 실제 수로 확인되는지 살펴보세요.
만지며 배우기
#| '!! shinylive warning !!': |
#| shinylive does not work in self-contained HTML documents.
#| Please set `embed-resources: false` in your metadata.
#| standalone: true
#| viewerHeight: 640
# matplotlib·numpy 없이 stdlib + 인라인 SVG 로만 그린다
from math import comb, factorial
from shiny import App, render, ui
ACCENT = "#2563eb"
INK = "#111827"
MUTED = "#6b7280"
GRID = "#e5e7eb"
def bars_svg(vals, hi):
W, H, ml, mr, mt, mb = 460, 320, 46, 12, 14, 34
pw, ph = W - ml - mr, H - mt - mb
vmax = max(vals) or 1
nb = len(vals)
bw = pw / nb
grid = ""
for t in range(5):
v = vmax * t / 4
yy = mt + ph - (v / vmax) * ph
grid += (f'<line x1="{ml}" y1="{yy:.1f}" x2="{W-mr}" y2="{yy:.1f}" stroke="{GRID}"/>'
f'<text x="{ml-6}" y="{yy+3:.1f}" font-size="9" fill="{MUTED}" '
f'text-anchor="end">{int(round(v))}</text>')
bars = ""
for i, v in enumerate(vals):
bh = (v / vmax) * ph
x = ml + i * bw
y = mt + ph - bh
col = ACCENT if i == hi else "#d1d5db"
bars += (f'<rect x="{x+1:.1f}" y="{y:.1f}" width="{bw-2:.1f}" '
f'height="{bh:.1f}" fill="{col}"/>'
f'<text x="{x+bw/2:.1f}" y="{mt+ph+14:.1f}" font-size="9" '
f'fill="{MUTED}" text-anchor="middle">{i}</text>')
return (
f'<svg viewBox="0 0 {W} {H}" style="width:100%;height:auto;'
'font-family:-apple-system,sans-serif;">'
f'{grid}{bars}'
f'<text x="{ml+pw/2:.0f}" y="{H-4}" font-size="10" fill="{MUTED}" '
'text-anchor="middle">k (뽑는 개수)</text>'
f'<text x="8" y="{mt-2}" font-size="10" fill="{MUTED}">C(n, k)</text>'
'</svg>'
)
app_ui = ui.page_sidebar(
ui.sidebar(
ui.input_slider("n", "전체 개수 n", min=1, max=12, value=6, step=1),
ui.input_slider("r", "뽑는 개수 r", min=0, max=12, value=2, step=1),
width=240,
),
ui.card(
ui.card_header("조합의 수 C(n, k) — 파란 막대가 지금 고른 r"),
ui.output_ui("bars"),
),
ui.card(ui.output_ui("readout")),
fillable=True,
)
def server(input, output, session):
@render.ui
def bars():
n = input.n()
r_eff = min(input.r(), n)
return ui.HTML(bars_svg([comb(n, k) for k in range(n + 1)], r_eff))
@render.ui
def readout():
n, r = input.n(), input.r()
r_eff = min(r, n)
npr = comb(n, r_eff) * factorial(r_eff)
ncr = comb(n, r_eff)
note = ""
if r > n:
note = (f" (r = {r}은 n = {n}보다 클 수 없어 "
f"r = {r_eff}로 맞춰 계산했습니다.)")
return ui.HTML(
f'<p class="hs-readline">'
f"{n}P{r_eff} = {npr:,} · {n}C{r_eff} = {ncr:,} 입니다. "
f"관계식으로 확인하면 {n}P{r_eff} = {n}C{r_eff} × {r_eff}! = "
f"{ncr:,} × {factorial(r_eff):,} = {npr:,} 이 성립합니다."
f"{note}</p>"
)
app = App(app_ui, server)순열과 조합의 수는 math 모듈로 바로 계산할 수 있습니다.
from math import comb, factorial
n, r = 6, 2
nCr = comb(n, r) # 6C2 = 15
nPr = nCr * factorial(r) # 6P2 = 15 × 2! = 30
print(nPr, nCr) # 30 15
print(nPr == comb(n, r) * factorial(r)) # nPr = nCr × r! 확인스스로 확인
가운데(\(k = n/2\) 근처)가 가장 높고 양끝(\(k=0,\,n\))이 1인 좌우 대칭 모양입니다. \({}_n\mathrm{C}_r = {}_n\mathrm{C}_{n-r}\)이기 때문입니다 — \(r\)개를 “뽑는” 것과 \(n-r\)개를 “남기는” 것은 같은 선택입니다.
대표 3명은 순서가 없으니 \({}_8\mathrm{C}_3 = 56\), 회장·부회장·총무는 자리가 구별되니 \({}_8\mathrm{P}_3 = 336\)입니다. \(336 = 56 \times 3!\) — 같은 3명을 세 자리에 배치하는 방법이 \(3! = 6\)가지라서 정확히 6배가 됩니다. 앱에서 \(n=8\), \(r=3\)으로 확인해 보세요.