수학(mathematics)에서, 파스칼의 규칙(Pascal's rule 또는 Pascal's formula)은 이항 계수에 대한 조합론적(combinatorial) 항등식(identity)입니다. 그것은 양의 자연수(natural numbers) n 및 k에 대해 다음임을 말합니다:
\(\quad\displaystyle {n-1\choose k} + {n-1\choose k-1} = {n\choose k},\)
여기서 \(\displaystyle {n\choose k}\)는 이항 계수입니다; 이것의 한 가지 해석은 \((1+x)^n\)의 전개(expansion)에서 \(x^k\) 항의 계수입니다. n 및 k의 상대적 크기에 대한 제한이 없는데, 왜냐하면, 만약 n < k이면, 이항 계수의 값은 영이고 항등은 유효하게 남기 때문입니다.
파스칼의 규칙은 다항 계수(multinomial coefficient)에 적용하기 위해 역시 일반화될 수 있습니다.
Combinatorial proof
파스칼의(Pascal's) 규칙은 직관적인 조합론적 의미를 지니고 있으며, 즉, 이 세는 증명에서 명확하게 표현됩니다.
증명. \(\displaystyle {n\choose k}\)는 n 원소를 가진 집합으로부터 k 원소를 가진 부분-집합(subsets)의 숫자와 같음을 상기하십시오. 하나의 특정 원소는 n 원소를 가진 집합에서 고유하게 레이블된 X로 가정하십시오.
X를 포함하는 k 원소의 부분-집합을 구성하기 위해, X를 선택하고 집합에서 남아있는 n-1 원소로부터 k-1 원소를 선택하십시오. \(\displaystyle {n-1\choose k-1}\) 그러한 부분-집합이 있습니다.
X를 포함하지 않는 k 원소의 부분-집합을 구성하기 위해, 집합에서 남아있는 n-1 원소로부터 k 원소를 선택하십시오. \(\displaystyle {n-1\choose k}\) 그러한 부분-집합이 있습니다.
k 원소의 모든 각 부분-집합은 X를 포함하거나 그렇지 않을 수 있습니다. n 원소의 집합에서 k 원소를 갖는 부분-집합의 전체 숫자는 X를 포함하는 부분-집합의 숫자와 X를 포함하지 않는 부분-집합의 숫자의 합, \(\displaystyle {n-1\choose k-1} + {n-1\choose k}\)입니다.
이것은 \(\displaystyle {n\choose k}\)와 같습니다; 그러므로, \(\displaystyle {n\choose k} = {n-1\choose k-1} + {n-1\choose k}\)입니다.
Algebraic proof
대안적으로, 이항 경우의 대수적 유도는 다음입니다:
\(\quad\displaystyle \begin{align}
{ n-1 \choose k } + { n-1 \choose k-1} & = \frac{(n-1)!}{k! (n - 1 - k)!} + \frac{(n-1)!}{(k - 1)!(n - k)!} \\
& = (n-1)! \left[ \frac{n - k}{k!(n - k)!} + \frac{k}{k!(n - k)!}\right] \\
& = (n-1)! \frac{n}{k!(n - k)!} \\
& = \frac{n!}{k!(n - k)!} \\
& = \binom{n}{k}.
\end{align}
\)
Generalization
파스칼의 규칙은 다항 계수로 일반화될 수 있습니다. \(\displaystyle p \ge 2\), \(\displaystyle k_1, k_2, k_3,\dots, k_p \in \mathbb{N}^* \), 및 \(\displaystyle n=k_1+k_2+k_3+ \cdots +k_p \ge 1\)를 만족하는 임의의 정수 p에 대해, 다음입니다:
\(\quad\displaystyle {n-1\choose k_1-1,k_2,k_3, \dots, k_p}+{n-1\choose k_1,k_2-1,k_3,\dots, k_p}+\cdots+{n-1\choose k_1,k_2,k_3,\dots,k_p-1} = {n\choose k_1, k_2, k_3, \dots , k_p}\)
여기서 \(\displaystyle {n\choose k_1, k_2, k_3, \dots , k_p}\)는 \(\displaystyle (x_1+x_2+\dots+x_p)^{n}\) 전개에서 \(\displaystyle x_1^{k_1}x_2^{k_2}\dots x_p^{k_p}\) 항의 계수입니다.
이 일반적인 경우에 대해 대수적 유도는 다음처럼 입니다. p를 \(\displaystyle p \ge 2\), \(\displaystyle k_1, k_2, k_3,\dots, k_p \in \mathbb{N}^* \), 및 \(\displaystyle n=k_1+k_2+k_3+ \cdots +k_p \ge 1\)를 만족하는 정수로 놓습니다. 그런-다음, 다음입니다:
\(\quad\displaystyle
\begin{align}
& {} \quad {n-1\choose k_1-1,k_2,k_3, \dots, k_p}+{n-1\choose k_1,k_2-1,k_3,\dots, k_p}+\cdots+{n-1\choose k_1,k_2,k_3,\dots,k_p-1} \\
& = \frac{(n-1)!}{(k_1-1)!k_2!k_3! \cdots k_p!} + \frac{(n-1)!}{k_1!(k_2-1)!k_3!\cdots k_p!} + \cdots + \frac{(n-1)!}{k_1!k_2!k_3! \cdots (k_p-1)!} \\
& = \frac{k_1(n-1)!}{k_1!k_2!k_3! \cdots k_p!} + \frac{k_2(n-1)!}{k_1!k_2!k_3! \cdots k_p!} + \cdots + \frac{k_p(n-1)!}{k_1!k_2!k_3! \cdots k_p!} = \frac{(k_1+k_2+\cdots+k_p) (n-1)!}{k_1!k_2!k_3!\cdots k_p!} \\
& = \frac{n(n-1)!}{k_1!k_2!k_3! \cdots k_p!} = \frac{n!}{k_1!k_2!k_3! \cdots k_p!}
= {n\choose k_1, k_2, k_3, \dots , k_p}.
\end{align}
\)
See also
References
- Mazur, David R. (2010), Combinatorics / A Guided Tour, Mathematical Association of America, p. 60, ISBN 978-0-88385-762-5
- Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, p. 44, ISBN 978-0-13-602040-0
- Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, p. 144, ISBN 978-0-13-602040-0
Bibliography
- Merris, Russell. Combinatorics. John Wiley & Sons. 2003 ISBN 978-0-471-26296-1
External links
