위에서부터 1, 그 아래 1 1, 다음 줄 1 2 1을 쓰고 양 끝에는 1을, 가운데에는 바로 위 두 수의 합을 적으면 숫자 삼각형이 만들어집니다. 파스칼의 삼각형입니다. 단순한 덧셈표처럼 보이지만 각 수는 조합의 개수이고, 한 행은 이항식의 전개 계수입니다. 비스듬한 줄을 더하면 피보나치 수열이 나오며 홀수와 짝수만 색칠하면 자기 닮은 삼각형 무늬가 나타납니다.
이 구조는 블레즈 파스칼보다 오래전부터 여러 문화권에서 연구됐습니다. 파스칼은 17세기에 산술삼각형을 체계적으로 다루고 확률과 조합 문제에 활용했습니다. 오늘날 그의 이름으로 널리 불리지만 ‘파스칼이 처음 숫자를 발견했다’고 설명하는 것은 역사적으로 정확하지 않습니다. 핵심 수학은 이항계수 C(n,k) 또는 (n choose k)의 배열입니다.
행과 열의 번호를 먼저 정하기
맨 위 행을 n=0으로 정하면 그 행의 유일한 값은 C(0,0)=1입니다. 다음 행 n=1은 C(1,0), C(1,1)이므로 1 1이고, n=2는 1 2 1입니다. n번째 행의 k번째 값은 C(n,k)=n!/[k!(n−k)!]이며 0≤k≤n입니다. 설명마다 맨 위를 1번째 행이라고 부르기도 하므로 행 번호를 밝히지 않으면 한 줄씩 어긋날 수 있습니다.
| n | 파스칼 삼각형의 n번째 행 | 행의 합 |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 1 | 2 |
| 2 | 1 2 1 | 4 |
| 3 | 1 3 3 1 | 8 |
| 4 | 1 4 6 4 1 | 16 |
| 5 | 1 5 10 10 5 1 | 32 |
파스칼 항등식의 정확한 형태
삼각형의 가운데 수가 위의 두 수를 더한 값이라는 규칙은 C(n,k)=C(n−1,k−1)+C(n−1,k)로 씁니다. 1≤k≤n−1에서 적용하고 양 끝은 C(n,0)=C(n,n)=1입니다. 요청문처럼 위아래 인덱스가 뒤섞인 식은 어떤 값이 행이고 어떤 값이 선택 개수인지 알기 어렵습니다. 보통 n을 전체 원소 수, k를 선택할 원소 수로 통일합니다.
C(n,k)=C(n−1,k−1)+C(n−1,k)
조합으로 증명해 보겠습니다. n명 중 k명을 뽑되 특정한 사람 A가 있다고 합시다. A를 뽑는 경우에는 남은 n−1명 중 k−1명을 고르므로 C(n−1,k−1)가지입니다. A를 뽑지 않는 경우에는 n−1명 중 k명을 고르므로 C(n−1,k)가지입니다. 두 경우는 겹치지 않고 모든 선택을 포함하므로 합이 C(n,k)가 됩니다.
팩토리얼로도 확인할 수 있습니다. C(n−1,k−1)+C(n−1,k)를 공통분모 k!(n−k)!로 맞추면 분자가 k(n−1)!+(n−k)(n−1)!=n!이 되어 C(n,k)가 됩니다. 덧셈 규칙은 단순한 표 작성 요령이 아니라 같은 조합 집합을 두 경우로 나눈 결과입니다.
이항정리와 한 행의 의미
이항정리는 (x+y)^n=Σ(k=0부터 n까지) C(n,k)x^(n−k)y^k라고 말합니다. 예를 들어 n=4인 행 1,4,6,4,1을 사용하면 (x+y)^4=x^4+4x^3y+6x²y²+4xy³+y^4입니다. x 네 개 또는 y 네 개 중 어느 항을 선택해 곱할지를 세면 y를 정확히 k번 고르는 방법이 C(n,k)가지이므로 이 계수가 나옵니다.
x=1, y=1을 대입하면 (1+1)^n=ΣC(n,k)=2^n입니다. 따라서 n번째 행의 합은 2^n입니다. 이는 n개의 원소로 만들 수 있는 모든 부분집합이 2^n개라는 사실과 같습니다. 각 원소마다 포함 또는 제외 두 선택이 있고, 크기가 k인 부분집합을 분류해 세면 C(n,k)를 모두 더한 값이 됩니다.
x=1, y=−1을 넣으면 (1−1)^n=Σ(−1)^kC(n,k)=0입니다. n≥1인 행에서는 짝수 번째 위치 계수의 합과 홀수 번째 위치 계수의 합이 각각 2^(n−1)로 같습니다. 위치의 홀짝과 계수 값 자체의 홀짝은 다른 개념이므로 뒤의 프랙탈 무늬와 섞어서는 안 됩니다.
대칭성과 하키 스틱 항등식
C(n,k)=C(n,n−k)이므로 각 행은 좌우 대칭입니다. n개 중 k개를 고르는 일은 고르지 않을 n−k개를 정하는 일과 일대일로 대응하기 때문입니다. 팩토리얼 식에서도 분모 k!(n−k)!가 자리를 바꿔도 같습니다.
한 대각선을 따라 C(r,r), C(r+1,r), …, C(n,r)을 더하면 C(n+1,r+1)이 됩니다. 삼각형에서 더하는 항들이 막대처럼 이어지고 결과가 옆 위에 붙어 하키 스틱 모양으로 보이기 때문에 하키 스틱 항등식이라고 부릅니다. 파스칼 항등식을 반복 적용하거나, n+1개 중 r+1개를 뽑을 때 가장 큰 번호로 경우를 나눠 증명할 수 있습니다.
얕은 대각선의 합에서 피보나치 수가 나옵니다
파스칼 삼각형의 수직선이나 바로 옆 대각선이 아니라, 한 칸 아래로 갈 때마다 두 칸 안쪽으로 움직이는 ‘얕은 대각선’을 더하면 피보나치 수가 됩니다. 인덱스로 쓰면 F_(n+1)=Σ(k=0부터 ⌊n/2⌋까지) C(n−k,k)입니다. F_1=1, F_2=1을 쓰는 규약에서 n=0이면 1, n=1이면 1, n=2이면 C(2,0)+C(1,1)=1+1=2가 됩니다.
| n | 얕은 대각선 합 | 결과 |
|---|---|---|
| 0 | C(0,0) | 1=F₁ |
| 1 | C(1,0) | 1=F₂ |
| 2 | C(2,0)+C(1,1) | 2=F₃ |
| 3 | C(3,0)+C(2,1) | 3=F₄ |
| 4 | C(4,0)+C(3,1)+C(2,2) | 5=F₅ |
| 5 | C(5,0)+C(4,1)+C(3,2) | 8=F₆ |
이 항등식은 길이 n인 줄을 길이 1인 칸과 길이 2인 칸으로 채우는 방법을 세어 설명할 수 있습니다. 길이 2짜리 조각을 k개 쓰면 길이 1짜리는 n−2k개이고 전체 조각 수는 n−k개입니다. 그중 k자리에 길이 2짜리를 배치하는 방법은 C(n−k,k)가지입니다. 가능한 k를 모두 더하면 타일링 방법 수가 되고, 이 수는 마지막 조각이 길이 1인지 2인지에 따라 앞의 두 수를 더하는 피보나치 점화식을 만족합니다.
따라서 대각선의 방향을 막연히 ‘비스듬히 더한다’고 말하기보다 합 공식과 시작점을 함께 적어야 합니다. 반대 방향의 평범한 대각선에는 자연수나 삼각수가 놓이기도 합니다. 피보나치 수열과 황금비 수렴에서는 F_(n+1)/F_n이 φ로 가까워지는 별도의 성질을 확인할 수 있습니다.
홀수만 색칠하면 나타나는 시에르핀스키 무늬
각 이항계수가 홀수면 검게, 짝수면 희게 칠해 보겠습니다. 처음 2행, 4행, 8행, 16행처럼 2의 거듭제곱 크기로 자르면 큰 검은 삼각형 안에서 가운데의 흰 역삼각형이 빠지고, 남은 세 모서리에 같은 모양이 절반 크기로 반복됩니다. 단계를 계속 늘리면 시에르핀스키 삼각형과 같은 자기 닮음 패턴이 드러납니다.
이 무늬는 숫자가 우연히 얼룩처럼 배열된 결과가 아닙니다. 덧셈을 2로 나눈 나머지만 계산하면 1+1=0, 1+0=1, 0+1=1, 0+0=0이 됩니다. 파스칼의 덧셈 규칙을 모듈로 2에서 반복한 결과가 각 단계의 세 부분 복제 구조를 만듭니다.
루카스 정리로 홀수 위치를 판정하기
소수 p에 대한 루카스 정리는 n과 k를 p진법으로 쓴 각 자리 n_i, k_i에 대해 C(n,k)≡∏C(n_i,k_i) (mod p)라고 말합니다. p=2이면 각 자리는 0 또는 1입니다. 이 곱이 홀수이려면 k의 어떤 이진 자리에도 n에는 없는 1이 나오면 안 됩니다. 즉 k의 1비트가 모두 n의 1비트 안에 포함될 때 C(n,k)는 홀수입니다.
예를 들어 n=5는 이진수 101입니다. 가능한 k 가운데 1비트가 101의 자리에만 있는 수는 000, 001, 100, 101, 즉 0,1,4,5입니다. 실제로 5번째 행 1,5,10,10,5,1에서 C(5,0), C(5,1), C(5,4), C(5,5)만 홀수입니다. 이 판정은 큰 팩토리얼을 계산하지 않고도 홀짝을 알려 줍니다.
n의 이진 표현에 1이 s개 있으면 그 행의 홀수 항 개수는 2^s입니다. 각 1비트를 k에 포함할지 말지 독립적으로 선택할 수 있기 때문입니다. n=7은 111₂이고 s=3이므로 7번째 행의 8개 항이 모두 홀수입니다. 실제 행은 1,7,21,35,35,21,7,1입니다. 반면 n=8은 1000₂이므로 양 끝 두 항만 홀수입니다.
왜 프랙탈 차원이 log 3/log 2인가
시에르핀스키 삼각형은 전체를 길이 1/2인 닮은 조각 세 개로 나눌 수 있습니다. 자기유사 차원 D는 3=2^D를 만족하므로 D=log3/log2≈1.58496입니다. 파스칼 삼각형의 홀짝 무늬를 2의 거듭제곱 행까지 확대한 뒤 크기를 맞춰 보는 극한에서 이 차원이 연결됩니다. 유한한 행 몇 줄 자체가 무한 프랙탈이라는 뜻은 아닙니다.
코흐 곡선의 하우스도르프 차원은 길이 1/3인 조각 네 개에서 D=log4/log3을 얻습니다. 파스칼 홀짝 무늬는 길이 1/2인 조각 세 개이므로 공식의 수가 다릅니다. ‘프랙탈’이라는 공통 이름만 보고 같은 차원을 대입하면 안 됩니다.
다른 소수로 나눈 나머지도 무늬를 만듭니다
계수를 2가 아니라 3, 5 같은 소수로 나눈 나머지에 따라 색을 칠해도 자기 닮은 구조가 나타납니다. 루카스 정리가 p진법의 각 자리에서 조합을 분해하기 때문입니다. p=2에서는 홀수와 짝수 두 색이라 시에르핀스키 삼각형이 가장 선명하게 보이고, 더 큰 p에서는 여러 나머지에 대응하는 복잡한 반복 무늬를 얻습니다.
확률 계산에도 같은 행이 등장합니다
성공 확률이 p인 독립 시행을 n번 할 때 정확히 k번 성공할 확률은 C(n,k)p^k(1−p)^(n−k)입니다. 어느 k번이 성공인지 고르는 방법이 C(n,k)가지이기 때문입니다. 공정한 동전을 n번 던지면 각 구체적인 앞뒤 순서는 확률 1/2^n이고, 앞면이 k번인 순서가 C(n,k)개이므로 확률은 C(n,k)/2^n입니다.
n번째 행의 합이 2^n이라는 사실은 이 확률들의 합이 1이라는 조건과도 맞습니다. 다만 파스칼 삼각형만으로 시행의 독립성이나 성공 확률이 보장되는 것은 아닙니다. 이항분포 공식을 쓰려면 시행 횟수가 고정되고, 각 시행이 독립이며, 성공 확률 p가 일정하고, 결과를 성공과 실패로 나눌 수 있어야 합니다.
큰 이항계수를 계산할 때의 주의점
n!을 먼저 계산해 C(n,k)=n!/[k!(n−k)!]에 넣으면 중간 정수가 매우 커집니다. 파스칼 점화식으로 필요한 범위를 채우거나, 대칭성 C(n,k)=C(n,n−k)을 이용해 작은 k를 선택한 뒤 곱셈과 나눗셈을 번갈아 처리할 수 있습니다. 정수형 범위를 넘는 언어에서는 임의정밀도 정수나 모듈러 계산이 필요합니다.
파스칼 삼각형의 한 행 전체를 만들 때는 이전 행만 저장하면 메모리를 O(n)으로 줄일 수 있습니다. 한 배열을 뒤쪽에서 앞으로 갱신하면 아직 사용하지 않은 이전 값이 보존됩니다. 앞에서 뒤로 갱신하면 이번 행에서 방금 바뀐 값을 다시 더하게 되어 잘못된 결과가 나옵니다. 수학적 점화식과 구현 순서가 만나는 지점입니다.
자주 틀리는 식과 해석
- 파스칼 항등식은 C(n,k)=C(n−1,k−1)+C(n−1,k)입니다. 오른쪽 두 항의 전체 원소 수는 모두 n−1입니다.
- 맨 위를 0번째 행으로 세는지 1번째 행으로 세는지 먼저 밝혀야 합니다.
- 피보나치 수는 모든 대각선의 합이 아니라 C(n−k,k)를 따르는 얕은 대각선 합에서 나옵니다.
- 홀수 무늬는 계수의 값 전체가 아니라 값을 2로 나눈 나머지를 표시한 것입니다.
- 유한한 파스칼 삼각형은 근사 패턴이고, 무한히 확대하는 구조에서 시에르핀스키 삼각형의 자기 닮음이 정확히 드러납니다.
파스칼의 삼각형 핵심 정리
파스칼 삼각형의 n번째 행 k번째 값은 C(n,k)이며, 가운데 값은 C(n−1,k−1)+C(n−1,k)입니다. 이 식은 특정 원소를 선택하는 경우와 선택하지 않는 경우로 나눠 증명할 수 있습니다. 한 행은 (x+y)^n의 계수이고, 행의 합은 2^n이며 좌우가 대칭입니다.
얕은 대각선 합 ΣC(n−k,k)는 피보나치 수 F_(n+1)이 됩니다. 각 계수를 2로 나눈 나머지로 색칠하면 루카스 정리에 따라 이진 자릿수 구조가 드러나고, 2의 거듭제곱 규모마다 시에르핀스키 삼각형 패턴이 반복됩니다. 단순한 덧셈 규칙 하나가 조합, 확률, 수열, 모듈러 연산과 프랙탈을 이어 주는 셈입니다.