확률과 통계 · 경우의 수 — 서로 다른 n개에서 중복을 허용해 순서 없이 r개를 고르는 방법의 수
ₙHᵣ = ₙ₊ᵣ₋₁Cᵣ. 똑같은 ○ r개를 n개의 칸에 나눠 담는 ‘별과 막대’ 모델로 눈에 보이게 만든다.
1. 직접 해보기
칸 수 n, 담을 개수 r 을 정하자. 아래 줄은 ○(별) r개와 |(막대) n−1개를 일렬로 놓은 것이다.
다음 배치 로 넘기면 막대의 위치가 바뀌며 각 칸의 개수 (x₁, x₂, …, xₙ) 가 달라진다.
이 배치의 총 개수가 곧 ₙ₊ᵣ₋₁Cᵣ 다.
중복조합 ₙHᵣ
–
= ₙ₊ᵣ₋₁Cᵣ
–
현재 배치
–
n, r 을 정하고 «다음 배치» 로 넘겨 보세요.
해: –
2. 왜 ₙHᵣ = ₙ₊ᵣ₋₁Cᵣ 인가
n개의 칸에 똑같은 공 r개를 나눠 담는 상황을 생각하자. 칸을 나누려면 칸막이가 n−1개 필요하다.
결국 공 r개 와 칸막이 n−1개, 합쳐서 (n−1)+r 개의 자리 중에서 공이 놓일 r개의 자리를 고르는 것과 같다.
ₙHᵣ = ( (n−1) + r )Cᵣ = ₙ₊ᵣ₋₁Cᵣ = ₙ₊ᵣ₋₁Cₙ₋₁
방정식의 해와 연결 — x₁ + x₂ + ⋯ + xₙ = r 를 만족하는
음이 아닌 정수해 (x₁, …, xₙ) 의 개수가 바로 ₙHᵣ 다.
각 xᵢ ≥ 1 (양의 정수해) 을 원하면 먼저 1개씩 깔아 두고 남은 r−n 개를 나누므로
ₙHᵣ₋ₙ = ᵣ₋₁Cₙ₋₁ 가 된다.
3. 순열·조합과 한눈 비교
구분
순서
중복
공식 (n개에서 r개)
순열 ₙPᵣ
있음
없음
n!/(n−r)!
중복순열 ₙΠᵣ
있음
허용
nʳ
조합 ₙCᵣ
없음
없음
n!/{r!(n−r)!}
중복조합 ₙHᵣ
없음
허용
ₙ₊ᵣ₋₁Cᵣ
대표 예시
· 3종류 음료에서 (같은 것 여러 잔 가능) 5잔 고르기 → ₃H₅ = ₇C₅ = 21
· 사과·배·귤 중에서 과일 4개 담기 → ₃H₄ = ₆C₄ = 15
· x + y + z + w = 10 의 음이 아닌 정수해 → ₄H₁₀ = ₁₃C₁₀ = 286
· 0 ≤ a ≤ b ≤ c ≤ 9 인 (a,b,c) 개수 → 10개에서 중복허용 3개 = ₁₀H₃ = ₁₂C₃ = 220
한 줄 요약 — 중복조합은 ‘별 r개 + 막대 (n−1)개’ 의 배열이라
ₙHᵣ = ₙ₊ᵣ₋₁Cᵣ. 방정식 x₁+⋯+xₙ = r 의 음이 아닌 정수해 개수와 같다.