정리 1.4.1. 이항 정리_{(binomial theorem)}

$n$이 음이 아닌 정수일 때, \begin{align*} (a + b)^{n} & = \sum_{k=0}^{n} \binom{n}{k}a^{n-k}b^{r} \\[1ex] & = \binom{n}{0}a^{n} + \binom{n}{1}a^{n-1}b + \cdots + \binom{n}{n}b^{n}. \end{align*}

$ $

참고. 이항정리에서 $a = 1$, $b = x$로 두면 다음을 얻는다. \[ (1 + x)^{n} = \sum_{k=0}^{n} \binom{n}{k}x^{k} = \binom{n}{0} + \binom{n}{1}x + \cdots + \binom{n}{n}x^{n}. \]

$ $

예제 1.4.2.
Q. $(2a - b)^{10}$의 전개식에서 다음을 구하여라.

1. $a^4b^6$의 계수를 구하여라.
2. 각 항의 계수의 합을 구하여라.

A.

1. 이항정리에 의해 \[ \binom{10}{4} 2^4 (-1)^{6} = 3360. \]
2. 이항정리에 의해 \begin{align*} (2a - b)^{10} & = \sum_{k=0}^{n} \binom{10}{k}(2a)^{n-k}(-b)^{k} \\[1ex] & = \sum_{k=0}^{n} \binom{10}{k}2^{n-k}(-1)^{k}a^{n-k}b^{k} \end{align*} 을 얻는다. 이제 위 식의 양변에 $a = b = 1$을 대입하면 우변은 각 항의 계수의 합과 같고, 좌변은 $(2 \cdot 1 - 1)^{10} = 1$을 얻는다. $ $

$ $

예제 1.4.3.
Q. $(2a - b)^{3}(a + 3b)^{3}$의 전개식에서 $a^{2}b^{4}$의 계수를 구하여라.
A. 다음과 같이 경우를 나누어 생각한다.

• 첫번째 항에서 $b^3$, 두번째 항에서 $a^2b$를 선택하는 경우: \[ \binom{3}{3} 2^{0} (-1)^{3} \binom{3}{1} 1^{2} 3^{1} = -9 \]
• 첫번째 항에서 $ab^2$, 두번째 항에서 $ab^2$을 선택하는 경우: \[ \binom{3}{2} 2^{1} (-1)^{2} \binom{3}{2} 1^{1} 3^{2} = 162 \]
• 첫번째 항에서 $a^2b$, 두번째 항에서 $b^3$을 선택하는 경우: \[ \binom{3}{1} 2^{2} (-1)^{1} \binom{3}{3} 1^{0} 3^{3} = -324 \]

따라서 $a^{2}b^{4}$의 계수는 $- 9 + 162 - 324 = -171$. $ $

$ $

예제 1.4.4.
Q. 이항정리를 이용하여 다음 등식을 증명하여라.

1. $\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$

$ $

2. $\displaystyle \sum_{k=1}^{n} k \binom{n}{k} = n 2^{n-1}$

$ $

3. $\displaystyle \sum_{k=1}^{n} k^2 \binom{n}{k} = n(n+1) 2^{n-2}$

$ $

4. $\displaystyle \sum_{k \geq 0} \binom{n}{2k} = \sum_{k \geq 0} \binom{n}{2k+1} = 2^{n-1}$

$ $

5. $\displaystyle \sum_{k=0}^{n} \frac{1}{k+1} \binom{n}{k} = \frac{1}{n+1} (2^{n+1} - 1)$

$ $

6. $\displaystyle \sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$

A.

1. 이항정리에서 $a = b = 1$을 대입하고 양변을 정리하면 원하는 등식을 얻는다.

$ $

2. $a = 1,\, b = x$로 둔 이항정리를 생각하자. \[ (1 + x)^{n} = \sum_{k=0}^{n} \binom{n}{k}x^{k} \] 위 식의 양변을 $x$에 대하여 미분하면, \[ n (1 + x)^{n-1} = \sum_{k=1}^{n} k \binom{n}{k} x^{k-1} \] 을 얻는다. 이제 위 식의 양변에 $x=1$을 대입하고 식을 정리하면 원하는 등식을 얻는다.

$ $

