정수론(Number theory)

파스칼의 삼각형(Pascal's triangle)

위의 두 수를 더해 아래 수를 만드는 삼각형. n번째 줄의 수는 n개 중 k개를 고르는 방법의 수 C(n, k)이다.

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}, \qquad (1+x)^n = \sum_k \binom{n}{k} x^k

양 끝은 1이고, 그 밖의 칸은 바로 위 두 칸의 합입니다. 윗줄의 답을 적어 두고 그것으로 다음 줄을 만드니, 계승( $n! = 1 \cdot 2 \cdots n$ )을 한 번도 계산하지 않는 동적 계획법⁠(dynamic programming)⁠입니다. 맨 윗줄을 0번째 줄, 각 줄의 맨 왼쪽을 0번째 칸으로 세면, $n$ 번째 줄 $k$ 번째 수 $\binom nk$ 는 $n$ 개 중 $k$ 개를 고르는 방법의 수입니다. 맨 위에서 아래로 내려가며 매번 왼쪽 또는 오른쪽을 고르는 길의 개수이기도 합니다( $n$ 걸음 중 오른쪽 $k$ 걸음을 고르는 셈). 갈림길마다 동전을 던져 방향을 정하면 이 길이 무작위 행보⁠(random walk)⁠가 되고, 도착한 칸의 분포가 이항분포⁠(binomial distribution)⁠ $\binom nk / 2^n$ 입니다. 크기 $k$ 인 부분집합⁠(subset)⁠의 개수이므로 한 줄을 모두 더하면 멱집합⁠(power set)⁠의 크기 $2^n$ 입니다.

이제 각 수를 $m =$ 으로 나눈 나머지⁠(remainder)⁠로 칠해 봅시다(모듈러 연산⁠(modular arithmetic)⁠). 줄 수는 입니다.

어두운

옅은 칸은 m으로 나누어떨어지는 수, 밝은짙은 칸은 나머지마다 다른 색입니다. 줄 수가 적으면 숫자가 보입니다.

$m = 2$ 로 두고 줄 수를 늘려 보세요. 홀수만 칠하면 시에르핀스키 삼각형⁠(Sierpiński triangle)⁠이 나타납니다(1915년 폴란드 수학자 바츠와프 시에르핀스키가 소개했습니다). 줄 수를 32로 두면 위쪽 16줄짜리 삼각형과 똑같은 삼각형 셋이 들어 있고, 가운데가 비어 있습니다. 일부를 확대하면 전체와 같은 모양이 다시 나오는 도형을 자기닮음⁠(self-similarity)⁠ 도형이라 하는데, 가운데를 계속 도려내 만드는 칸토어 집합⁠(Cantor set)⁠과 같은 종류입니다. 이 모양이 생기는 까닭은 2로 나눈 나머지만 보아도 "위 두 칸의 합" 규칙이 그대로 성립하기 때문입니다. 정확한 규칙도 있습니다. $\binom nk$ 가 홀수일 필요충분조건은 $k$ 를 2진법⁠(positional notation)⁠으로 썼을 때 1인 자리가 모두 $n$ 에서도 1인 것입니다(뤼카의 정리).

