이항계수

◼︎ 이항계수

이항계수 ‘nCk’ 는 ‘n개의 아이템 중 k개를 선택하는 방법의 수를 의미한다.

예를 들어, 5개의 사과 중 2개를 선택하는 방법의 수는 ‘5C2’이고, 이는 10가지 방법이 있음을 나타낸다.

---

이항계수 점화식

이항계수의 계산은 점화식을 통해 이뤄진다.

dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

점화식 ‘dp[i][j] = dp[i-1][j] + dp[i-1][j-1]’을 해석하면,

• ‘i-1개 중에서 j개를 선택하는 방법의 수’
  • 기존에 가지고 있던 아이템 들 중에서, j개를 선택하는 경우의 수
• ‘i-1개 중에서 j-1개를 선택하는 방법의 수’
  • 기존에 가지고 있던 아이템들 중에서 하나로 추가를 선택하는 경우의 수

를 합친것과 같다는 의미이다.

---

예를 들면

세 개의 공(A, B, C)이 있을 때, 이 중에서 두 개를 고르는 방법은 ‘3C2’로 표현할 수 있다.

공 A, B, C 중에서 두 개를 고르는 방법은 총 세 가지(A-B, B-C, A-C)이다.

3개의 아이템(A, B, C) 중 2개를 선택하는 경우의 수를 찾으려면, 아래와 같이 행렬을 채울 수 있다.

0 1 0 0 0
1 1 1 0 0
2 1 2 1 0
3 1 3 3 1

dp[3][2] 셀의 숫자 3은 3개의 아이템 중 2개를 선택하는 방법이 3가지라는 것을 의미한다.

‘3개의 아이템 중 2개를 선택하는 방법’을 찾기 위해서는 아래 두 가지 경우를 합친 것이다.

1. ‘2개의 아이템 중 2개를 선택하는 방법’ (dp[2][2])
2. ‘2개의 아이템 중 1개를 선택하는 방법’ (dp[2][1])

더 쉽게 이해

점화식에서 ‘i-1개 중에서 j개를 선택하는 방법의 수’와 ‘i-1개 중에서 j-1개를 선택하는 방법의 수’를 합하는 이유는 다음과 같다.

‘3C2’를 생각해보면, 3개의 아이템(A, B, C) 중에서 2개를 선택하는 방법을 찾아야 한다.

• 2개 중 2개를 선택하는 방법은 A,B 중에서 2개를 선택하는 방법을 찾는다.
• 2개 중 1개를 선택하는 방법은 A,B 두 개 중에서 하나를 선택하고, 그 다음 C를 추가로 선택하는 경우를 의미하며 이 경우는 AC, BC 두 가지이다.

따라서 이 두 가지 경우를 합하면, 3개의 아이템 중에서 2개를 선택하는 모든 경우의 수를 구할 수 있는 것이다.