3. $a = 1,\, b = x$로 둔 이항정리를 생각하자. \[ (1 + x)^{n} = \sum_{k=0}^{n} \binom{n}{k}x^{k} \] 위 식의 양변을 $x$에 대하여 두번 미분하면, \[ n(n-1) (1 + x)^{n-2} = \sum_{k=2}^{n} k(k-1) \binom{n}{k} x^{k-2} \] 을 얻는다. 이제 위 식에 양변에 $x=1$을 대입하면, \begin{align*} n(n-1) 2^{n-2} & = \sum_{k=2}^{n} k(k-1) \binom{n}{k} \\[1ex] & = \sum_{k=2}^{n} k^2 \binom{n}{k} - \sum_{k=2}^{n} k \binom{n}{k} \\[1ex] & = \sum_{k=1}^{n} k^2 \binom{n}{k} - \sum_{k=1}^{n} k \binom{n}{k} \\[1ex] & = \sum_{k=1}^{n} k^2 \binom{n}{k} - n 2^{n-1}. \end{align*} 위 식의 마지막 등식은 $\myblue{\text{(b)}}$에 의해 성립한다. 이제 위 식을 정리하면, \begin{align*} \sum_{k=1}^{n} k^2 \binom{n}{k} & = n(n-1) 2^{n-2} + n 2^{n-1} \\[1ex] & = n(n+1) 2^{n-2}. \end{align*}

$ $

4. 이항정리에서 $a = 1,\, b = -1$을 대입하면, \[ (1 - 1)^{n} = \sum_{k=0}^{n} \binom{n}{k}1^{n-k}(-1)^{k} \] 위 식을 정리하면, \[ 0 = \sum_{k=0}^{n} \binom{n}{k}(-1)^{k} = \sum_{k \geq 0} \binom{n}{2k} - \sum_{k \geq 0} \binom{n}{2k+1} \] 따라서 위 식과 $\myblue{\text{(a)}}$에 의해 원하는 등식을 얻는다.

$ $

5. $a = 1,\, b = x$로 둔 이항정리를 생각하자. \[ (1 + x)^{n} = \sum_{k=0}^{n} \binom{n}{k}x^{k} \] 위 식의 양변에 정적분 $\int_{0}^{1} \cdot dx$를 취하면, \begin{align*} \int_{0}^{1} (1+x)^{n} dx & = \frac{1}{1+n} (1+x)^{n+1} \bigg|_{0}^{1} \\[1ex] & = \frac{1}{n+1} (2^{n+1} - 1), \\[3ex] \int_{0}^{1} \bigg( \sum_{k=0}^{n} \binom{n}{k}x^{k} \bigg) dx & = \sum_{k=0}^{n} \binom{n}{k} \bigg( \int_{0}^{1} x^{k} dx \bigg) \\[1ex] & = \sum_{k=0}^{n} \binom{n}{k} \bigg( \frac{1}{k+1} x^{k+1} \bigg|_{0}^{1} \bigg) \\[1ex] & = \sum_{k=0}^{n} \binom{n}{k} \frac{1}{k+1} \\[1ex] \end{align*} 가 되어 원하는 등식을 얻는다.

$ $

6. 다음 항등식 \[ (1+x)^{2n} = (1+x)^{n}(1+x)^{n} \] 의 양변을 각각 이항정리를 이용하여 전개하면, \begin{align*} \sum_{k=0}^{2n} \binom{2n}{k} x^{k} & = \bigg( \sum_{k=0}^{n} \binom{n}{k} x^{k} \bigg)\bigg( \sum_{k=0}^{n} \binom{n}{k} x^{k} \bigg) \\[1ex] & = \sum_{k=0}^{2n} \bigg( \sum_{i=0}^{k} \binom{n}{i} \binom{n}{k-i} \bigg) x^{k}. \end{align*} 를 얻는다. 이제 위 식의 양변에서 $x^n$의 계수를 비교하면 \[ \binom{2n}{n} = \sum_{i=0}^{n} \binom{n}{i} \binom{n}{n-i} = \sum_{i=0}^{n} \binom{n}{i}^{2}. \tag*{$\myblue{\blacksquare}$} \]

$ $