$m$ 이 소수⁠(prime number)⁠ $p$ 이면 $p$ 번째 줄은 양 끝을 빼고 모두 어둡습니다. $0 \lt k \lt p$ 일 때 $\binom pk = \frac{p!}{k!\,(p-k)!}$ 의 분자에는 $p$ 가 있지만, 분모의 인수는 모두 $p$ 보다 작아 이 $p$ 를 지우지 못하니까요(소수). 그래서 $(a+b)^p$ 를 전개하면 양 끝 항만 남고, $(a+b)^p \equiv a^p + b^p \pmod p$ 입니다( $\equiv \pmod p$ 는 양쪽을 $p$ 로 나눈 나머지가 같다는 뜻). 자연수⁠(natural number)⁠ $a = 1 + 1 + \cdots + 1$ 에 이 식을 거듭 쓰면 $a^p \equiv a$ 가 나옵니다. $a$ 가 $p$ 의 배수⁠(multiple)⁠가 아니면 양변을 $a$ 로 나눌 수 있어 $a^{p-1} \equiv 1$ 이 되는데, 이것이 페르마 소정리⁠(Fermat's little theorem)⁠입니다. 비스듬한 얕은 대각선을 따라 더하면 피보나치 수가 나옵니다.

이 삼각형의 수를 이항계수⁠(binomial coefficient)⁠라고도 부릅니다. 고른 $k$ 개를 늘어놓는 순서까지 따지면 $k!$ 배가 되어 순열⁠(permutation)⁠의 수 $n!/(n-k)!$ 입니다. 똑같은 사탕 $n$ 개를 $k$ 명에게 나눠 주는 방법의 수도, 한 개도 못 받는 사람이 있어도 된다면 이 삼각형 안의 수 $\binom{n+k-1}{k-1}$ 입니다(별과 막대⁠, stars and bars⁠).

괄호 $n$ 쌍을 올바르게 짝짓는 방법의 수 $\binom{2n}{n}/(n+1)$ (카탈랑 수⁠, Catalan number⁠)도 이 삼각형의 수로 계산됩니다. 단어 $n+1$ 개를 둘씩 묶어 나가는 방법(이진 구문 트리⁠(parse tree)⁠)의 수도 같은 카탈랑 수라서, 묶는 순서를 정해 주지 않는 문맥 자유 문법⁠(context-free grammar)⁠에서는 한 문장의 구문 트리가 이만큼 빠르게 늘어납니다.

이 개념이 나오는 큰 생각무작위성 무한을 다루는 법

이 개념이 나오는 긴 글

확률 도박판에서 온 편지 1654년, 도중에 멈춘 내기의 판돈을 어떻게 나눌까? 두 수학자가 주고받은 편지에서 확률론이 태어났다. 집합론 무한에도 크기가 있다 자연수와 짝수는 어느 쪽이 많을까? 칸토어는 무한을 세는 법을 찾았고, 무한이 하나가 아님을 보였다. 통계와 인과 담배와 폐암 상관관계는 인과관계가 아니라고들 한다. 그렇다면 담배가 폐암을 일으킨다는 것은 어떻게 알게 되었을까? 거리와 유사도 까마귀와 택시 까마귀는 곧장 날고 택시는 블록을 돌아간다. '얼마나 먼가'에는 답이 하나가 아니고, 어떤 거리를 고르느냐가 통계와 기계 학습의 답을 바꾼다. 조합론 세지 않고 세기 시의 운율을 세던 인도의 운율학자부터 오일러의 생성함수까지. 하나하나 늘어놓지 않고 경우의 수를 세는 법은 어떻게 자라났을까? 램지 이론 완전한 무질서는 없다 여섯 명이 모이면 서로 아는 세 사람이나 서로 모르는 세 사람이 반드시 있다. 충분히 크면 어디에나 질서가 숨어 있다는 이론과, 그것을 동전 던지기로 증명한 에르되시. 반환과 동적 계획법 같은 계산, 다른 덧셈 가장 짧은 길, 길의 가짓수, 가장 그럴듯한 해석, 갈 수 있는지 없는지. 따로 태어난 알고리즘들이 사실은 한 계산이고, 달라지는 것은 더하기와 곱하기 자리에 무엇을 넣느냐뿐이다. 그렇게 바꿔 넣어도 되는 까닭은 분배법칙 하나다.

이 개념 위에 세워진 것

이항분포 이항계수

이 개념을 언급하는 페이지

이항분포
… 가지이고, 각 경로의 확률은 p^k(1-p)^{n-k} 입니다. 경로의 수를 한 줄씩 적으면 바로파스칼의 삼각형입니다. 한 칸에 도달하는 길의 수는 위의 두 칸에 도달하는 길의 수의 합이니까요. 보드 전체가 파스칼 …
무작위 행보
… 앞면이 k번 나올 확률, 곧 \binom{n}{k}/2^n 입니다. 도착점까지 가는 길의 개수를 세는 것이파스칼의 삼각형입니다. 걸음 수가 많아지면 이 분포는 종 모양이 되는데, 이것이 중심극한정리가 말하는 …
멱집합
… 번호 를 이진수로 쓰면 이고, 이 부분집합은 입니다. 같은 층(크기가 같은 부분집합)에 있는 개수는 , 곧파스칼의 삼각형의 한 줄입니다. 크기 k 인 부분집합의 수가 이항계수 \binom{n}{k} 이고, 동전 n 개를 …
피보나치 수열
… 비네의 이름을 따 비네 공식이라 부르지만, 드무아브르가 한 세기 앞서 알고 있었습니다. 피보나치 수는파스칼의 삼각형의 얕은 대각선을 더해도 나옵니다. 정의를 그대로 옮긴 재귀 프로그램은 같은 값을 거듭 다시 …
이항계수
… + \binom{n-1}{k} 이고, 격자를 45° 돌려 세우면 이 수들이 그대로파스칼의 삼각형이 됩니다. 작은 칸의 답을 표에 적어 두고 더해 큰 칸의 답을 얻는 이 방식은 동적 계획법의 가장 …
연속체 가설
… 이하인 부분집합만 모으면 입니다. 왼쪽 그림은 부분집합 2^n 개를 원소 수별로 쌓은 것이고(기둥의 높이가파스칼의 삼각형의 한 줄입니다), 노란 점이 지금 모은 부분집합입니다. 같은 일을 자연수 전체 \mathbb{N} 에서 …
무작위 대조 시험
… 세어 보기는 어렵습니다. 20명만 돼도 배정의 수가 \binom{20}{10} = 184756 가지라서(파스칼의 삼각형에서 맨 위를 0번째 줄로 셀 때 20번째 줄의 가운데 수), 보통은 몬테카를로 방법으로 일부만 뽑아 …
그래프
… 곧 i의 차수와 같습니다. 꼭짓점 n개 사이에 변을 넣을 수 있는 자리는 \binom{n}{2} 개(파스칼의 삼각형)이고, 이름 붙은 n개 점 위의 그래프는 그 자리들의 부분집합마다 하나씩, 곧 멱집합의 크기인 …
맨해튼 거리
… 수를 더한 값입니다(그곳에 도착하는 마지막 한 걸음이 둘 중 하나이므로). 그래서 수들이 비스듬히 누운파스칼의 삼각형을 이룹니다. 도로망을 그래프로 보면 맨해튼 거리는 그 그래프 위의 최단 경로 길이입니다. 한 …
체비쇼프 거리
… 맨해튼 거리가 되고 같은 거리의 칸들은 마름모가 됩니다. 최단 경로의 수도 이때는 이항계수가 되어파스칼의 삼각형이 판 위에 나타납니다. 판을 칸이 꼭짓점인 그래프로 보면 두 거리 모두 최단 경로의 길이입니다. …
편집 거리
… 개뿐이라 계산량이 O(mn) 에 그칩니다(점근 표기법). 이웃 칸에서 값을 모아 오는 방식은파스칼의 삼각형을 채우는 방식, 앞의 두 값을 기억해 두고 피보나치 수를 구하는 방식과 같습니다. 편집 거리는 ⟦거리 …
처치–튜링 논제
… 논문으로 출판되었습니다. 규칙 30은 무작위처럼 보이는 무늬를 만듭니다. 규칙 90을 한 칸에서 시작하면파스칼의 삼각형의 수를 2로 나눈 나머지가 나오는데, 이것이 삼각형 가운데를 되풀이해 파낸 무늬인 시에르핀스키 …
별과 막대
… (1-x)^{-k} 이며 그 x^n 계수가 바로 이 답입니다. n과 k를 바꿔 가며 표에 적으면 수들이파스칼의 삼각형의 대각선을 따라 늘어섭니다. 거꾸로, 사탕이 아이보다 많으면 어떤 배치에서든 누군가는 둘 이상 받습니다. …
동적 계획법
… 칸의 수는 왼쪽 칸의 수와 아래 칸의 수의 합입니다(위의 식). 막힌 칸이 없으면 이 표는 비스듬히 누운파스칼의 삼각형이고, 답은 이항계수 \binom{10}{4} = 210 입니다. 칸을 누르면 막히거나 다시 열립니다. …
정수론
… 실수의 경계에는 무리수와 대수적 수와 초월수가 있습니다. 세는 문제와 만나는 곳이 분할수,파스칼의 삼각형, 생성함수이고, 1의 거듭제곱근은 나머지 계산을 원 위의 회전으로 바꿉니다. 수를 적는 방법은 …

이 페이지가 가리키는 개념

동적 계획법 무작위 행보 이항분포 멱집합 모듈러 연산 칸토어 집합 진법 소수와 에라토스테네스의 체 오일러 피 함수와 페르마 소정리 피보나치 수열 이항계수 순열 별과 막대 카탈랑 수 문맥 자유 문법