Pascal's rule

Original article: w:Pascal's rule

Not to be confused with Pascal's law.

수학(mathematics)에서, 파스칼의 규칙(Pascal's rule 또는 Pascal's formula)은 이항 계수에 대한 조합론적(combinatorial) 항등식(identity)입니다. 그것은 양의 자연수(natural numbers) n 및 k에 대해 다음임을 말합니다:

${n-1 \choose k}+{n-1 \choose k-1}={n \choose k},$

여기서 ${n \choose k}$는 이항 계수입니다; 이것의 한 가지 해석은 (1 + x)ⁿ의 전개(expansion)에서 x^k 항의 계수입니다. n 및 k의 상대적 크기에 대한 제한이 없는데, 왜냐하면, 만약 n < k이면, 이항 계수의 값은 영이고 항등은 유효하게 남기 때문입니다.

파스칼의 규칙은 다항 계수(multinomial coefficient)에 적용하기 위해 역시 일반화될 수 있습니다.

Combinatorial proof

파스칼의(Pascal's) 규칙은 직관적인 조합론적 의미를 지니고 있으며, 즉, 이 세는 증명에서 명확하게 표현됩니다.

증명. ${n \choose k}$는 n 원소를 가진 집합으로부터 k 원소를 가진 부분-집합(subsets)의 숫자와 같음을 상기하십시오. 하나의 특정 원소는 n 원소를 가진 집합에서 고유하게 레이블된 X로 가정하십시오.

X를 포함하는 k 원소의 부분-집합을 구성하기 위해, X를 선택하고 집합에서 남아있는 n-1 원소로부터 k-1 원소를 선택하십시오. ${n-1 \choose k-1}$ 그러한 부분-집합이 있습니다.

X를 포함하지 않는 k 원소의 부분-집합을 구성하기 위해, 집합에서 남아있는 n-1 원소로부터 k 원소를 선택하십시오. ${n-1 \choose k}$ 그러한 부분-집합이 있습니다.

k 원소의 모든 각 부분-집합은 X를 포함하거나 그렇지 않을 수 있습니다. n 원소의 집합에서 k 원소를 갖는 부분-집합의 전체 숫자는 X를 포함하는 부분-집합의 숫자와 X를 포함하지 않는 부분-집합의 숫자의 합, ${n-1 \choose k-1}+{n-1 \choose k}$입니다.

이것은 ${n \choose k}$와 같습니다; 그러므로, ${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$입니다.

Algebraic proof

대안적으로, 이항 경우의 대수적 유도는 다음입니다:

${\begin{aligned}{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{aligned}}$

Generalization

파스칼의 규칙은 다항 계수로 일반화될 수 있습니다. $p\geq 2$, $k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{*}$, 및 $n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1$를 만족하는 임의의 정수 p에 대해, 다음입니다:

${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}}$

여기서 ${n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}$는 $(x_{1}+x_{2}+\dots +x_{p})^{n}$ 전개에서 $x_{1}^{k_{1}}x_{2}^{k_{2}}\dots x_{p}^{k_{p}}$ 항의 계수입니다.

이 일반적인 경우에 대해 대수적 유도는 다음처럼 입니다. p를 $p\geq 2$, $k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{*}$, 및 $n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1$를 만족하는 정수로 놓습니다. 그런-다음, 다음입니다:

${\begin{aligned}&{}\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{aligned}}$

See also

• Pascal's triangle

Bibliography

• Merris, Russell. Combinatorics. John Wiley & Sons. 2003 ISBN 978-0-471-26296-1

External links

• "Central binomial coefficient". PlanetMath.
• "Binomial coefficient". PlanetMath.

This article incorporates material from Pascal's triangle on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

This article incorporates material from Pascal's rule proof on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.