예제 1.4.5.
Q. 집합 $A = \{1,\, 2,\, \ldots,\, n\}$를 서로소인 $A$의 두 부분집합들의 순서쌍 $(P,\, Q)$로 나누는 경우의 수를 구하여라.
A1. 우선 $A$의 적당한 부분집합 $P$를 택하고 나서 $Q$는 $A \setminus P$의 임의의 부분집합을 택하면 된다. 이제 $\abs{P} = k$라 가정해 보자. 그러면 원소의 개수가 $k$개인 부분집합 $P$를 택하는 경우의 수는 $\binom{n}{k}$이고, $\abs{A \setminus P} = n-k$이므로 $Q$가 될 수 있는 $A \setminus P$의 임의의 부분집합의 개수는 $2^{n-k}$이다. 따라서 \[ \binom{n}{k} 2^{n-k} \] 를 얻는다. 이제 $k = 0,\ 1,\, \ldots,\, n$의 값을 택할 수 있고, 이는 모두 동시에 발생하지 않으므로 전체 경우의 수는 \[ \sum_{k=0}^{n} \binom{n}{k} 2^{n-k} = (2 + 1)^{n} = 3^n. \tag*{$\myblue{\blacksquare}$} \] A2. $A = \{1,\, 2,\, \ldots,\, n\}$의 부분집합은 각 원소가 $0$ 또는 $1$인 $n$차원 벡터와 일대일대응이다. 예를 들어 $n=6$인 경우, \[ P = \{1,\, 2,\, 3,\, 6\} \quad \leftrightarrow \quad [ 1,\, 1,\, 1,\, 0,\, 0,\, 1 ] \] 과 같이 대응 관계를 줄 수 있다. 같은 방법으로 부분집합들의 순서쌍 $(P,\, Q)$ 각 원소가 $0$ 또는 $1$인 $2 \times n$ 행렬과 일대일대응을 줄 수 있다. 마찬가지로 $n=6$이라 하면, \[ \begin{aligned} P & = \{1,\, 2,\, 3,\, 6\} \\[1ex] Q & = \{2,\, 4,\, 6\} \end{aligned} \quad \leftrightarrow \quad \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix} \] 이제 두 부분집합 $P,\, Q$가 서로소이기 위해서는 $2 \times n$ 행렬에서 $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$이 존재해서는 안된다. 따라서 선택 가능한 열의 경우의 수는 $\begin{bmatrix} 0 \\ 0 \end{bmatrix},\, \begin{bmatrix} 1 \\ 0 \end{bmatrix},\, \begin{bmatrix} 0 \\ 1 \end{bmatrix}$의 세가지이고, 이를 중복을 허락하여 $n$개를 선택하면 되므로 전체 경우의 수는 $3^n$이 된다. $ $

$ $

문자 $A$가 $n_1$개, $B$가 $n_2$개, $C$가 $n_3$개 있다고 가정하자. 편의상 $n = n_1 + n_2 + n_3$라 하면, $A,\, B,\, C$를 모두 일렬로 나열하는 경우의 수는 정리 1.2.6에 의해 \[ \frac{n!}{n_1! \cdot n_2! \cdot n_3!} \] 으로 구할 수 있다. 위 경우의 수는 전체 $n$개의 자리에서 $A$가 들어갈 $n_1$의 자리를 선택하고, 나머지 $n - n_1$개의 자리에서 $B$가 들어갈 자리를 선택하고, 나머지 $n - n_1 - n_2$개의 자리에 모두 $C$를 배열하는 경우의 수와 같다. 즉, \[ \frac{n!}{n_1! \cdot n_2! \cdot n_3!} = \binom{n}{n_1} \binom{n - n_1}{n_2} \binom{n - n_1 - n_2}{n_3} \] 가 성립한다. 이를 일반화 하면 $n = n_1 + n_2 + \cdots n_k$에 대하여 \[ \frac{n!}{n_1! \cdot n_2! \cdots n_k!} = \binom{n}{n_1} \binom{n - n_1}{n_2} \cdots \binom{n - n_1 - \cdots - n_{k-1}}{n_k} \] 가 성립한다. 위 값을 다항계수_{(multinomial coefficient)}라 하고 기호로 간단히 \[ \binom{n}{n_1,\, n_2,\, \ldots,\, n_k} \] 로 나타낸다.

$ $

