수학(mathematics)에서, 파스칼의 삼각형(Pascal's triangle)은 이항 계수(binomial coefficient)의 삼각형 배열(triangular array)입니다. 서구 세계(Western world)의 많은 곳에서, 그것은 비록 다른 수학자들, 인도(India), 페르시아(Persia, 이란), 중국(China), 독일(Germany), 및 이탈리아(Italy)에서 파스칼보다 몇 세기 전에 그것을 연구했음에도 불구하고, 프랑스의 수학자 블레즈 파스칼(Blaise Pascal)의 이름을 따서 지어졌습니다.
파스칼 삼각형의 행은 최상단에서 행 n = 0 (0-번째 행)부터 시작하여 전통적으로 열거됩니다. 각 행에서 엔트리는 k = 0과 함께 시작하는 왼쪽부터 숫자가 매겨지고 인접한 행에서 숫자에 비해 보통 서로 교체됩니다. 삼각형은 다음 방식으로 구성될 수 있습니다: 행 0 (맨 위 행)에서, 고유한 비-영 엔트리 1이 있습니다. 각 후속 행의 각 엔트리는 왼쪽 위의 숫자와 오른쪽의 위의 숫자를 더함으로써 구성되며, 빈 엔트리는 0으로써 취급합니다. 예를 들어, 첫 번째 (또는 임의의 다른) 행의 초기 숫자는 (0과 1의 합) 1이며, 반면에 세 번째 행에서 숫자 1과 3은 네 번째 행에서 숫자 4를 생성하기 위해 더해집니다.
Formula
\(\displaystyle
\begin{array}{c}
1 \\
1 \quad 1 \\
1 \quad 2 \quad 1 \\
1 \quad 3 \quad 3 \quad 1 \\
1 \quad 4 \quad 6 \quad 4 \quad 1 \\
1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1 \\
1 \quad 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad 1 \\
1 \quad 7 \quad 21 \quad 35 \quad 35 \quad 21 \quad 7 \quad 1 \\
\end{array}
\)
파스칼의 삼각형의 n번째 행이고 k번째 열에서 엔트리는 \(\displaystyle \tbinom{n}{k}\)로 표시됩니다. 예를 들어, 제일 위의 행에서 고유한 비-영 엔트리는 \(\displaystyle \tbinom{0}{0} = 1\)입니다. 이 표기법과 함께, 이전 단락의 구성은 다음으로 쓰일 수 있을 것입니다: 임의의 비-음의 정수 n 및 0과 n 사이의 임의의 정수 k에 대해, 계산됩니다:
\(\quad\displaystyle {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\).
이항 계수에 대해 이 재귀는 파스칼의 규칙(Pascal's rule)으로 알려져 있습니다.
파스칼의 삼각형은 더 높은 차원(dimension)의 일반화를 가집니다. 삼-차원 버전은 파스칼의 피라미드(Pascal's pyramid) 또는 파스칼의 사면체(Pascal's tetrahedron)로 불리지만, 일반적인 버전은 파스칼의 심플렉스(Pascal's simplices)로 불립니다.
History
파스칼의 삼각형을 형성하는 숫자의 패턴은 파스칼 시대 이전에 잘 알려져 있었습니다. 파스칼은 삼각형의 숫자에 대한 이전에 언급되지 않은 많은 사용을 혁신했으며, 그는 아마도 삼각형에 특별히 전념한 최초의 알려진 수학적 논문(treatise) Traité du triangle arithmétique (1654; 1665년에 출판됨)에서 포괄적으로 설명한 것을 사용합니다. 수세기 전에, 숫자에 대한 논의는 조합론(combinatorics)과 이항 숫자의 인도(Indian)의 연구 및 그림 숫자(figurate numbers)의 그리스(Greeks)의 연구의 문맥에서 발생했습니다.
나중의 주석으로부터, 그것은 이항 계수와 그것을 생성하기 위한 덧셈 공식, \(\displaystyle \tbinom{n}{r}=\tbinom{n-1}{r}+\tbinom{n-1}{r-1}\)은 기원전 2세기 또는 그 이전에 핀갈라(Pingala)에 의해 알려진 것으로 나타납니다. 핀갈라의 업적은 오직 단편적으로 살아남았지만, 505년경, 주석자 브라미히러(Varāhamihira)는 덧셈 공식의 명확한 설명을 제공했었고, 같은 규칙의 보다 자세한 설명은, 975년경, 할라유터(Halayudha)에 의해 제공되었습니다. 할라유터는, 메루 산의 계단(Staircase of Mount Meru), Meru-prastaara에 대한 모호한 참조를 역시 설명했으며, 삼각형으로 이들 숫자의 배열의 최초의 생존하는 설명을 제공합니다. 대략 850년에서, 자이나교(Jain)의 수학자 마하비러(Mahāvīra)는 현대 공식 \(\displaystyle \tbinom{n}{r}=\tfrac{n!}{r!(n-r)!}\)과 동등한, 곱셈을 사용하여, 이항 계수에 대해 다른 공식을 제공했습니다. 1068년에서, 처음 16행의 4열이 수학자 바투빨라(Bhattotpala)에 의해 제공되었으며, 그는 이들 숫자에 대해 덧셈과 곱셈 공식을 동등하게 다룬 최초의 기록된 수학자였습니다.
거의 동시대에, 페르시아(Persian)의 수학자 알-카라지(Al-Karaji) (953–1029)는 파스칼의 삼각형의 첫 번째 설명이 포함된 지금은 잃어버린 책을 썼었습니다. 그것은 나중에 페르시아의 시인-천문학자-수학자 오마르 카야얌(Omar Khayyám) (1048–1131)에 의해 다사 나타났습니다; 따라서 그 삼각형은 이란(Iran)에서 카야얌 삼각형(Khayyam triangle)으로 역시 참조됩니다. 이항 정리(binomial theorem)를 포함하여, 삼각형과 관련된 여러가지 정리가 알려져 있었습니다. 카야얌은 이항 전개, 및 그러므로 이항 계수에 기초한 n번째 근(nth roots)을 찾는 방법을 사용했습니다.
파스칼의 삼각형은 11세기 초 중국에서 중국의 수학자 고 헌(Jia Xian) (1010–1070)의 연구를 통해 알려졌습니다. 13세기에서, 양 휘(Yang Hui) (1238–1298)는 삼각형을 제시했고 따라서 그것은 여전히 중국(China)에서 양 휘의 삼각형(Yang Hui's triangle, 杨辉三角; 楊輝三角)으로 불립니다.
서구에서, 이항 계수는 14세기 초에서 게르소니데스(Gersonides)에 의해, 그들에 대해 곱셈 공식을 사용하여, 계산되었습니다. 피토스 아피아노스(Petrus Apianus) (1495–1552)는 1527년에서 영업 계산에 관한 그의 책의 전면 삽화(frontispiece)에 가득차게 삼각형을 게시했습니다. 이것은 유럽에서 삼각형의 첫 번째 기록입니다. 미카엘 스티펠(Michael Stifel)은 1544년에서 (각 행에서 두 번째 열에서부터 중간 열까지) 삼각형의 일부분을 게시했으며, 그것을 그림 숫자(figurate number)의 테이블로 묘사했습니다. 이탈리아(Italy)에서, 파스칼의 삼각형은, 1556년에서 삼각형의 여섯 행을 게시한, 이탈리아 대수학자 니콜로 폰타나 타르탈리아(Niccolò Fontana Tartaglia) (1500–1577)의 이름을 따서 타르탈리아의 삼각형(Tartaglia's triangle)으로 참조됩니다. 제롤라모 카르다노(Gerolamo Cardano)는 역시 1570년에서 삼각형뿐만 아니라 그것을 구성하기 위한 덧셈적 및 곱셈적 규칙을 출판했습니다.
파스칼의 산술 삼각형에 관한 논문(Traité du triangle arithmétique)은 1665년에서 출판되었습니다. 이 논문에서, 파스칼은 여러결과를 수집했고 그런-다음 삼각형에 대해 알게 되었고, 확률 이론(probability theory)에서 문제를 해결하기 위해 그것을 사용했습니다. 그 삼각형은 파스칼 이후에 피에르 레몽 드 몽모르(Pierre Raymond de Montmort) (1708)에 의해 "Pascal Poural Poulele Combinedis" (프랑스어: 조합에 대한 파스칼의 테이블) 및 아브라암 드 무아브르(Abraham de Moivre) (1730)에 의해 "Triangulum Arithmeticum PASCALIANUM" (라틴어: 파스칼의 산술 삼각형)으로 나중에 이름지어졌으며, 이것이 현대 서양의 이름이 되었습니다.
Binomial expansions
파스칼의 삼각형은 이항 전개(binomial expansion)에서 발생하는 계수를 결정합니다. 예제에 대해, 다음 전개를 생각해 보십시오:
\(\quad\displaystyle (x+y)^2 = x^2+2xy+y^2=\mathbf{1}x^2y^0 + \mathbf{2}x^1y^1 + \mathbf{1}x^0y^2\)
계수는 파스칼의 삼각형의 두 번째 행에 있는 숫자: 1, 2, 1입니다. 일반적으로, x + y와 같은 이항식(binomial)은 양의 정수 거듭제곱을 올려졌을 때 우리는 다음을 가집니다:
\(\quad\displaystyle (x+y)^n = a_0 x^n+a_1 x^{n-1} y +a_2 x^{n-2}y^2+\cdots + a_{n-1}x y^{n-1}+a_ny^n\),
여기서 전개에서 계수 \(a_i\)는 정확하게 파스칼의 삼각형의 행 n에 있는 숫자입니다. 달리 말해서,
\(\quad\displaystyle a_i = {n \choose i}.\)
이것이 이항 정리(binomial theorem)입니다.
파스칼의 삼각형의 전체 오른쪽 대각은 이들 이항 전개에서 \(y^n\)의 계수에 해당하지만, 다음 대각은 \(xy^{n-1}\)의 계수에 해당하고, 등등입니다.
이항 정리가 어떻게 파스칼 삼각형의 간단한 구조와 관련되는지 알아보기 위해, \((x+1)^n\)의 해당하는 계수의 관점에서 \((x+1)^{n+1}\)의 전개의 계수를 계산하는 문제를 생각해 보십시오 (단순화를 위해 y = 1로 설정함). 그런-다음 다음임을 가정합니다:
\(\quad\displaystyle (x+1)^n=\sum_{i=0}^n a_i x^i.\)
이제
\(\quad\displaystyle (x+1)^{n+1} = (x+1)(x+1)^n = x(x+1)^n + (x+1)^n = \sum_{i=0}^n a_i x^{i+1} + \sum_{i=0}^n a_i x^i.\)
\(\quad\displaystyle \begin{array}{c}
\binom{0}{0} \\
\binom{1}{0} \quad \binom{1}{1} \\
\binom{2}{0} \quad \binom{2}{1} \quad \binom{2}{2} \\
\binom{3}{0} \quad \binom{3}{1} \quad \binom{3}{2} \quad \binom{3}{3} \\
\binom{4}{0} \quad \binom{4}{1} \quad \binom{4}{2} \quad \binom{4}{3} \quad \binom{4}{4} \\
\binom{5}{0} \quad \binom{5}{1} \quad \binom{5}{2} \quad \binom{5}{3} \quad \binom{5}{4} \quad \binom{5}{5}
\end{array}\)
두 합은 다음으로 재구성될 수 있습니다:
\(\quad\displaystyle
\begin{align}
& \sum_{i=0}^{n } a_{i } x^{i+1} + \sum_{i=0}^n a_i x^i \\
& {} = \sum_{i=1}^{n+1} a_{i-1} x^{i } + \sum_{i=0}^n a_i x^i \\
& {} = \sum_{i=1}^{n } a_{i-1} x^{i } + \sum_{i=1}^n a_i x^i + a_0x^0 + a_{n}x^{n+1} \\
& {} = \sum_{i=1}^{n } (a_{i-1} + a_i)x^{i } + a_0x^0 + a_{n}x^{n+1} \\
& {} = \sum_{i=1}^{n } (a_{i-1} + a_i)x^{i } + x^0 + x^{n+1}
\end{align}
\)
(왜냐하면 다항식을 거듭제곱으로 올리는 방법 때문에, \(a_0=a_n=1\)입니다).
우리는 이제 \((x+1)^n\)의 계수 (이것들은 \(a_i\)들입니다)의 관점에서 다항식 \((x+1)^{n+1}\)에 대해 표현을 가지며, 이것은 만약 우리가 그것 위의 직선의 관점에서 한 직선을 표현하기를 원한다면 우리가 필요로 하는 것입니다. 더 위쪽-왼쪽으로부터 더 아래쪽-오른쪽으로 가는 대각선에서 모든 항은 x의 같은 거듭제곱에 해당하고, a-항은 다항식 \((x+1)^n\)의 계수이고, 우리는 \((x+1)^{n+1}\)의 계수를 결정하는 것임을 기억하십시오. 이제, 0 또는 n + 1이 아닌 임의의 주어진 i에 대해, 다항식 \((x+1)^{n+1}\)에서 \(x^i\) 항의 계수는 \(a_{i-1}+a_i\)와 같습니다. 이것은 사실 파스칼의 삼각형 행-단위로 구성하기 위한 간단한 규칙입니다.
이 논증을 이항 정리의 (수학적 귀납법(mathematical induction)에 의한) 증명(proof)으로 바꾸는 것은 어렵지 않습니다. 왜냐하면 \((a+b)^n = b^n (a/b+1)^n\)이므로, 계수는 일반적인 경우의 전개에서 동일합니다.
이항 정리의 흥미로운 결과는 변수 x와 y 둘 다를 1로 설정함으로써 얻어집니다. 이 경우에서, 우리는 \((1+1)^n=2^n\)임을 알고, 그래서 다음입니다:
\(\quad\displaystyle {n \choose 0} + {n \choose 1} + \cdots +{n \choose n-1} + {n \choose n} = 2^n. \)
달리 말해서, 파스칼의 삼각형의 n번째 행에서 엔트리의 합은 2의 n번째 거듭제곱입니다. 이것은 n-원소 집합의 부분-집합의 숫자 (거듭제곱 집합(power set)의 카디널리티)가 \(\displaystyle 2^n\)이라는 명제와 동등한데, 왜냐하면 부분-집합의 숫자는 0에서 완전히 ''n''까지 범위에서 가능한 길이의 각각의 조합의 숫자의 합이라는 것을 관찰함으로써 알 수 있기 때문입니다.
Combinations
파스칼 삼각형의 두 번째 유용한 응용은 조합(combination)의 계산에 있습니다. 예를 들어, (n 선택 k로 불리는) n 대상에서 한 번에 k를 취하는 조합의 숫자는 다음 방정식에 의해 구할 수 있습니다:
\(\quad\displaystyle \mathbf{C}(n,k) = \mathbf{C}_k^n= {_nC_k} = {n \choose k} = \frac{n!}{k!(n-k)!}.\)
그러나 이것은 역시 파스칼 삼각형의 셀에 대해 공식입니다. 계산을 수행하는 것보다는, 우리는 삼각형에서 적절한 엔트리를 간단히 찾을 수 있습니다. 우리가 먼저 행을 가지고 행에서 첫 번째 엔트리로 0으로 숫자를 매기는 것으로 제공하면, 그 답은 행 n에서 엔트리 k에 위치할 것입니다. 예를 들어, 농구 팀에 10명의 선수가 있고 8명을 선택하는 방법이 얼마나 많은지 알고 싶어한다고 가정해 보겠습니다. 그 답은 행 10에서 엔트리 8이며, 이것은 45입니다; 즉, 10 선택 8은 45입니다.
Relation to binomial distribution and convolutions
\(2^n\)으로 나눌 때, 파스칼의 삼각형의 n번째 행은 p = 1/2인 대칭 경우에서 이항 분포(binomial distribution)가 됩니다. 중심 극한 정리(central limit theorem)에 의해, 이 분포는 n이 증가할 때 정규 분포(normal distribution)에 접근합니다. 이것은 조합에 대해 공식에서 포함된 팩토리얼에 대한 스털링의 공식(Stirling's formula)을 적용함으로써 역시 알 수 있습니다.
이것은 두 가지 방법에서 이산 합성곱(convolution)의 연산과 관련됩니다. 첫째, 다항식 곱셈은, 수열 {..., 0, 0, 1, 0, 0, ...}을 1 + x의 거듭제곱을 취하는 것, 따라서 삼각형의 행을 생성하는 것에 해당하는 자체와 반복적으로 합성곱하도록, 정확하게 이산 합성곱에 해당합니다. 둘째, 확률 변수(random variable)에 대해 분포 함수를 자체와 반복적으로 합성곱하는 것은 해당 변수의 n 독립적인 사본의 합에 대해 분포 함수를 계산하는 것에 해당합니다; 이것은 정확히 중앙 극한 정리가 적용되는 상황이고, 따라서 극한에서 정규 분포로 이어집니다.
Patterns and properties
파스칼의 삼각형은 많은 속성을 가지고 숫자의 많은 패턴을 포함합니다.
Rows
- 단일 행의 원소의 합은 그것 바로 전에 오는 행의 합의 두 배입니다. 예를 들어, (제일 위의 행) 행 0은 1의 값을 가지며, 행 1은 2의 값을 가지며, 행 2는 4의 값, 등을 가집니다. 이것은 행에서 모든 항목이 다음 행에서 두 개의 항목: 하나는 왼쪽, 하나는 오른쪽을 생성하기 때문입니다. 행 n의 원소의 합은 \(2^n\)과 같습니다.
- 각 행에서 원소의 곱을 취하면, 곱의 수열 (OEIS에서 수열 A001142)은 자연 로그의 밑, e와 관련됩니다. 구체적으로, 다음으로 수열 \(s_n\)을 정의합니다:
- \(\displaystyle s_n=\prod_{k=0}^{n}\binom{n}{k} = \prod_{k=0}^{n}\frac{n!}{k!(n-k)!}~, ~ n \geq 0.\)
- 그런-다음, 연속적인 행 곱의 비율은 다음입니다:
- \(\displaystyle \frac{s_{n+1}}{s_{n}}=\frac{(n+1)!^{(n+2)}\prod_{k=0}^{n+1}{k!^{-2}}}{n!^{(n+1)}\prod_{k=0}^{n}{k!^{-2}}}
=\frac{(n+1)^n}{n!}\) - 그리고 이들 비율들의 비율은 다음입니다:
- \(\displaystyle \frac{(s_{n+1})(s_{n-1})}{(s_n)^2}=\left(\frac{n+1}{n}\right)^n, ~ n\geq 1.\)
- 위의 방정식의 오른쪽 변은 e의 극한 정의의 형식을 띄고 있습니다:
- \(\displaystyle \textit{e} =\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{n}.\)
- Pi는 닐라간터(Nilakantha) 무한 급수를 통해 파스칼의 삼각형에서 구할 수 있습니다:
- \(\displaystyle \pi=3+\sum_{n=1}^\infty(-1)^{n+1}\frac{\binom{2n+1}{1}}{\binom{2n+1}{2}\binom{2n+2}{2}}\)
- 하나의 행의 그 값은, 만약 각 엔트리가 십진 자릿수로 여겨지면 (및 9보다 큰 숫자는 적절히 올림수로 여겨지면), 11의 거듭제곱입니다 (행 n에 대해, \(11^n\)입니다). 따라서, 행 2에서, ⟨1, 2, 1⟩은 \(11^2\)이 되지만, 행 5에서, ⟨1, 5, 10, 10, 5, 1⟩은 (올림수가 발생 후에) 161,051이 되며, 이것은 \(11^5\)입니다. 이 속성은 \((x+1)^n\)의 이항 전개에서 x = 10으로 설정하고, 십진 시스템으로 값을 조정함으로써 설명됩니다. 그러나 x는 행을 임의의 밑수(any base)에서 값을 표현하는 것을 허용하도록 선택될 수 있습니다.
- 밑수 3에서: \(1\,2\,1_3 = 4^2\,(16)\)
- \(\langle 1, 3, 3, 1\rangle \to 2\,1\,0\,1_3 = 4^3\,(64)\)
- 밑수 9에서: \(1\,2\,1_9 = 10^2\,(100)\)
- \(1\,3\,3\,1_9 = 10^3\,(1000)\)
- \(\langle 1,5,10,10,1 \rangle \to 1\,6\,2\,1\,5\,1_9 = 10^5\,(100000)\)
- 특히 (이전 속성을 참조하십시오), x = 1에 대해 자리 값은 상수(constant) (1자리=1)로 유지됩니다. 따라서 엔트리는 행의 값을 해석하는 것에서 단순히 더해질 수 있습니다.
- 파스칼의 삼각형에서 숫자의 일부는 로자니치의 삼각형(Lozanić's triangle)에서 숫자와 상호 관련이 있습니다.
- 행 n의 원소의 제곱의 합은 행 2n의 중간 원소와 같습니다. 예를 들어, \(1^2+4^2+6^2+4^2+1^2=70\). 일반적인 형식에서:
- \(\displaystyle \sum_{k=0}^n {n \choose k}^2 = {2n \choose n}.\)
- 임의의 행 n에서, 여기서 n이 짝수이면, 중간 항에서 왼쪽으로 두 번째 지점에 있는 항을 뺀 것은 카탈랑 숫자, 구체적으로 (n/2 + 1)번째 카탈랑 숫자(Catalan number)와 같습니다. 예를 들어: 행 4에서, 6 − 1 = 5이며, 이것은 세 번째 카탈랑 숫자, 및 4/2 + 1 = 3입니다.
- 행 p에서, 여기서 p가 소수(prime number)이면, 1을 제외한 해당 행에서 모든 항은 p의 배수(multiples)입니다. 이것은 쉽게 증명될 수 있는데, 왜냐하면 만약 \(\displaystyle p\in \mathbb{P}\)이면, p는 1과 그 자체를 제외하고 아무런 인수도 가지지 않기 때문입니다. 삼각형에서 모든 각 엔트리는 정수이므로, 따라서 정의 \(\displaystyle (p-k)!\) 및 \(\displaystyle k!\)에 의해 \(\displaystyle p!\)의 인수입니다. 어쨌든, p 자체가 분모에서 나타날 수 있는 방법이 없으므로, 따라서 p (또는 그것의 어떤 배수)는 반드시 분자에서 남겨지며, 전체 엔트리를 p의 배수로 만듭니다.
- 패리티 : 행 n에서 홀수(odd) 항들을 세기 위해, n을 이진수(binary)로 변환합니다. x를 이진 표현에서 1들의 숫자로 놓습니다. 그런-다음 홀수 항의 숫자는 \(2^x\)일 것입니다. 이들 숫자는 굴드의 수열(Gould's sequence)에 있는 값입니다.
- n ≥ 0, 행 \(2^n-1\)에서, 모든 각 엔트리는 홀수입니다.
- 극성(Polarity): 파스칼의 삼각형의 행의 원소가, 중간 숫자를 갖는 모든 각 행, 즉 정수의 홀수 개를 가지는 행에서, 중간 숫자로부터 연속적으로 함께 빼고 더한 것은 결과로 0을 제공합니다. 예를 들어, 행 4는 1 4 6 4 1이므로, 수식은 6 – (4+4) + (1+1) = 0이 되고; 행 6은 1 6 15 20 15 6 1이므로, 수식은 20 – (15+15) + (6+6) – (1+1) = 0이 될 것입니다. 그래서 파스칼 삼각형의 모든 각 짝수 행은, 여러분이 중간 숫자를 취하고, 그런-다음 중앙의 바로 옆에 있는 두 정수를 뺀 다음, 다음 두 정수를 더한 다음, 빼기 등을 수행하여 행의 끝에 도달할 때까지 반복했을 때, 0과 같아집니다.
Diagonals
파스칼의 삼각형의 대각선은 심플렉스의 그림 숫자(figurate numbers)를 포함합니다:
- 왼쪽 및 오른쪽 가장자리를 따라 진행하는 대각선은 오직 1을 포함합니다.
- 가장자리 대각선 다음의 대각선은 순서대로 자연수(natural number)를 포함합니다.
- 안쪽으로 이동할 때, 대각선의 다음 쌍은 순서대로 삼각형 숫자를 포함합니다.
- 대각선의 다음 쌍은 순서대로 사면체 숫자(tetrahedral number)를 포함하고, 다음 쌍은 펜타토프 숫자(pentatope number)를 제공합니다.
- \(\displaystyle \begin{align}
P_0(n) &= P_d(0) = 1, \\
P_d(n) &= P_d(n-1) + P_{d-1}(n) \\
&= \sum_{i=0}^n P_{d-1}(i) = \sum_{i=0}^d P_i(n-1).
\end{align}\)
- \(\displaystyle \begin{align}
삼각형의 대칭성은 \(n^{\rm 번째}\) d-차원 숫자가 \(d^{\rm 번째}\) n-차원 숫자와 같음을 의미합니다.
재귀를 포함하지 않는 대안적인 공식은 다음처럼 입니다:
\(\quad\displaystyle P_d(n)=\frac{1}{d!}\prod_{k=0}^{d-1} (n+k) = {n^{(d)}\over d!} = \binom{n+d-1}{d}\)
여기서 \(n^{(d)}\)은 올라가는 팩토리얼(rising factorial)입니다.
함수 \(P_d\)의 기하학적 의미는, 모든 d에 대해 \(P_d(1)=1\)라는 것입니다. \(P_d(1)=1\)에 해당하는, 초기 점 아래에 추가적인 점을 배치함으로써 d-차원(dimensional) 삼각형(triangle)을 구성하십시오 (3-차원 삼각형은 정사면체(tetrahedron)입니다). 파스칼 삼각형에서 숫자의 배치와 비슷한 방식에서 이들 점을 배치하십시오. \(P_d(x)\)를 찾는 것은, 목표 모양을 합성하는 전체 x 점을 가집니다. \(P_d(x)\)는 그런-다음 그 모양에서 전체 점의 숫자와 같습니다. 0-차원 삼각형은 한 점이고 1-차원 삼각형은 단순한 직선이고, 따라서 \(P_0(x)=1\) 및 \(P_1(x)=x\)이며, 이것은 자연수의 수열입니다. 각 층에서 점의 숫자는 \(P_{d-1}(x)\)에 해당합니다.
Calculating a row or diagonal by itself
다른 원소 또는 팩토리얼 계산없이 행 또는 대각선에서 모든 원소를 계산하기 위한 간단한 알고리듬이 있습니다.
원소 \(\displaystyle \tbinom{n}{0}\), \(\displaystyle \tbinom{n}{1}\), ..., \(\displaystyle \tbinom{n}{n}\)을 갖는 행 \(\displaystyle n\)을 계산하기 위해, \(\displaystyle \tbinom{n}{0}=1\)으로 시작하십시오. 각 후속 원소에 대해, 그 값은 천천히 변하는 분자 및 분모를 가진 분수에 의해 이전 값을 곱함으로써 결정됩니다:
\(\quad\displaystyle {n\choose k}= {n\choose k-1}\times \frac{n+1-k}{k}.\)
예를 들어, 행 5를 계산하기 위해, 분수는 \(\displaystyle \tfrac{5}{1}\), \(\displaystyle \tfrac{4}{2}\), \(\displaystyle \tfrac{3}{3}\), \(\displaystyle \tfrac{2}{4}\) 및 \(\displaystyle \tfrac{1}{5}\)이고, 따라서 원소는 \(\displaystyle \tbinom{5}{0}=1\), \(\displaystyle \tbinom{5}{1}=1\times\tfrac{5}{1}=5\), \(\displaystyle \tbinom{5}{2}=5\times\tfrac{4}{2}=10\), 등입니다. (남아있는 원소는 대칭에 의해 대부분 쉽게 얻습니다.)
원소 \(\displaystyle \tbinom{n}{0}\), \(\displaystyle \tbinom{n+1}{1}\), \(\displaystyle \tbinom{n+2}{2}\), ...를 포함하는 대각선을 계산하기 위해, 우리는 다시 \(\displaystyle \tbinom{n}{0}=1\)로 시작하고 특정 분수에 의해 곱셈으로 후속 원소를 얻습니다:
\(\quad\displaystyle {n+k\choose k}= {n+k-1\choose k-1}\times \frac{n+k}{k}.\)
예를 들어, \(\displaystyle \tbinom{5}{0}\)에서 시작하는 대각선을 계산하기 위해, 분수는 \(\displaystyle \tfrac{6}{1}\), \(\displaystyle \tfrac{7}{2}\), \(\displaystyle \tfrac{8}{3}\), ...이고 원소는\(\displaystyle \tbinom{5}{0}=1\), \(\displaystyle \tbinom{6}{1}=1\times\tfrac{6}{1}=6\), \(\displaystyle \tbinom{7}{2}=6\times\tfrac{7}{2}=21\), 등입니다. 대칭에 의해, 이들 원소는 \(\displaystyle \tbinom{5}{5}\), \(\displaystyle \tbinom{6}{5}\), \(\displaystyle \tbinom{7}{5}\), 등과 같습니다.
Overall patterns and properties
파스칼 삼각형에서 오직 홀수를 색칠함으로써 얻어진 패턴은 시에르핀스키 삼각형(Sierpinski triangle)으로 불리는 프랙탈(fractal)과 매우 흡사합니다. 이 닮음은 더 많은 행이 고려될 때 점점 더 정확하게 됩니다; 극한에서, 행의 숫자가 무한대에 접근할 때, 결과 패턴은 시에르핀스키 삼각형이며, 고정된 둘레를 가정합니다. 보다 일반적으로, 숫자는, 그들이 3, 4 등의 배수인지 여부에 따라 다르게 색칠될 수 있습니다; 이것은 다른 유사한 패턴을 낳습니다.
(아래 그림에서 처럼) 그리드의 삼각형 부분에서, 삼각형의 주어진 노드로부터 맨 위 노드까지 가장-짧은 그리드 경로의 숫자는 파스칼의 삼각형에서 해당하는 엔트리입니다. 삼각형과 같은 모양의 플링코(Plinko) 게임 보드에서, 이 분배는 다양한 상을 받을 확률을 제공해야 합니다.
만약 파스칼의 삼각형의 행이 왼쪽-정렬이면, (아래에서 색상으로-구분된) 대각선 밴드는 피보나치 숫자(Fibonacci number)를 합합니다.
Construction as matrix exponential
\(\displaystyle \begin{align}
\exp\begin{pmatrix}
. & . & . & . & . \\
1 & . & . & . & . \\
. & 2 & . & . & . \\
. & . & 3 & . & . \\
. & . & . & 4 & .
\end{pmatrix} &=
\begin{pmatrix}
1 & . & . & . & . \\
1 & 1 & . & . & . \\
1 & 2 & 1 & . & . \\
1 & 3 & 3 & 1 & . \\
1 & 4 & 6 & 4 & 1
\end{pmatrix}\\
e^{counting} &= binomial
\end{align}
\)
팩토리얼에 의한 간단한 구성으로 기인해서, 행렬 지수(matrix exponential)의 관점에서 파스칼의 삼각형의 매우 기본적인 표현은 제공될 수 있습니다: 파스칼의 삼각형은 그의 부-대각선에 수열 1, 2, 3, 4, …를 가지고 다른 곳에 영을 가지는 행렬의 지수입니다.
Connections to geometry of polytopes
파스칼의 삼각형은 (삼각형, 사면체, 정사각형, 및 정육면체와 같은) 폴리토프(polytope) 내의 (가장자리와 꼭짓점과 같은) 원소의 숫자에 대해 조회 테이블(lookup table)로 사용될 수 있습니다.
Number of elements of simplices
1, 3, 3, 1 값을 가진 파스칼의 삼각형의 세 번째 직선을 고려함으로써 시작해 봅시다. 이-차원 삼각형은 1 이-차원 원소 (자체), 3 일-차원 원소 (직선 또는 가장자리), 및 3 영-차원 원소 (꼭짓점(vertices) 또는 구석)을 가집니다. 마지막 숫자 (1)의 의미는 설명하기가 더 어렵습니다 (그러나 아래를 참조하십시오). 이 예제와 함께 계속해서, 사면체(tetrahedron)는 1 삼-차원 원소 (자체), 4 이-차원 원소 (면), 6 일-차원 원소 (가장자리) 및 4 영-차원 원소 (꼭짓점)를 가집니다. 마지막 1을 다시 더하면, 이들 값은 삼각형의 4번째 행 (1, 4, 6, 4, 1)에 해당합니다. 직선 1은 한 점에 해당하고, 직선 2는 선분 (둘(dyad))에 해당합니다. 이 패턴은 임의적으로 고차원 초-사면체 (심플렉스(simplices)로 알려짐)를 계속합니다.
이 패턴이 존재하는 이유를 이해하기 위해, 우리는 먼저 (n − 1)-심플렉스로부터 n-심플렉스를 구축하는 과정은 단순히 새로운 꼭짓점을 후자에 더하는 것으로 구성되며, 이 새로운 꼭짓점이 원래 심플렉스의 공간 밖에 놓이게 위치시키고, 그것을 모든 원본 꼭짓점에 연결합니다. 예제로써, 삼각형에서 사면체를 만드는 경우를 생각해 보십시오. 그것의 후자의 원소는 파스칼의 삼각형의 행 3에 열거된 원소입니다: 1 면, 3 가장자리, 및 3 꼭짓점 (마지막 1의 의미는 곧 설명될 것입니다). 삼각형으로부터 사면체를 만들기 위해, 우리는 삼각형의 평면 위에 새로운 꼭짓점을 위치시키고 이 꼭짓점을 원래 삼각형의 세 꼭짓점에 모두 연결합니다.
사면체에서 주어진 차원 원소의 숫자는 이제 두 숫자의 합입니다: 먼저 원래 삼각형에서 찾은 해당 원소의 숫자, 더하기 새로운 원소의 숫자, 그것의 각각은 원래 삼각형에서 하나 더 작은 차원의 원소 위에 만들어집니다. 따라서, 사면체에서, 셀(cells) (다면체 원소)의 숫자는 0 + 1 = 1입니다; 면의 숫자는 1 + 3 = 4입니다; 가장자리의 숫자는 3 + 3 = 6입니다; 새로운 꼭짓점의 숫자는 3 + 1 = 4입니다. 주어진 차원의 원소의 숫자를 하나의 더 작은 차원의 원소와 합하여 다음 상위 심플렉스에서 발견된 전자의 숫자에 도달하는 이 과정은 파스칼의 삼각형의 행에서 두 개의 인접한 숫자를 합해서 아래 숫자가 산출하는 것과 동등합니다. 따라서, 파스칼 삼각형의 행에서 마지막 숫자 (1)의 의미는 다음 행에 의해 표현된 다음 상위 심플렉스를 산출하기 위해 그 행에 의해 표현된 심플렉스에 더해질 다음 새로운 꼭짓점 나타내는 것으로 이해됩니다. 이 새로운 꼭짓점은 새로운 심플렉스에서 하나 상위 차원의 새로운 원소를 산출하기 위해 원래 심플렉스에서 모든 각 원소에 결합되고, 이것은 파스칼의 삼각형에서 보이는 것과 동일한 것으로 발견되는 패턴의 원점입니다. 행에서 "추가" 1은 -1 심플렉스, 심플렉스의 고유한 중심으로 생각될 수 있으며, 이것은 항상 새로운 꼭짓점과 새로운 차원을 야기하여, 새로운 중심을 갖는 새로운 심플렉스를 생성합니다.
Number of elements of hypercubes
비슷한 패턴은, 삼각형과 반대로, 정사각형(squares)에 관련하여 관찰됩니다. 패턴을 찾기 위해, 우리는 파스칼의 삼각형과 아날로그로 구성해야 하며, 그의 엔트리는 \((x+1)^{\rm 행 번호}\) 대신에 \((x+2)^{\rm 행 번호}\)의 계수입니다. 이것을 수행하는 두 방법이 있습니다. 더 단순한 것은 행 0 = 1 및 행 1 = 1, 2로 시작하는 것입니다. 다음 규칙에 따라 아날로그 삼각형을 구성하기 위해 진행하십시오:
\(\quad\displaystyle {n \choose k} = 2\times{n-1 \choose k-1} + {n-1 \choose k}.\)
즉, 파스칼의 삼각형의 규칙에 따라 한 쌍의 숫자를 선택하지만, 더하기 전에 왼쪽에 있는 숫자를 두 배하십시오. 이것은 다음의 결과를 초래합니다:
\(\quad\displaystyle \begin{matrix}
\text{ 1} \\
\text{ 1} \quad \text{ 2} \\
\text{ 1} \quad \text{ 4} \quad \text{ 4} \\
\text{ 1} \quad\text{ 6} \quad \text{ 12} \quad\text{ 8} \\
\text{ 1} \quad\text{ 8} \quad \text{ 24} \quad \text{ 32} \quad \text{ 16} \\
\text{ 1} \quad \text{ 10} \quad \text{ 40} \quad \text{ 80} \quad \text{ 80} \quad \text{ 32} \\
\text{ 1} \quad \text{ 12} \quad \text{ 60} \quad 160 \quad 240 \quad 192 \quad \text{ 64} \\
\text{ 1} \quad \text{ 14} \quad \text{ 84} \quad 280 \quad 560 \quad 672 \quad 448 \quad 128
\end{matrix}\)
이 삼각형을 제작하는 다른 방법은 파스칼의 삼각형으로 시작하고 각 엔트리에 \(2^k\)를 곱하는 것이며, 여기서 k는 주어진 숫자 행에서 위치입니다. 예를 들어, 파스칼의 삼각형의 행 4에서 2번째 값은 6입니다 (1들의 기울기는 각 행에서 영 번째 엔트리에 해당합니다). 아날로그 삼각형에서 해당 위치에 있는 값을 얻기 위해, 6에 곱하십시오: \(2^{\rm 행 번호} = 6 \times 2^2 = 6 \times 4 =24\). 이제 아날로그 삼각형이 구성되었으며, 임의적인 차원 큐브(cube) (초-입방체(hypercube)로 불림)를 구성하는 임의의 차원의 원소의 숫자는 파스칼의 삼가혀에 대한 아날로그 방법에서 테이블로부터 읽힐 수 있습니다. 예를 들어, 이-차원 큐브 (정사각형)의 2-차원 원소의 숫자는 1이고 1-차원 원소 (변 또는 직선)의 숫자는 4이고, 0-차원 원소 (점, 또는 꼭짓점)의 숫자는 4입니다. 이것은 테이블의 두 번째 행 (1, 4, 4)과 일치합니다. 큐브는 1 큐브, 6 면, 12 가장자리, 및 8 꼭짓점을 가지며, 이것은 아날로그 삼각형의 다음 줄 (1, 6, 12, 8)에 해당합니다. 이 패턴은 무한정 계속됩니다.
이 패턴이 존재하는 이유를 이해하기 위해, 먼저 (n − 1)-큐브에서 n-큐브의 구성은 원래 도형을 복제하고 원래 도형의 공간에 직교(orthogonal)하는 어떤 거리 (정규 n-큐브에 대해, 가장자리 거리)에 그것을 바꾸어 놓고, 그런-다음 새 도형의 각 꼭짓점을 원래의 해당하는 꼭짓점에 연결합니다. 이 초기 복제 과정은 n-큐브의 차원 원소를 열거하기 위해, 아래의 숫자를 산출하기 위해 합산하기 전에 파스칼의 삼각형의 이 아날로그의 행에서 한 쌍의 숫자 중 첫 번째 숫자를 두 배로 늘려야 하는 이유입니다. 초기에 두-배하는 것은 따라서 다음 더 높은 n-큐브에서 발견될 "원래" 원소의 숫자를 산출하고, 이전과 같이, 새로운 원소는 하나 낮은 차원의 원소 (꼭짓점의 가장자리, 가장자리의 면, 등)를 기반으로 합니다. 다시 말하지만, 행의 마지막 숫자는 다음으로 높은 n-큐브를 생성하기 위해 더해질 새로운 꼭짓점의 숫자를 나타냅니다.
이 삼각형에서, 행 m의 원소의 합은 \(3^m\)과 같습니다. 다시, 예제로서 행 4의 원소를 사용하기 위해: {{math|1=1 + 8 + 24 + 32 + 16 = 81}}, 이것은 \(\displaystyle 3^4 = 81\)과 같습니다.
Counting vertices in a cube by distance
파스칼의 삼각형의 각 행은 n-차원 큐브에서 고정된 꼭짓점으로부터 각 거리에서 꼭짓점의 숫자를 제공합니다. 예를 들어, 삼-차원에서, 세 번째 행 (1 3 3 1)은 보통의 삼-차원 큐브(cube)에 해당합니다: 꼭짓점 V를 고정하면, V로부터 거리 0에서 하나의 꼭짓점 (즉, V 자체), 거리 1에서 세 꼭짓점, 거리 \(\sqrt{2}\)에서 세 꼭짓점 및 거리 \(\sqrt{3}\)에서 한 꼭짓점 (V 반대편의 꼭짓점)이 있습니다. 두 번째 행은 정사각형에 해당하지만, 더 큰-숫자의 행은 각 차원에서 초-입방체(hypercube)에 해당합니다.
Fourier transform of \(\sin(x)^{n+1}/x\)
앞에서 말했듯이, \((x+1)^n\)의 계수는 삼각형의 n번째 행입니다. 이제 \((x-1)^n\)의 계수는 부호가 +1에서 −1로 교대하고 다시 되돌아오는 것을 제외하고는 같습니다. 적절한 정규화 후에, 숫자의 같은 패턴은 \(\sin(x)^{n+1}/x\)의 푸리에 변환(Fourier transform)에서 발생합니다. 보다 정확하게: 만약 n이 짝수이면, 변환의 실수 부분(real part)을 취하고, 만약 n이 홀수이면, 허수 부분(imaginary part)을 취하십시오. 그런-다음 결과는 계단 함수(step function)이며, (적절하게 정규화된) 그의 값은 교대하는 부호를 갖는 삼각형의 n번째 행에 의해 제공됩니다. 예를 들어, 다음으로부터 결과로써 생기는 계단 함수의 값은:
\(\quad\displaystyle \,\mathfrak{Re}\left(\text{Fourier} \left[ \frac{\sin(x)^5}{x} \right]\right)\)
교대하는 부호와 함께, 삼각형의 4번째 행을 구성합니다. 이것은 다음 기본 결과의 일반화입니다 (종종 전기 공학(electrical engineering)에서 사용됩니다):
\(\quad\displaystyle \,\mathfrak{Re}\left(\text{Fourier} \left[ \frac{\sin(x)^1}{x}\right] \right)\)
이것은 박스카 함수(boxcar function)입니다. 삼각형의 해당하는 행은 0이며, 이것은 단지 숫자 1로 구성됩니다.
만약 n이 2 또는 3 모드 4와 일치(congruent)하면, 부호는 −1로 시작합니다. 실제로, (정규화된) 첫 번째 항의 수열은 i의 거듭-제곱에 해당하며, 이것은 복소 평면에서 단위 원과 축의 교차를 중심으로 순환합니다:
\(\qquad\displaystyle \, +i,-1,-i,+1,+i,\ldots \, \)
Elementary cellular automaton
규칙 60을 사용하여 기본 셀룰러 오토마톤(elementary cellular automaton)에 의해 생성된 패턴은 모듈로 2로 감소된 이항 계수의 정확히 파스칼의 삼각형입니다 (검은 셀은 홀수 이항 계수에 해당합니다). 규칙 102는 후행 영이 생략될 때 이 패턴을 역시 생성합니다. 규칙 90(Rule 90)은 같은 패턴을 생성하지만 행에서 각 엔트리를 분리하는 빈 셀을 가집니다.
Extensions
파스칼의 삼각형은 음의 행 숫자로 확장될 수 있습니다.
먼저 다음 형식에서 삼각형을 쓰십시오:
다음으로, 1의 열을 위쪽으로 확장하십시오:
이제 그 규칙:
\(\quad\displaystyle {n \choose m} = {n-1 \choose m-1} + {n-1 \choose m}\)
은 다음으로 다시-정렬될 수 있습니다:
\(\quad\displaystyle {n-1 \choose m} = {n \choose m} - {n-1 \choose m-1}\)
이것은 음의 행에 대해 다른 엔트리의 계산을 허용합니다:
이 확장은 n의 함수로 보이는 m번째 열에서 값이 차수 m 다항식에 적합하다는 속성을 보존합니다, 즉
\(\quad\displaystyle
{n \choose m} = \frac{1}{m!}\prod_{k=0}^{m-1} (n-k) = \frac{1}{m!}\prod_{k=1}^{m} (n-k+1)
\).
이 확장은 역시 n번째 행에서 값이 \((1+x)^n\)의 계수에 해당하는 속성을 보존합니다:
\(\quad\displaystyle
(1+x)^n = \sum_{k=0}^\infty {n \choose k} x^k \quad |x| < 1
\)
예를 들어:
\(\quad\displaystyle
(1+x)^{-2} = 1-2x+3x^2-4x^3+\cdots \quad |x| < 1
\)
급수로 보일 때, 음의 n의 행은 발산합니다. 어쨌든, 그들은 여전히 아벨 합-가능(Abel summable)이며, 이 합은 \(2^n\)의 표준 값을 제공합니다. (사실, n = -1 행은 그란디의 급수(Grandi's series)를 초래하며 이것은 "합해져서" 1/2이 되고, n = -2 행은 또 다른 잘-알려진 급수를 초래하며 이것은 1/4의 아벨 합을 가집니다.)
파스칼의 삼각형을 음의 행으로 확장하는 것에 대해 또 다른 선택-사항은 1의 다른 줄을 확장하는 것으로부터 옵니다:
이전처럼 같은 규칙을 적용하면 다음으로 이어집니다:
이 확장은 단지 다음인 것처럼 속성을 역시 가집니다:
\(\quad\displaystyle
\exp\begin{pmatrix}
. & . & . & . & . \\
1 & . & . & . & . \\
. & 2 & . & . & . \\
. & . & 3 & . & . \\
. & . & . & 4 & .
\end{pmatrix} =
\begin{pmatrix}
1 & . & . & . & . \\
1 & 1 & . & . & . \\
1 & 2 & 1 & . & . \\
1 & 3 & 3 & 1 & . \\
1 & 4 & 6 & 4 & 1
\end{pmatrix}, \)
우리는 다음을 가집니다:
\(\quad\displaystyle
\exp\begin{pmatrix}
. & . & . & . & . & . & . & . & . & . \\
-4 & . & . & . & . & . & . & . & . & . \\
. & -3 & . & . & . & . & . & . & . & . \\
. & . & -2 & . & . & . & . & . & . & . \\
. & . & . & -1 & . & . & . & . & . & . \\
. & . & . & . & 0 & . & . & . & . & . \\
. & . & . & . & . & 1 & . & . & . & . \\
. & . & . & . & . & . & 2 & . & . & . \\
. & . & . & . & . & . & . & 3 & . & . \\
. & . & . & . & . & . & . & . & 4 & .
\end{pmatrix} =
\begin{pmatrix}
1 & . & . & . & . & . & . & . & . & . \\
-4 & 1 & . & . & . & . & . & . & . & . \\
6 & -3 & 1 & . & . & . & . & . & . & . \\
-4 & 3 & -2 & 1 & . & . & . & . & . & . \\
1 & -1 & 1 & -1 & 1 & . & . & . & . & . \\
. & . & . & . & . & 1 & . & . & . & . \\
. & . & . & . & . & 1 & 1 & . & . & . \\
. & . & . & . & . & 1 & 2 & 1 & . & . \\
. & . & . & . & . & 1 & 3 & 3 & 1 & . \\
. & . & . & . & . & 1 & 4 & 6 & 4 & 1
\end{pmatrix} \)
역시, 단지 파스칼 행렬의 아래-왼쪽에서 위-오른쪽 대각선을 따라 합산하면 피보나치 숫자(Fibonacci numbers)를 산출하지만, 이 두 번째 유형의 확장은 여전히 합해져서 음수 인덱스의 피보나치 숫자가 됩니다.
이들 확장 중 하나는 만약 우리가 다음을 정의하고 감마 함수(gamma function), \(\displaystyle \Gamma(z)\)의 특정 극한을 취하면 도달될 수 있습니다:
\(\quad\displaystyle {n \choose k} = \frac{n!}{(n-k)! k!} \equiv \frac{\Gamma(n+1)}{\Gamma(n-k+1)\Gamma(k+1)}\).
See also
External links
- "Pascal triangle", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- Weisstein, Eric W. "Pascal's triangle". MathWorld.
- The Old Method Chart of the Seven Multiplying Squares (from the Ssu Yuan Yü Chien of Chu Shi-Chieh, 1303, depicting the first nine rows of Pascal's triangle)
- Pascal's Treatise on the Arithmetic Triangle (page images of Pascal's treatise, 1654; summary)
