Combinatorics to the rescue.
어떤 문제는 분명 해석학(삼각함수)이나 정수론(합동식)의 영역처럼 보입니다 — 미분을 하거나 소수의 성질을 깊이 파야 풀릴 것 같죠. 그런데 결정적인 순간마다, 그저 무언가를 ‘세는’ 조합론이 슬그머니 나타나 문제를 풀어 버립니다. \(\tan\)의 계수가 순열의 수였고, 페르마의 소정리는 목걸이를 돌려서, 윌슨의 정리는 순열을 돌려서 증명되죠. 조합론 형이 구하러 오는 두 무대 — 삼각함수와 정수론 — 를 함께 봅니다.
삼각함수는 미적분·복소지수의 언어로 다루는 게 보통입니다. 배각 공식 \(\sin 5\theta\)를 \(\cos\theta\)로 펼치거나, \(\tan x\)의 테일러 급수를 구하는 일은 ‘해석학’의 영역이죠. 한편 조합론은 타일링·순열·격자경로처럼 유한한 것을 세는 일입니다. 서로 다른 교과서, 서로 다른 도구.
그런데 조합론적 삼각함수(combinatorial trigonometry)는 이렇게 묻습니다 — "삼각함수 항등식을, 미분 한 번 없이 그냥 세어서 증명할 수 있을까?" 답은 놀랍게도 ‘그렇다’이고, 그 다리가 두 개 있습니다. 하나는 교대순열과 \(\tan\cdot\sec\), 다른 하나는 체비쇼프 다항식과 타일링. 둘 다 같은 비밀을 품고 있어요 — 양쪽 세계가 똑같은 점화식을 만족한다는 것.
놀랍게도, \(\tan x\)와 \(\sec x\)의 테일러 계수가 — 순열을 세고 있었습니다.
교대순열이란 \(p_1\lt p_2\gt p_3\lt p_4\gt\cdots\)처럼 오르락내리락하는 순열입니다. 길이 \(n\)짜리 교대순열의 개수를 \(A_n\)이라 하면 \(A_0,A_1,A_2,\dots = 1,1,1,2,5,16,61,272,\dots\) (지그재그 수). 그런데
① 세기(점화식). 길이 \(n+1\) 교대순열에서 가장 큰 원소는 반드시 봉우리(국소 최대)에 앉습니다. 그 왼쪽에 \(k\)개, 오른쪽에 \(n-k\)개가 놓인다면 — 양쪽 조각도 각각 다시 교대순열이어야 하니 \(A_k\)가지, \(A_{n-k}\)가지, 그리고 어느 원소를 왼쪽에 둘지 고르는 \(\binom{n}{k}\)가지. 오르내림 두 방향을 합치면
$$ 2A_{n+1} = \sum_{k=0}^{n}\binom{n}{k} A_k\,A_{n-k}. $$② 생성함수. \(E(x)=\sum A_n x^n/n!\)로 두면, 위 점화식은 정확히 미분방정식 \(E' = \tfrac12\bigl(1+E^2\bigr)\), \(E(0)=1\)과 같아집니다(곱셈은 \(E^2\)의 합성곱이 되니까). 그런데 \(\sec x+\tan x\)가 바로 이 방정식의 해예요 —
$$ (\sec+\tan)' = \sec(\sec+\tan) = \tfrac12\bigl(1+(\sec+\tan)^2\bigr), $$마지막 등호는 \(\sec^2-\tan^2=1\)에서 곧장 나옵니다. 출발값도 \(E(0)=\sec0+\tan0=1\)로 같으니, 두 함수는 같습니다. 따라서 \(\sum A_n x^n/n! = \sec x+\tan x\). \(\blacksquare\)
지금까진 삼각함수로 조합 문제를 풀었습니다. 이제 방향을 뒤집어, 교대순열을 세는 것만으로 삼각 항등식 \(1+\tan^2 x=\sec^2 x\)를 증명해 봅시다 — 미분도, 단위원도 없이.
도구 하나가 더 필요합니다. 지수생성함수(EGF)의 곱은 ‘라벨 붙은 쌍’을 셉니다 — \([n]\)을 두 블록으로 나눠 한쪽엔 \(f\)-구조, 다른 쪽엔 \(g\)-구조를 얹는 모든 방법(이항 합성곱). 그러므로
$$ \tan^2 x = \Bigl(\sum_{k\ \mathrm{odd}}A_k\tfrac{x^k}{k!}\Bigr)^2,\qquad \sec^2 x = \Bigl(\sum_{k\ \mathrm{even}}A_k\tfrac{x^k}{k!}\Bigr)^2. $$즉 \(\tan^2 x\)의 \(x^n/n!\) 계수는 \([n]\)을 두 블록으로 갈라 양쪽 모두 ‘홀수 길이’ 교대순열을 얹는 방법의 수(이를 \(\mathrm{OO}(n)\)), \(\sec^2 x\)의 계수는 양쪽 모두 ‘짝수 길이’인 수(\(\mathrm{EE}(n)\))예요. 상수 \(1\)은 \(n=0\)(빈 구조)만 셉니다.
2장의 ‘봉우리 논법’을 다시 씁니다. 길이 \(n+1\) 교대순열을 가장 큰 원소에서 쪼개면 양쪽이 다시 교대순열인 쌍이 되죠. 교대순열엔 두 방향(오르락 먼저 / 내리락 먼저)이 있고 개수는 둘 다 \(A_{n+1}\)입니다.
같은 \(A_{n+1}\)을 두 가지로 셌으니 모든 \(n\ge1\)에서 \(\mathrm{EE}(n)=\mathrm{OO}(n)\) — 즉 \(\sec^2\)과 \(\tan^2\)의 계수가 \(n\ge1\)에서 똑같습니다. 남은 건 \(n=0\): \(\sec^2\)은 \(1\)(빈 쌍), \(\tan^2\)은 \(0\). 따라서
$$ \sec^2 x - \tan^2 x = 1, \qquad\text{즉}\qquad 1+\tan^2 x = \sec^2 x. \qquad\blacksquare $$미분도 단위원도 없이, 봉우리에서 쪼개 세기만으로 피타고라스 삼각 항등식이 떨어졌습니다. 아래에서 \(\mathrm{EE}(n)\), \(\mathrm{OO}(n)\), \(A_{n+1}\)이 정말 같은지 확인해 보세요.
똑같은 ‘최댓값에서 쪼개기’가 시컨트의 미분 공식도 줍니다. 이번엔 길이 \(n+1\)이 짝수(즉 \(n\)이 홀수)인 교대순열을 최댓값에서 쪼개면, 한 조각은 홀수·다른 조각은 짝수 길이가 됩니다. 즉 \(A_{n+1}\)이 ‘짝수 + 홀수’ 쌍의 수 \(\mathrm{EO}(n)\)와 같고 — 그게 바로 \(\sec x\,\tan x\)의 계수죠(EGF 곱).
$$ n!\,\bigl[x^n\bigr](\sec x\,\tan x) = \mathrm{EO}(n) = A_{n+1} = n!\,\bigl[x^n\bigr](\sec x)' \quad\Rightarrow\quad (\sec x)' = \sec x\,\tan x. $$\(\tan' = \sec^2\)과 \(\sec' = \sec\tan\) — 미적분 교과서의 두 미분 공식이, 똑같이 봉우리에서 쪼개 세기로 떨어집니다.
그렇다면 지그재그 수 \(A_n\)을 빨리 구하는 길은? 파스칼 삼각형을 닮은 보스트로페돈(소가 밭 갈듯 줄마다 방향을 바꾸는) 삼각형이 있습니다. 규칙은 딱 하나 — 각 칸은 같은 줄의 직전 칸과 윗줄의 (거꾸로 센) 칸을 더한 값:
$$ T(n,k)=T(n,k-1)+T(n-1,\,n-k),\qquad T(n,0)=[\,n=0\,]. $$줄을 한 줄씩 채워 나가면, 줄 끝의 값 \(T(n,n)\)이 정확히 \(A_n\)입니다(자이델–엔트링거–아널드). 직전 줄을 거꾸로 읽으며 누적한다는 점이 ‘갈지자’라는 이름의 이유죠. 아래에서 줄 수를 늘려 보세요 — 오른쪽 모서리를 따라 \(1,1,1,2,5,16,61,\dots\)가 흘러내립니다.
\(1\times n\) 띠를 정사각형과 도미노(가로 두 칸)로 빈틈없이 덮는 방법을 셉니다. 단, 보통의 개수 세기가 아니라 무게를 매겨서 — 정사각형엔 \(2x\), 도미노엔 \(-1\) — 각 타일링마다 그 타일들의 무게를 곱하고, 모든 타일링에 대해 더합니다. 이 값을 \(U_n(x)\)라 부릅시다(\(U_0=1\), \(U_1=2x\)).
길이 \(n\) 띠의 마지막 타일을 봅니다. 정사각형(\(2x\))이면 앞의 \(n-1\)칸을 덮는 모든 방법이 뒤따르고, 도미노(\(-1\))면 앞의 \(n-2\)칸이 뒤따르죠. 무게를 곱해 더하면
$$ U_n(x) = 2x\,U_{n-1}(x) - U_{n-2}(x). $$한편 삼각함수 쪽. \(\sin((n+1)\theta)+\sin((n-1)\theta)=2\cos\theta\,\sin(n\theta)\)이므로, \(\dfrac{\sin((n+1)\theta)}{\sin\theta}\) 역시 \(x=\cos\theta\)로 두면 똑같은 점화식을 만족합니다. 게다가 \(n=0,1\)에서 두 수열의 값이 모두 \(1,\ 2\cos\theta\)로 일치하죠. 점화식과 출발값이 같으면 두 수열은 완전히 같습니다 —
$$ U_n(\cos\theta) = \frac{\sin\bigl((n+1)\theta\bigr)}{\sin\theta}. \qquad\blacksquare $$그러니 타일을 세는 일과 \(\sin((n{+}1)\theta)/\sin\theta\)를 계산하는 일이 글자 그대로 같습니다. 배각 공식 \(\sin 5\theta = \sin\theta\,(16\cos^4\theta-12\cos^2\theta+1)\)에 나오는 계수 \(16,-12,1\)은 다름 아닌 도미노 \(j\)개를 쓴 타일링의 수 \(\binom{n-j}{j}\)에 무게를 실은 값입니다. 아래에서 직접 깔아 보세요.
이 타일 그림은 곱셈·덧셈 공식까지 공짜로 줍니다. 길이 \(m+n\) 띠를 \(m\)번째 칸과 \(m{+}1\)번째 칸 사이의 솔기 기준으로 봅시다.
두 경우뿐입니다. (가) 솔기에 걸친 도미노가 없다 — 그러면 왼쪽 길이 \(m\), 오른쪽 길이 \(n\)이 독립이라 \(U_m\,U_n\). (나) 도미노 하나가 솔기를 가로지른다(무게 \(-1\)) — 그 도미노가 \(m,m{+}1\)칸을 먹으니 남은 건 왼쪽 \(m-1\), 오른쪽 \(n-1\)이고, 무게 \(-1\)이 곱해져 \(-\,U_{m-1}U_{n-1}\). 더하면
$$ U_{m+n} = U_m\,U_n - U_{m-1}\,U_{n-1}. \qquad\blacksquare $$\(x=\cos\theta\)를 넣으면 이건 그대로 삼각함수 곱→합 공식입니다 — \(\sin((m{+}n{+}1)\theta)\,\sin\theta = \sin((m{+}1)\theta)\sin((n{+}1)\theta) - \sin(m\theta)\sin(n\theta)\). ‘솔기를 가로지르는 도미노가 있나 없나’라는 이산적인 두 경우가, 연속 세계의 덧셈정리가 된 셈이죠.
두 증명의 급소는 똑같았습니다. 조합론 쪽에서 "마지막 타일을 보라" / "가장 큰 원소를 보라"로 점화식을 얻고, 해석학 쪽에서 같은 점화식(또는 그 생성함수꼴인 미분방정식)이 이미 성립함을 확인한 것. 점화식과 생성함수가 두 세계의 통역사였던 셈이죠.
이건 우연이 아닙니다. 수를 늘어놓는 방식이 ‘덧셈으로 쌓이면’ 보통의 생성함수가, ‘끼워 넣기로 쌓이면’ 지수생성함수가 자연스럽게 나오고 — 삼각함수처럼 점화식으로 정의되는 양은 어김없이 그런 ‘셈’의 그림자를 갖습니다. 그래서 \(\cos\)·\(\tan\) 같은 매끈한 곡선의 계수가, 알고 보면 타일과 순열의 개수였던 거죠. 그림 한 장으로 끝나는 증명들과 같은 즐거움 — "왜?"가 계산이 아니라 한눈에 보입니다.
마지막으로 가장 깊은 "왜?"에 답해 봅시다. 5장(체비쇼프 타일링)에서 \(\sin\)이 나온 게 우연이었을까요? 아닙니다 — 셈을 대수(행렬)로 번역하면 삼각함수가 피할 수 없이 튀어나옵니다. 이것이 ‘대수로 조합을 푸는’ 대수조합의 정신입니다.
점화식 \(U_n=2x\,U_{n-1}-U_{n-2}\)는 벡터에 행렬을 한 번 곱하는 일입니다:
$$ \begin{pmatrix}U_n\\U_{n-1}\end{pmatrix} =\underbrace{\begin{pmatrix}2x&-1\\1&0\end{pmatrix}}_{M}\begin{pmatrix}U_{n-1}\\U_{n-2}\end{pmatrix} \;\Longrightarrow\; \begin{pmatrix}U_n\\U_{n-1}\end{pmatrix}=M^{\,n}\begin{pmatrix}U_0\\U_{-1}\end{pmatrix}. $$즉 타일을 세는 일 = 행렬 \(M\)의 거듭제곱입니다(전이행렬 방법). 그리고 행렬의 거듭제곱은 고유값이 지배하죠. \(M\)의 특성방정식은
$$ \lambda^2 - 2x\,\lambda + 1 = 0,\qquad \lambda_\pm = x\pm\sqrt{x^2-1}. $$여기서 마법이 일어납니다. \(\det M = 1\)이라 두 고유값의 곱이 \(1\) — 그래서 \(x=\cos\theta\)(즉 \(|x|\le 1\))이면
$$ \lambda_\pm = \cos\theta \pm i\sin\theta = e^{\pm i\theta}. $$고유값이 정확히 복소평면 단위원 위, 각도 \(\pm\theta\)에 놓입니다. 단위원을 가정한 적이 없는데 — 행렬의 대수에서 저절로 회전 \(e^{i\theta}\)가 나온 거죠. 그러면 닫힌 형은 곧장 떨어집니다:
$$ U_n=\frac{\lambda_+^{\,n+1}-\lambda_-^{\,n+1}}{\lambda_+-\lambda_-} =\frac{e^{i(n+1)\theta}-e^{-i(n+1)\theta}}{e^{i\theta}-e^{-i\theta}}=\frac{\sin((n+1)\theta)}{\sin\theta}. $$\(|x|>1\)이면? 고유값이 단위원을 떠나 실수 두 개(서로 역수)가 되고, 답은 삼각함수 대신 지수적으로 커집니다(쌍곡함수 \(\sinh\)). 아래에서 \(x\)를 움직여, 고유값이 원 위를 돌다가 원 밖 실수축으로 튀어나가는 걸 보세요.
지금까지는 조합론이 삼각함수를 구했습니다. 이제 무대를 바꿔 — 조합론이 정수론을 구할 차례죠. 정수론 기초에 나오는 합동식 중 상당수는, 소수의 성질을 직접 파는 대신 그저 무언가를 세어서 증명할 수 있습니다. 첫 타자는 페르마의 소정리.
원 하나를 똑같은 부채꼴 \(p\)개로 등분하고, 각 칸을 \(a\)가지 색 중 하나로 칠합니다. 칠하는 모든 경우의 수는 \(a^p\)이죠. 이 색칠들을 두 부류로 나눕니다.
원을 시계방향으로 \(2\pi/p\)만큼 돌리는 걸 ‘회전’이라 합시다. 두 색 이상 쓴 목걸이는 \(p\)번 회전하면 제자리로 오는데, 그 사이 나오는 \(p\)개의 모습은 모두 서로 다릅니다. (만약 \(k\)번과 \(k+d\)번 회전한 모습이 같다면(\(0\lt d\lt p\)), 양쪽을 \(k\)번 역회전해 ‘\(d\)번 회전하면 그대로’가 되고, 그런 \(d\)의 최솟값은 \(p\)를 나눕니다. \(p\)가 소수이니 \(d=1\) — 한 칸만 돌려도 그대로라면 단색이어야 하는데, 모순.)
그러니 ‘그 외’의 \(a^p-a\)가지는 회전으로 묶으면 정확히 \(p\)개씩인 동치류로 깔끔히 나뉩니다. 따라서 \(p \mid a^p - a\), 곧 \(a^p \equiv a \pmod p\). \(\blacksquare\)
\(a\lt b\)면 양변이 0이라 자명하니 \(a \ge b\)라 하자. 단위칸을 가로 \(p\), 세로 \(a\)로 배열한 \(ap\)칸 격자에서 \(bp\)칸을 골라 칠한다. 전체 경우의 수는 \(\binom{ap}{bp}\).
각 행을 칠해진 칸 수로 분류한다 — \(1\)개 이상 \(p-1\)개 이하면 불완전, \(p\)개를 다 칠했으면 완전. 칠한 칸의 총수 \(bp\)는 \(p\)의 배수이므로 불완전한 행이 딱 1개일 수는 없다(나머지 행은 0 또는 \(p\)칸이라 \(p\)의 배수인데, 거기에 \(1\)~\(p-1\)을 더하면 총합이 \(p\)의 배수가 못 됨). 그러니 불완전 행은 0개거나 2개 이상.
불완전한 행 하나를 골라 칸들을 오른쪽으로 한 칸씩 밀기(맨 오른쪽 칸은 맨 왼쪽으로)를 ‘슬라이딩’이라 하자. 페르마 때와 똑같이, 한 불완전 행을 \(p\)번 슬라이딩하면 \(p\)개의 서로 다른 모습이 나온다. 불완전 행이 \(k\)개면 각 행을 따로 슬라이딩할 수 있어 한 동치류의 크기는 \(p^k\). \(k\ge 2\)이니 \(p^2 \mid p^k\), 따라서 그 경우의 수의 합도 \(p^2\)의 배수. \(\blacksquare\)
방금 것을 \(\bmod\ p\)로 약하게 보면 \(\binom{ap}{bp}\equiv\binom{a}{b}\). 그런데 격자에 딸린 \(c\)칸을 더 붙이면(이 \(c\)칸은 슬라이딩 없이 그대로 두고 그중 \(d\)칸을 고른다) 한 걸음 더 나아갑니다 — \(0\le c,d\lt p\)에 대해
$$ \binom{ap+c}{bp+d} \equiv \binom{a}{b}\binom{c}{d} \pmod p. $$이걸 자릿수마다 거듭 적용하면, \(a,b\)를 \(p\)진법으로 \(a=(a_k\cdots a_0)_p,\ b=(b_k\cdots b_0)_p\)로 쓸 때:
각 자리에서 \(b_i \gt a_i\)이면 그 항이 \(\binom{a_i}{b_i}=0\)이라 곱 전체가 0이 됩니다. 즉 \(\binom{a}{b}\)가 \(p\)로 나눠지지 않을 조건은 ‘\(p\)진법 모든 자리에서 \(b\)의 숫자가 \(a\)의 숫자 이하’라는 거죠. 이 단순한 규칙이 그림으로 드러난 것이 — 파스칼의 삼각형을 \(\bmod\ p\)로 칠했을 때 나타나는 자기닮은 프랙탈입니다(\(p=2\)면 그 유명한 시에르핀스키 삼각형!). 아래에서 \(p\)를 바꿔 보세요.
페르마와 더불어 정수론 기초의 또 다른 단골, 윌슨의 정리도 페테르센이 ‘세어서’ 증명했습니다.
\(1,\dots,p\)의 순열 중 길이 \(p\)짜리 순환(p-cycle) 하나로 이루어진 것은 \((p-1)!\)개입니다. 회전 \(\sigma:i\mapsto i+1 \pmod p\)로 켤레를 취하는 작용 \(w\mapsto \sigma w\sigma^{-1}\)을 생각하죠(이것도 순환군 \(C_p\)의 작용입니다). 켤레는 순환 구조를 보존하니 \(p\)-순환을 \(p\)-순환으로 보냅니다.
\(p\)가 소수라 궤도의 크기는 1 아니면 \(p\). 크기 1(고정점)은 \(\sigma w=w\sigma\), 곧 \(w\)가 \(\sigma\)와 교환되는 경우인데, \(p\)-순환 \(\sigma\)와 교환되는 원소는 \(\sigma\)의 거듭제곱뿐입니다. 그중 \(p\)-순환은 \(\sigma^1,\dots,\sigma^{p-1}\) — 곧 \(w(i)=i+k\ (0\lt k\lt p)\) 꼴의 \(p-1\)개죠. 나머지는 모두 크기 \(p\)의 궤도를 이룹니다.
따라서 \((p-1)! = (p-1) + p\cdot(\text{크기 }p\text{ 궤도의 수})\), 즉 \((p-1)!\equiv p-1\equiv -1 \pmod p\). \(\blacksquare\)
삼각함수에서는 배각 공식의 계수가 타일링의 수였고, \(\tan\)의 계수가 지그재그 순열의 수였습니다. 정수론에서는 페르마와 윌슨이 목걸이·순열을 ‘돌려서’, 이항계수의 합동식이 격자를 ‘밀어서’ 떨어졌고요. 미적분이나 소수의 깊은 성질이 필요해 보이던 자리마다, 결국 무언가를 세는 일이 답을 들고 나타났습니다. 조합론은 멀리서 불려 온 손님이 아니라, 같은 진실을 보는 또 하나의 눈이었던 셈이죠.