참고. $n_1 = r$, $n_2 = n-r$으로 두면 $n_1 + n_2 = n$이므로 다항계수 \[ \binom{n}{n_1, n_2} = \frac{n!}{n_1! n_2!} = \frac{n!}{r!(n-r)!} = \binom{n}{r} \] 이 되어 다항계수는 이항계수의 자연스러운 확장임을 알 수 있다. $ $

$ $

정리 1.4.6. 다항 정리_{(multinomial theorem)}

$n$이 음이 아닌 정수일 때, \begin{align*} & (a_1 + a_2 + \cdots + a_k)^n \\[1ex] & \qquad = \sum_{(n_1, n_2, \ldots, n_k)} \binom{n}{n_1,\, n_2,\, \ldots,\, n_k} a_{1}^{n_1} a_{2}^{n_2} \cdots a_{k}^{n_k} \\[1ex] & \qquad = \sum_{(n_1, n_2, \ldots, n_k)} \frac{n!}{n_1! \cdot n_2! \cdots n_k!} a_{1}^{n_1} a_{2}^{n_2} \cdots a_{k}^{n_k} \end{align*} 가 성립한다. 단, $(n_1,\, n_2,\, \ldots,\, n_k)$는 $n_1 + n_2 + \cdots + n_k = n$을 만족하는 음이 아닌 정수해이다.

$ $

예제 1.4.7.
Q. $(2a - b + c)^{10}$의 전개식에서 $a^4b^4c^2$의 계수를 구하여라.
A. 다항정리에 의해 \[ \binom{10}{4, 4, 2} 2^4 (-1)^4 1^2 = \frac{10! \cdot 2^4}{4! \cdot 4! \cdot 2!} = 50400. \tag*{$\myblue{\blacksquare}$} \]

$ $

예제 1.4.8.
Q. $(1 + x + x^2)^{10}$의 전개식에서 $x^{16}$의 계수를 구하여라.
A. 다항정리에 의해 \begin{align*} (1 + x + x^2)^{10} & = \sum_{a+b+c=10} \binom{10}{a, b, c} 1^{a} x^{b} (x^2)^{c} \\[1ex] & = \sum_{a+b+c=10} \binom{10}{a, b, c} x^{b+2c} \end{align*} 따라서 $x^{10}$의 계수는 \[ \sum_{\substack{a+b+c=10 \\ b+2c=16}} \binom{10}{a, b, c} \] 와 같다. 이제 두 선형방정식 $a+b+c=10$과 $b+2c=16$을 동시에 만족하는 음이 아닌 정수해는 ($b+2c=16$이 성립하기 위해서는 $b$가 짝수여야만 하므로 경우를 나누어 생각하면) $(2,\, 0,\, 8)$, $(1,\, 2,\, 7)$, $(0,\, 4,\, 6)$ 세가지가 존재한다. 따라서 \[ \binom{10}{2, 0, 8} + \binom{10}{1, 2, 7} + \binom{10}{0, 4, 6} = 615. \tag*{$\myblue{\blacksquare}$} \]

$ $

예제 1.4.9.
Q. 다항식 $(a_1 + a_2 + \cdots + a_k)^n$의 전개식에서 모든 항의 개수를 구하여라.
A. 위 전개식의 각각의 항은 다항정리에 의해 $a_{1}^{n_1} a_{2}^{n_2} \cdots a_{k}^{n_k}$ 꼴로 주어지고 이때 $(n_1,\, n_2,\, \ldots,\, n_k)$는 $n_1 + n_2 + \cdots + n_k = n$을 만족하는 음이 아닌 정수해이므로, 전체 경우의 수는 \[ {}_{k}H_{n} = {}_{k+n-1}C_{n} = \frac{(k+n-1)!}{n!(k-1)!}. \tag*{$\myblue{\blacksquare}$} \]

$ $

위에서 살펴본 이항계수 $\binom{n}{r}$는 $n,\, r$이 모두 음이 아닌 정수일 때만 정의 되었었다. 이제 다음과 같이 이항계수의 정의를 $n$이 임의의 실수인 경우로 확장해보자: 임의의 실수 $\alpha$와 음이 아닌 정수 $k$에 대하여 \[ \binom{\alpha}{r} = \begin{cases} \dfrac{\alpha(\alpha - 1)(\alpha - 2) \cdots (\alpha - r + 1)}{r!} & \text{if} \;\; r \geq 1 \\[1ex] 1 & \text{if} \;\; r = 0 \end{cases} \] 위와 같이 정의된 수를 일반화된 이항계수_{(generalized binomial coefficient)}라 한다.

$ $

예제 1.4.10.
Q. 양의 정수 $n$과 음이 아닌 정수 $r$에 대하여 다음 식을 증명하여라. \[ \binom{-n}{r} = (-1)^{r} {}_{n}H_{r} = (-1)^{r} \binom{n+r-1}{r} \] A. 일반화된 이항계수의 정의에 의해 \begin{align*} \binom{-n}{r} & = \frac{(-n)(-n-1)(-n-2) \cdots (-n-r+1)}{r!} \\[1ex] & = (-1)^{r} \frac{n(n+1)(n+1) \cdots (n+r-1)}{r!} \end{align*} 이므로 원하는 식을 얻는다. $ $

$ $

정리 1.4.11. 일반화된 이항 정리_{(generalized binomial theorem)}

$\alpha$가 임의의 실수이고 $\abs{a} > \abs{b}$일 때, \[ (a + b)^{\alpha} = \sum_{r=0}^{\infty} \binom{\alpha}{r} a^{\alpha - r} b^{r}. \] 특히, $\abs{x} < 1$인 경우, \[ (1 + x)^{\alpha} = \sum_{r=0}^{\infty} \binom{\alpha}{r} x^{r}. \]

$ $

예제 1.4.12.
Q. 일반화된 이항정리를 이용하여 다음 식을 전개하여라.

1. $\displaystyle \frac{1}{1-x}$

$ $

2. $\displaystyle \frac{1}{\sqrt{1 + 2x}}$

A.

1. $\begin{aligned}[t] \frac{1}{1-x} & = (1 - x)^{-1} \\[1ex] & = \sum_{r=0}^{\infty} \binom{-1}{r} (-x)^{r} \\[1ex] & = \sum_{r=0}^{\infty} (-1)^{r} {}_{1}H_{r} (-1)^{r} x^{r} \\[1ex] & = \sum_{r=0}^{\infty} x^{r} \\[1ex] & = 1 + x + x^2 + x^3 + \cdots \end{aligned}$

$ $

2. $\begin{aligned}[t] \frac{1}{\sqrt{1 + 2x}} & = (1 + 2x)^{-\frac{1}{2}} \\[1ex] & = \sum_{r=0}^{\infty} \binom{-\frac{1}{2}}{r} (2x)^{r} \\[1ex] & = 1 + \binom{-\frac{1}{2}}{1} (2x) + \binom{-\frac{1}{2}}{2} (2x)^{2} + \binom{-\frac{1}{2}}{3} (2x)^{3} + \cdots \\[1ex] & = 1 - x + \frac{3}{2} x^2 - \frac{5}{2} x^3 + \cdots \end{aligned}$

$ $

예제 1.4.13.
Q. 다음 식 $\displaystyle \frac{1 + x}{(1 - x)^3}$의 전개식에서 $x^n$의 계수를 구하여라.
A. 먼저 위 식을 아래와 같이 정리하자. \[ \frac{1 + x}{(1 - 2x)^3} = (1 - 2x)^{-3} + x (1 - 2x)^{-3} \] 이제 일반화된 이항정리를 이용하여 $(1 - 2x)^{-3}$에서 $x^n$과 $x^{n-1}$의 계수를 각각 구하면 \begin{align*} \text{$x^n$의 계수 : } & \binom{-3}{n}(-1)^{n} = \binom{n+2}{n}, \\[1ex] \text{$x^{n-1}$의 계수 : } & \binom{-3}{n-1}(-1)^{n-1} = \binom{n+1}{n-1}. \end{align*} 따라서 주어진 전개식에서 $x^n$의 계수는 \begin{align*} \binom{n+2}{n} + \binom{n+1}{n-1} & = \frac{(n+2)(n+1)}{2} + \frac{(n+1)n}{2} \\[1ex] & = (n+1)^2. \tag*{$\myblue{\blacksquare}$} \end{align*}

$ $