세지 않고 세기

짧은 음절과 긴 음절로 시를 짓는다면 가능한 운율은 몇 가지일까요? 2,000년 전 인도의 운율학자들은 목록을 다 적지 않고도 답을 냈습니다. 그 요령이 파스칼의 삼각형⁠(Pascal's triangle)⁠, 오일러의 생성함수⁠(generating function)⁠, 오늘날 알고리즘⁠(algorithm)⁠의 비용 계산으로 자라났습니다.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속 줄과 칸, 막대는 눌러서 고를 수 있습니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

산스크리트 시인이 여덟 음절짜리 시행을 짓는다고 해 봅시다. 산스크리트의 음절은 가볍거나 무겁습니다. 짧은 모음으로 끝나는 음절은 가볍고(라구), 긴 모음이 있거나 자음 두 개 앞에 놓인 음절은 무겁습니다(구루). 무거운 음절은 가벼운 음절보다 두 배쯤 길게 읊습니다. 시의 운율은 이 가볍고 무거운 음절이 늘어선 무늬입니다. 이 글에서는 가벼운 음절을 ∪, 무거운 음절을 —로 적겠습니다. 서양 운율학⁠(prosody)⁠이 쓰는 표시와 같습니다.

여덟 음절로 만들 수 있는 무늬는 모두 몇 가지일까요? 하나씩 적어 나가면 언젠가는 답이 나옵니다. 하지만 빠뜨리거나 두 번 적지 않았다는 것을 어떻게 확신할까요? 음절이 스무 개라면 무늬가 백만 개가 넘어서, 1분에 하나씩 하루 여덟 시간을 적어도 6년 가까이 걸립니다. 필요한 것은 목록을 만들지 않고 목록의 길이를 아는 방법입니다. 이 글의 제목 '세지 않고 세기'가 가리키는 것이 이것입니다. 유한한 대상들을 빠짐없이, 겹치지 않게 세고 늘어놓는 방법을 연구하는 수학을 조합론⁠(combinatorics)⁠이라고 부릅니다.

조합론은 흔히 파스칼과 페르마의 편지에서 시작하는 확률론의 곁가지처럼 소개됩니다(「도박판에서 온 편지」). 그러나 이 질문을 그보다 훨씬 먼저 붙든 것은 도박꾼이 아니라 시인과 문법학자였습니다. 인도의 운율학자, 바스라의 사전 편찬자, 바그다드와 마라케시와 항저우의 계산가들이 제각기 같은 삼각형에 이르렀습니다. 그 길을 따라가 봅시다.

1 · 짧은 음과 긴 음핑갈라의 표

이 절의 물음은 둘입니다. 음절이 $n$개인 무늬는 모두 몇 가지일까? 그리고 목록을 적지 않고도 '이 무늬는 몇 번째 줄에 있다'를 알 수 있을까? 둘 다 2,000년 전 한 운율학자가 답을 적어 두었습니다.

베다의 찬가는 글이 아니라 입에서 입으로 전해졌습니다. 한 음절도 틀리지 않게 전하려면 소리와 문법과 운율을 따로 연구해야 했고, 운율학은 베다를 지키는 여섯 보조 학문의 하나가 되었습니다. 운율학을 체계적으로 다룬 첫 책이 운율학자 핑갈라의 『찬다스 수트라』입니다. 연대는 확실하지 않아 흔히 기원전 3–2세기 무렵으로 보고, 더 이르게 잡는 학자도 있습니다. 핑갈라가 문법학자 파니니의 동생이라는 전승도 있지만 근거는 약합니다. 파니니의 문법이 규칙으로 말을 만들어 내는 장치였다는 이야기는 「말을 세는 기계」에 있습니다.

핑갈라의 책 마지막 장은 운율 하나하나가 아니라 운율 전체를 다룹니다. 주어진 음절 수의 무늬를 빠짐없이 늘어놓는 법, 몇 가지인지 세는 법, 번호를 주면 그 무늬를 찾는 법, 무늬를 주면 번호를 찾는 법이 짧은 경구로 적혀 있습니다. 그가 늘어놓은 표를 '프라스타라'(펼침)라고 부릅니다.

표를 만드는 규칙을 두 음절로 먼저 따라가 봅시다. 첫 줄은 모두 무거운 음절 ——입니다. 다음 줄은 앞 줄에서 왼쪽부터 보아 처음 나오는 —를 ∪로 바꾸고, 그보다 왼쪽에 있는 음절은 모두 —로 되돌려 만듭니다. 그러면 —— 다음은 ∪—, 그다음은 —∪(둘째 자리의 —가 ∪가 되고 첫째 자리는 —로 돌아갑니다), 마지막은 ∪∪입니다. 네 줄에서 두 음절 무늬가 모두 한 번씩 나왔습니다. 음절 수를 개로 바꿔 가며 표를 보세요. 음절이 하나 늘 때마다 줄 수가 두 배가 되는지 보면 됩니다.

음절이 개이면 무늬는 가지입니다. 왜 그런지 세 음절로 따져 봅시다. 첫 음절은 ∪ 아니면 —, 두 갈래입니다. 첫 음절을 무엇으로 정했든 둘째 음절이 또 두 갈래이니, 두 음절까지는 2 × 2 = 4갈래입니다. 셋째 음절도 두 갈래이니 2 × 2 × 2 = 8갈래입니다. 음절이 $n$개이면 2를 $n$번 곱한 $2 \times 2 \times \cdots \times 2 = 2^n$갈래입니다($2^n$은 '2의 $n$제곱'이라 읽고, 2를 $n$번 곱한 수를 뜻합니다).

이렇게 여러 번의 결정을 차례로 내릴 때, 앞의 결정이 무엇이었든 다음 결정의 가짓수가 같다면 전체 가짓수는 각 결정의 가짓수를 곱한 것입니다. 이것을 곱의 법칙⁠(rule of product)⁠이라고 합니다. 여덟 음절이면 $2^8 = 256$가지입니다. 무늬를 하나도 적지 않고 셌습니다.

이제 둘째 물음, 번호입니다. 핑갈라의 규칙은 이렇습니다. 자리마다 왼쪽부터 1, 2, 4, 8, …의 값을 주고(한 자리 오른쪽으로 갈 때마다 두 배), 가벼운 음절 ∪가 놓인 자리의 값만 모아 1에 더하면 줄 번호가 됩니다. 세 음절 무늬 ∪∪—로 해 보면, ∪가 있는 첫째와 둘째 자리의 값 1과 2를 1에 더해 1 + 1 + 2 = 4, 곧 넷째 줄입니다. 그림에서 직접 확인해 보세요. 지금 고른 번째 줄의 무늬는 입니다.

이 규칙은 우리가 아는 수 표기법과 닮았습니다. 보통 쓰는 십진법은 자리의 값이 1, 10, 100, …이고, 이진법⁠(binary)⁠은 자리의 값이 1, 2, 4, 8, …이며 자리마다 0 아니면 1만 씁니다. 예를 들어 3 = 2 + 1이므로 이진법으로 11, 5 = 4 + 1이므로 101입니다. 이제 ∪를 1, —를 0으로 읽어 봅시다. ∪∪—는 110이 되고, 이것을 오른쪽에서 왼쪽으로 뒤집은 011은 이진법으로 3, 곧 줄 번호 4에서 1을 뺀 수입니다. 어느 무늬든 마찬가지입니다. 핑갈라의 표는 0부터 $2^n - 1$까지의 수를 차례로 이진수로 적은 표이기도 합니다(다만 자릿값이 오른쪽이 아니라 왼쪽에서부터 커집니다). 라이프니츠가 이진법을 발표한 것은 1703년이었습니다. 그가 이진법을 『주역』의 괘와 어떻게 이었는지는 「기계가 풀 수 없는 문제」 첫머리에 있습니다.

곱의 법칙은 우리 곁에도 있습니다. 한글 음절 하나는 첫소리 자음(초성⁠, initial consonant⁠) 19개 가운데 하나, 가운데 모음(중성) 21개 가운데 하나, 받침(종성⁠, final consonant⁠) 27개에 '받침 없음'을 더한 28가지 가운데 하나를 골라 모아 씁니다. 그러니 현대 한글로 쓸 수 있는 음절은 $19 \times 21 \times 28 = 11{,}172$개이고, 컴퓨터의 유니코드 표에는 실제로 이 11,172자가 차례로 들어 있습니다. 『주역』의 괘도 음과 양 두 가지 효(막대)를 여섯 번 쌓으니 $2^6 = 64$괘입니다.

집합(물건들의 모임)에서도 같은 셈이 나옵니다. 집합⁠(set)⁠의 원소⁠(element)⁠ 가운데 몇 개를 골라 만든 집합을 부분집합⁠(subset)⁠이라 합니다(하나도 고르지 않은 빈 집합과 전부 고른 집합도 칩니다). {가, 나}의 부분집합은 { }, {가}, {나}, {가, 나}의 4개입니다. 원소마다 '넣는다, 뺀다' 두 갈래를 정하니, 원소가 $n$개인 집합의 부분집합은 $2^n$개입니다. 부분집합 전체의 모임을 멱집합⁠(power set)⁠이라 부릅니다. 음절마다 ∪와 —를 정하는 것과 같은 셈입니다.

곱의 법칙의 짝은 합의 법칙입니다. 세고 싶은 경우들이 서로 겹치지 않는 몇 묶음으로 나뉘면, 묶음마다 센 수를 더하면 됩니다. 예를 들어 한 음절부터 네 음절까지의 운율은 음절 수로 묶으면 네 묶음이고, 한 무늬가 두 묶음에 들 수는 없으니 모두 $2 + 4 + 8 + 16 = 30$가지입니다. 흔히 '여러 번 고르면 곱하고, 여러 경우로 나뉘면 더한다'고 외우지만, 더하기 전에는 묶음이 정말 겹치지 않는지, 곱하기 전에는 각 단계의 가짓수가 앞의 선택과 상관없이 같은지 확인해야 합니다.

전통적인 해석에 따르면 핑갈라는 $2^n$을 구하는 규칙도 적었습니다. $n$이 짝수이면 반으로 줄인 경우의 답을 제곱하고($2^n = 2^{n/2} \times 2^{n/2}$), 홀수이면 1을 뺀 경우의 답에 2를 곱합니다($2^n = 2^{n-1} \times 2$). 이렇게 하면 $2^{32}$도 곱셈 여섯 번이면 됩니다. 오늘날 컴퓨터가 큰 거듭제곱을 빠르게 계산하는 방법(「나머지로 지키는 비밀」)과 같은 모양입니다. 이 경구에서 '비었다'는 표시로 쓰인 말 '슌야'가 뒷날 인도에서 0을 가리키는 말이 되었다는 점도 자주 언급됩니다.

정리하면, 무늬가 몇 가지인지는 곱의 법칙이 알려 주고($2^n$), 몇 번째 무늬인지는 무늬를 이진수로 읽으면 나옵니다. 곱과 합, 이 두 법칙이 세기의 기본 문법이고, 문제는 늘 어디서 곱하고 어디서 더할지를 알아보는 데 있습니다.

2 · 메루산의 계단이항계수⁠(binomial coefficient)⁠와 여러 문명의 삼각형

시인에게 더 쓸모 있는 질문은 이것입니다. 여섯 음절 가운데 무거운 음절이 정확히 두 개인 운율은 몇 가지일까요? 이 절에서는 이런 수를 목록 없이 구하는 두 가지 방법, 덧셈으로 쌓는 방법과 곱셈 한 번으로 구하는 방법을 봅니다.

작은 경우부터 손으로 셉시다. 네 음절 가운데 무거운 음절이 두 개인 무늬는 ——∪∪, —∪—∪, —∪∪—, ∪——∪, ∪—∪—, ∪∪——의 6가지입니다. 무늬 하나는 '네 자리 가운데 어느 두 자리에 —를 놓았는가'로 정해지므로, 이 6은 네 자리 가운데 두 자리를 고르는 방법의 수입니다. 이 수를 이항계수라 하고 $\binom{4}{2} = 6$으로 적습니다. 일반적으로 $\binom{n}{k}$는 '$n$개 가운데 $k$개를 고르는 방법의 수'이고, 'n 선택 k'라고 읽습니다. 고르는 순서는 따지지 않습니다.

앞 그림에서 무늬들을 무거운 음절의 수로 묶어 보면, 여섯 음절일 때 묶음의 크기가 무거운 음절 0개부터 6개까지 차례로 1, 6, 15, 20, 15, 6, 1입니다. 처음 질문의 답은 무거운 음절이 두 개인 묶음의 크기, 곧 여섯 자리 가운데 두 자리를 고르는 방법의 수 $\binom{6}{2} = 15$입니다.

핑갈라의 경구는 이 수를 구하는 방법을 한 줄로 암시할 뿐입니다. 10세기 무렵의 주석가 할라유다는 그 줄을 수의 탑으로 풀어 설명하고 '메루 프라스타라', 곧 메루산의 계단이라고 불렀습니다. 메루는 인도 우주론에서 세계의 중심에 솟은 산입니다. 계단의 맨 위에 1을 놓고, 아래 칸마다 바로 위 두 칸의 수를 더해 채웁니다(양 끝 칸은 위 칸이 하나뿐이니 1입니다). 그러면 줄마다 1 / 1 1 / 1 2 1 / 1 3 3 1 / 1 4 6 4 1 / …이 됩니다. 맨 위의 1을 0째 줄로 치면 넷째 줄은 1 4 6 4 1이고, 그 가운데의 6 = 3 + 3이 방금 손으로 센 $\binom{4}{2}$입니다. 오늘날 우리가 파스칼의 삼각형이라고 부르는 바로 그 삼각형입니다.

아래 그림에서 맨 위 칸을 0째 줄로 치면, $n$째 줄의 왼쪽에서 $k$번째 칸(맨 왼쪽을 0번째로 칩니다)이 $\binom{n}{k}$입니다. 칸을 눌러 보고, 그 칸에 이르는 길이 몇 개인지와 칸에 적힌 수를 비교해 보세요.

왜 위의 두 수를 더할까요? 무늬 하나를 계단을 내려가는 길 하나로 바꾸어 보면 보입니다. 지금 칸은 음절 가운데 무거운 음절이 개인 무늬들의 칸이고, 그런 무늬는 가지입니다. 지금 진하게 그려진 길은 무늬 입니다. 다음 무늬 ▶ 모든 무늬 훑기 어느 무늬든 마지막 한 걸음은 두 부모 칸 가운데 하나에서 옵니다. 칸의 수는 그 칸에 이르는 길의 수이고, 그 길은 둘 중 한 부모를 반드시 거칩니다. 두 부모를 동시에 거치는 길은 없으니(마지막 한 걸음은 하나뿐입니다) 합의 법칙⁠(rule of sum)⁠으로 두 부모의 수를 더하면 됩니다. 그래서

식을 말로 읽으면 이렇습니다. $n$음절에 무거운 음절이 $k$개인 무늬는, 마지막 음절이 무거운 것(앞의 $n-1$음절에 무거운 음절 $k-1$개)과 마지막 음절이 가벼운 것(앞의 $n-1$음절에 무거운 음절 $k$개)으로 나뉩니다. 앞의 네 음절 예로는 $\binom{4}{2} = \binom{3}{1} + \binom{3}{2} = 3 + 3 = 6$입니다. 앞의 목록에서 —로 끝나는 무늬는 —∪∪—, ∪—∪—, ∪∪——의 3개이고, ∪로 끝나는 무늬는 ——∪∪, —∪—∪, ∪——∪의 3개입니다.

이 덧셈 규칙은 계산표로도 쓸모 있습니다. 곱셈 없이 덧셈만으로 필요한 줄까지 내려가면 됩니다. 하지만 $\binom{45}{6}$처럼 큰 수가 필요하면 45줄을 내려가야 합니다. 곱셈으로 한 번에 구하는 공식을 만들려면 먼저 '늘어놓기'를 세어야 합니다.

$n$개를 한 줄로 늘어놓는 방법은 첫 자리에 올 것이 $n$가지, 첫 자리를 정하고 나면 다음 자리에 올 것이 $n-1$가지, …, 마지막 자리는 남은 1가지이므로 곱의 법칙으로 $n! = n \times (n-1) \times \cdots \times 1$가지입니다(순열⁠, permutation⁠). 이 곱을 $n!$로 적고 '$n$ 팩토리얼⁠(factorial)⁠' 또는 $n$의 계승이라 부릅니다. 예를 들어 A, B, C를 늘어놓는 방법은 ABC, ACB, BAC, BCA, CAB, CBA의 $3! = 3 \times 2 \times 1 = 6$가지이고, 네 개면 $4! = 4 \times 3 \times 2 \times 1 = 24$가지입니다.

이제 고르기를 늘어놓기로 셉니다. A, B, C, D 네 개 가운데 두 개를 고르는 경우로 해 봅시다. 네 개를 늘어놓는 24가지를 '앞의 두 자리에 무엇이 왔는가'로 묶습니다. 앞 두 자리가 {A, B}인 묶음에는 ABCD, ABDC, BACD, BADC의 4줄이 있습니다. 앞 두 자리 안의 순서 $2! = 2$가지와 뒤 두 자리 안의 순서 $2! = 2$가지를 곱한 수입니다. 묶음마다 이렇게 4줄씩이니 묶음은 24 ÷ 4 = 6개이고, 묶음 하나가 두 개를 고르는 방법 하나이므로 $\binom{4}{2} = 6$입니다.

일반적으로도 같습니다. $n$개를 늘어놓은 $n!$가지를 '앞의 $k$자리에 어떤 것들이 왔는가'로 묶으면, 묶음 하나는 $k$개를 고르는 방법 하나에 해당합니다. 묶음마다 앞 $k$자리 안의 순서 $k!$가지와 뒤 $n-k$자리 안의 순서 $(n-k)!$가지를 곱한 만큼의 줄이 들어 있으니, 전체 줄 수를 묶음 하나의 줄 수로 나누면 묶음의 수가 나옵니다.

($6! = 720$, $2! = 2$, $4! = 24$입니다. 식이 성립하려면 $0! = 1$로 약속합니다. 0개를 늘어놓는 방법은 '아무것도 하지 않기' 한 가지이기 때문입니다.) 정리하면, 이항계수는 위의 두 칸을 더해 쌓을 수도 있고, 늘어놓기의 수를 겹친 만큼 나누어 한 번에 구할 수도 있습니다.

세는 일이 문명마다 다른 질문에서 시작해 같은 곳에 이르렀다는 것이 이 삼각형의 이야기입니다. 6세기 우자인의 천문학자 바라하미히라는 백과사전 『브리하트 삼히타』에서 향료 16가지 가운데 4가지를 섞어 만드는 향수가 $\binom{16}{4} = 1{,}820$가지라고 적었습니다. 8세기 바스라의 알할릴은 아랍어 운율학을 세운 사람이면서, 자음 두세 개로 된 어근의 모든 순서를 따져 낱말을 빠짐없이 싣는 첫 아랍어 사전을 구상했습니다. 인도와 아랍에서 모두 운율과 낱말, 곧 언어가 세기의 첫 무대였던 셈입니다.

이항계수 표가 대수와 만난 것은 11세기 무렵입니다. 이항계수라는 이름도 여기서 나왔습니다. $(a+b)^2 = a^2 + 2ab + b^2$, $(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$처럼 두 항(이항)의 합을 거듭제곱해 전개하면 계수가 1, 2, 1과 1, 3, 3, 1, 곧 삼각형의 줄이 됩니다. $(a+b)$를 $n$번 곱할 때 괄호마다 $a$와 $b$ 가운데 하나를 고르고, $b$를 고를 괄호 $k$개를 정하는 방법이 $\binom{n}{k}$가지이기 때문입니다. 바그다드의 수학자 알카라지는 $(a+b)^n$을 전개한 계수들을 표로 만들고, 그 표가 위의 덧셈 규칙으로 이어진다는 것을 보였습니다. 그의 책은 사라지고 12세기 수학자 알사마왈의 책에 인용된 대목으로 전합니다. 비슷한 무렵 북송의 수학자 가헌은 제곱근과 세제곱근을 구하는 데 같은 삼각형을 썼고, 1261년 항저우의 수학자 양휘가 이것을 자기 책에 옮겨 실었습니다. 13세기 초 알모하드 왕조의 수도 마라케시에서는 수학자 이븐 문임이 비단실의 색깔을 고르는 문제를 본보기로 조합의 규칙과 표를 세우고, 그것으로 정해진 길이의 아랍어 낱말이 몇 개인지 셌습니다. 1321년에는 프로방스의 유대인 수학자이자 철학자 게르손의 레비가 순열과 조합의 공식을 한 단계씩 늘려 가는 논증으로 증명했습니다.

파스칼이 이 삼각형의 성질을 책 한 권으로 정리한 것은 1654년 무렵입니다. 그해 여름 그는 페르마와 편지를 주고받으며 도중에 멈춘 도박판의 판돈을 나누는 문제를 풀고 있었고, 『산술 삼각형론』에도 이 판돈 나누기에 삼각형을 쓰는 법을 다룬 부분이 있습니다(「도박판에서 온 편지」). 인쇄는 1654년에 끝났지만 책이 세상에 나온 것은 그가 죽은 뒤인 1665년입니다. 유럽에서도 파스칼이 처음은 아니었습니다. 1527년 독일의 천문학자 페트루스 아피아누스가 상인을 위한 산술책의 표지에 이 삼각형을 새겼고, 1556년에는 이탈리아의 타르탈리아도 책에 실었습니다. 그래서 이 삼각형의 이름은 나라마다 다릅니다. 이탈리아에서는 '타르탈리아의 삼각형', 중국에서는 '양휘의 삼각형', 이란에서는 '하이얌의 삼각형'이라고 부릅니다. 이름은 처음 찾은 사람보다 그 나라에 이 삼각형을 알린 사람을 기억하는 셈입니다.

기원전 3세기 무렵부터 1400년까지. 인도의 우자인과 파탄, 아바스 왕조의 바스라와 바그다드, 송나라의 카이펑과 항저우, 알모하드 왕조의 마라케시. 같은 삼각형이 서로 다른 질문에서 거의 독립적으로 나타났습니다. 어디까지가 전파이고 어디부터가 독립적인 발견인지는 지금도 연구가 이어지고 있습니다.

세기는 철학자의 꿈이기도 했습니다. 13세기 마요르카의 철학자이자 신학자 라몬 률은 신의 속성 같은 기본 개념들을 원판에 적었습니다. 원판을 돌려 모든 조합을 만들어 내면 신앙의 진리를 논증할 수 있다고 믿었습니다. 그 꿈에는 자란 곳의 사정이 배어 있습니다. 마요르카는 률이 태어나기 몇 해 전인 1229년 아라곤 왕 하이메 1세가 무슬림 통치자에게서 빼앗은 섬이었고, 률은 이 땅의 이슬람교도와 유대교도를 논증으로 설득해 개종시키고 싶어 했습니다. 그래서 세 종교가 모두 받아들일 기본 개념에서 출발해, 그 조합을 빠짐없이 따지는 기계적인 절차를 원했던 것입니다. 그로부터 400년 가까이 지나 스무 살의 라이프니츠는 순열과 조합을 다룬 『결합술』(1666)에서 률을 언급하며, 모든 생각을 기본 개념의 조합으로 적고 계산으로 추론하는 꿈을 펼쳤습니다. 그보다 앞선 1636년에는 파리의 수도사이자 수학자 마랭 메르센이 음악 이론서 『보편적 조화』에서 음 몇 개로 만들 수 있는 가락의 수를 세면서, 여섯 음의 순서 720가지를 모두 적은 목록과 긴 계승의 표를 실었다고 전합니다.

계승은 무섭게 자랍니다. $5! = 120$, $10! = 3{,}628{,}800$이고, 카드 52장을 섞는 방법은 $52! \approx 8 \times 10^{67}$가지입니다($10^{67}$은 1 뒤에 0이 67개 붙은 수이고, ≈는 '약'이라는 뜻입니다). 80억 명이 우주의 나이인 138억 년 동안 1초에 한 번씩 섞었다고 쳐도 $4 \times 10^{27}$번이 안 됩니다. 이 수에 비하면 없는 것과 같습니다. 그러니 모든 순서가 똑같은 확률⁠(probability)⁠로 나오도록 잘 섞은 카드의 순서는 거의 틀림없이 역사상 한 번도 나온 적이 없는 순서입니다. 반대로 한국 로또처럼 45개의 수에서 6개를 고르는 방법은 $\binom{45}{6} = 8{,}145{,}060$가지입니다. 한 장을 사서 1등에 당첨될 확률은 약 814만분의 1입니다.

바라하미히라가 향료를 '고르는' 방법을 셌다면, 일본의 향 놀이 겐지코(源氏香)는 향을 '무리로 나누는' 방법을 셉니다. 향 다섯 개를 차례로 맡고 어느 것끼리 같은 향인지 맞히는 놀이입니다. 답은 다섯 개의 세로줄 가운데 같은 향끼리 위에서 가로줄로 이어 묶은 그림으로 냅니다. 세 개로 줄여 세어 보면, 모두 같음 1가지, 둘만 같음 3가지(어느 하나가 다른가), 모두 다름 1가지로 5가지입니다. 다섯 개면 이런 묶음이 52가지이고, 그림 52개에는 『겐지 이야기』 54첩 가운데 처음과 마지막을 뺀 52첩의 이름이 붙었습니다. 1726년 일본의 수학자 마쓰나가 요시스케는 몇 개의 향이든 이렇게 묶는 방법의 수를 계산하는 원고를 썼고, 그의 결과는 1769년 아리마 요리유키의 책에 실려 알려졌습니다. 오늘날 이 수들(1, 2, 5, 15, 52, 203, …)을 벨 수⁠(Bell number)⁠라고 부릅니다. 스코틀랜드에서 태어나 미국에서 일한 수학자 에릭 템플 벨의 이름을 딴 것인데, 벨 자신도 이 수가 여러 번 다시 발견되었다고 적었습니다.

3 · 박자로 세기비라한카와 헤마찬드라, 그리고 토끼

이 절의 물음은 이것입니다. 음절 수가 아니라 박자 수가 정해져 있으면 무늬는 몇 가지일까? 이번에는 곱의 법칙이 바로 통하지 않습니다. 음절 수가 무늬마다 달라서 '자리마다 두 갈래'라고 말할 수 없기 때문입니다. 대신 큰 경우의 답을 작은 경우의 답으로 짓는 방법을 배웁니다.

인도의 운율에는 음절 수가 아니라 박자 수를 맞추는 종류도 있습니다. 가벼운 음절은 한 박, 무거운 음절은 두 박입니다. 이 '마트라' 운율은 프라크리트어의 노래나 민요에서 널리 쓰였습니다. 프라크리트어는 산스크리트에서 갈라져 나와 사람들이 일상에서 쓰던 중세 인도의 여러 말입니다. 마트라 운율에서는 한 행의 음절 수가 들쭉날쭉해도 박자의 합은 같아야 합니다. 예를 들어 4박이면 ∪∪∪∪(네 음절), —∪∪, ∪—∪, ∪∪—(세 음절), ——(두 음절)의 5가지입니다. 그렇다면 박자의 합이 박인 무늬는 몇 가지일까요? 아래에서는 짧은 음절을 한 칸, 긴 음절을 두 칸짜리 막대로 그렸습니다. 박자 수를 바꿔 가며, 왼쪽 무리와 오른쪽 무리가 각각 몇 개인지 보세요.

지금 무늬는 모두 가지입니다. 이번에는 목록을 마지막 음절로 나누어 봅시다. 끝이 짧은 음절인 무늬에서 마지막 ∪를 떼면 한 박 짧은 무늬가 남고, 끝이 긴 음절인 무늬에서 마지막 —를 떼면 두 박 짧은 무늬가 남습니다. 로 확인해 보세요. 떼고 남은 것들은 각각 한 박 짧은 무늬 전부, 두 박 짧은 무늬 전부이고, 빠지거나 겹치는 것이 없습니다. 4박으로 확인해 봅시다. ∪로 끝나는 ∪∪∪∪, —∪∪, ∪—∪에서 마지막 ∪를 떼면 ∪∪∪, —∪, ∪—가 남는데, 이것이 3박 무늬 세 가지 전부입니다. —로 끝나는 ∪∪—, ——에서 마지막 —를 떼면 ∪∪, —가 남는데, 이것이 2박 무늬 두 가지 전부입니다. 거꾸로 3박 무늬 어느 것에든 ∪를 붙이면 4박 무늬가 되니, 떼기와 붙이기는 서로를 되돌립니다. 그러니 합의 법칙으로

입니다. 여기서 $M_m$은 박자의 합이 $m$박인 무늬의 수입니다($M_4 = 5$처럼 아래 첨자가 박자 수입니다). 식은 '$m$박 무늬의 수는 한 박 짧은 무늬의 수와 두 박 짧은 무늬의 수를 더한 것'이라고 읽습니다. 4박이면 $M_4 = M_3 + M_2 = 3 + 2 = 5$, 5박이면 $M_5 = 5 + 3 = 8$입니다.

2박에서 긴 음절 하나를 떼면 '빈 무늬' 하나가 남으므로, 0박 무늬를 하나로 쳐서 $M_0 = 1$로 두면 이 식은 $m = 2$부터 성립합니다($M_2 = M_1 + M_0 = 1 + 1 = 2$). 앞의 두 항으로 다음 항을 정하는 이런 규칙을 점화식⁠(recurrence relation)⁠이라고 합니다. 목록을 적는 대신 '큰 문제의 답을 작은 문제의 답으로 짓는 규칙'을 찾은 것입니다. 오른쪽 계단에서 각 막대가 앞의 두 막대의 합이라는 것을 보세요.

인도에서 이 수열을 처음 적은 사람으로는 흔히 운율학자 비라한카를 꼽습니다. 그의 연대는 6세기에서 8세기 사이로 폭이 넓습니다. 12세기에는 그의 책에 주석을 단 고팔라가 1, 2, 3, 5, 8, …을 직접 적었고, 1150년 무렵 구자라트의 자이나교 학승 헤마찬드라는 운율서에서 "앞의 수와 그 앞의 수를 더하면 다음 박자의 운율 수가 된다"는 뜻의 규칙을 남겼습니다. 핑갈라의 경구 가운데 한 줄이 이미 이것을 가리킨다고 읽는 학자도 있습니다.

유럽에서는 이 수열이 전혀 다른 문제로 등장합니다. 1202년 피사의 레오나르도, 곧 피보나치는 『산반서』에서 이렇게 물었습니다. 토끼 한 쌍은 태어난 지 두 달째부터 달마다 새끼 한 쌍을 낳습니다. 이미 새끼를 낳을 수 있는 한 쌍에서 시작하면 한 해 뒤에는 몇 쌍이 될까? 이번 달의 토끼는 지난달의 토끼에, 두 달 전에 이미 있던 토끼(이번 달에 새끼를 낳을 수 있는 쌍)가 낳은 쌍을 더한 것입니다. 그러니 역시 앞의 두 항의 합이고, 1, 2, 3, 5, …로 열두 달을 가면 답은 377쌍입니다. 피보나치는 세관 관리였던 아버지를 따라간 북아프리카의 부지(오늘날 알제리의 베자이아)에서 인도·아라비아 숫자를 배웠다고 스스로 적었습니다. 이 수열에 피보나치 수열⁠(Fibonacci sequence)⁠이라는 이름을 붙인 것은 1870년대 프랑스의 수학자 에두아르 뤼카입니다. 이웃한 두 항의 비는 황금비⁠(golden ratio)⁠ $1.618\ldots$로 다가갑니다. 예를 들어 $8/5 = 1.6$, $34/21 \approx 1.619$이고, 황금비는 정확히 $(1+\sqrt5)/2$입니다.

두 절의 그림은 서로 이어져 있습니다. $m$박 무늬 가운데 긴 음절이 $k$개인 것은 음절이 모두 $m-k$개이고(긴 음절 하나가 두 박을 차지하니 음절이 하나 줄어듭니다) 그중 $k$자리를 긴 음절로 고른 것이므로 $\binom{m-k}{k}$가지입니다. 이것을 $k$에 대해 모두 더한 값이 피보나치 수입니다. 4박이면 $\binom{4}{0} + \binom{3}{1} + \binom{2}{2} = 1 + 3 + 1 = 5$로, 앞에서 센 다섯 가지와 같습니다. 메루의 계단을 비스듬히 가로질러 더하면 피보나치 수가 나오는 까닭입니다.

정리하면, 박자 무늬는 마지막 음절로 나누어 세면 앞의 두 답의 합이 되고, 그 수열이 인도에서는 운율의 수로, 유럽에서는 토끼의 수로 나타난 피보나치 수입니다.

4 · 64개의 금 원판하노이의 탑⁠(Tower of Hanoi)⁠과 수학적 귀납법⁠(mathematical induction)⁠

1883년 파리에 '시암의 N. 클라우스 교수'가 만들었다는 퍼즐이 나왔습니다. 기둥 세 개와 크기가 다른 원판 몇 장이 있습니다. 원판을 한 번에 한 장씩 옮기되 큰 원판을 작은 원판 위에 얹으면 안 됩니다. 왼쪽 기둥의 탑을 통째로 오른쪽 기둥으로 옮기는 것이 목표입니다. 이름 'N. Claus de Siam'은 '아미앵의 뤼카(Lucas d'Amiens)'의 철자를 섞은 것이었습니다. 앞 절의 에두아르 뤼카가 만든 퍼즐, 하노이의 탑입니다.

이 절의 물음은 이것입니다. 원판이 $n$장일 때 가장 적게 몇 번 옮겨야 할까? 그리고 몇 장의 경우를 확인해서 찾은 답이 모든 $n$에서 맞다는 것은 어떻게 확신할까? 원판을 장으로 하고 옮겨 보세요. 옮기는 동안 가장 큰 원판이 언제 움직이는지, 그 순간 나머지 원판들이 어디에 있는지 보세요.

큰 원판이 움직이기 직전으로 지금 번 옮겼고, 모두 번이 필요합니다.

핵심은 가장 큰 원판에 있습니다. 이 원판이 오른쪽 기둥으로 가려면 그 순간 나머지 원판은 모두 가운데 기둥에 탑으로 비켜 있어야 합니다. 그러니 원판 $n$장을 옮기는 일은 세 단계입니다. 위의 $n-1$장을 가운데로 옮기고, 가장 큰 원판을 한 번 옮기고, $n-1$장을 다시 그 위로 옮깁니다. 원판 $n$장을 옮기는 데 필요한 횟수를 $T_n$이라 하면, 세 단계의 횟수를 더해 $T_n = T_{n-1} + 1 + T_{n-1}$입니다. 원판 1장은 한 번이면 되니 $T_1 = 1$이고, 차례로 계산하면 이렇습니다.

1, 3, 7, 15, 31은 2, 4, 8, 16, 32보다 하나씩 작습니다. 그래서 답은 이렇게 짐작됩니다(⟹는 '그러므로'라고 읽습니다).

이 방법은 문제를 같은 모양의 더 작은 문제로 줄입니다. 원판 $n$장의 풀이 안에 $n-1$장의 풀이가 두 번 들어 있습니다. 컴퓨터 과학에서는 이런 설계를 재귀⁠(recursion)⁠라고 부르고, 수많은 알고리즘이 이 모양입니다.

흔히 '이 방법으로 $2^n - 1$번에 옮겼으니 그것이 최소'라고 생각하기 쉽지만, 그것은 따로 보여야 합니다. 더 영리한 방법이 있을지도 모르니까요. 논리는 이렇습니다. 가장 큰 원판은 적어도 한 번 움직여야 합니다. 그것이 처음 움직이는 순간, 나머지 $n-1$장은 모두 다른 한 기둥에 탑으로 모여 있어야 합니다(큰 원판이 떠나는 기둥과 내려앉는 기둥에는 다른 원판이 없어야 하니까요). 거기까지 적어도 $T_{n-1}$번이 듭니다. 가장 큰 원판이 마지막으로 움직인 뒤에도 $n-1$장을 다시 그 위로 모아야 하니 또 적어도 $T_{n-1}$번입니다. 그러니 어떤 방법이든 $2T_{n-1} + 1$번 이상이 들고, 위의 방법은 정확히 그만큼 쓰므로 가장 짧습니다.

그런데 $T_n = 2^n - 1$이 모든 $n$에서 맞다는 것은 어떻게 확신할까요? 다섯 경우를 계산해 본 것만으로는 여섯째에서 틀리지 않는다는 보장이 없습니다. 두 단계로 확인합니다. 첫째, 원판 1장이면 $2^1 - 1 = 1$번이니 맞습니다. 둘째, 어떤 $n-1$에서 맞다고, 곧 $T_{n-1} = 2^{n-1} - 1$이라고 해 봅시다. 그러면 $T_n = 2(2^{n-1} - 1) + 1 = 2^n - 1$이니 $n$에서도 맞습니다. 중간을 풀어 쓰면 이렇습니다.

첫째 단계로 $n = 1$에서 맞고, 둘째 단계를 한 번 쓰면 $n = 2$에서, 또 한 번 쓰면 $n = 3$에서 맞습니다. 이렇게 어느 $n$에든 유한 번 만에 닿습니다. 첫 도미노가 넘어지고, 어느 도미노든 넘어지면 다음 도미노를 넘어뜨린다면 모든 도미노가 넘어지는 것과 같습니다. 이것이 수학적 귀납법입니다. 무한히 많은 경우를 유한한 두 단계로 확인하는 방법이니, '세지 않고 세기'의 증명판이라 할 만합니다.

뤼카는 퍼즐에 전설을 곁들였습니다. 인도 베나레스의 한 사원에서 브라만 승려들이 64장의 금 원판으로 된 탑을 옮기고 있고, 일이 끝나는 날 세상이 끝난다는 것입니다. 물론 지어낸 이야기입니다. 필요한 횟수는 $2^{64} - 1 = 18{,}446{,}744{,}073{,}709{,}551{,}615$번, 1초에 한 장씩 쉬지 않고 옮겨도 5,800억 년이 넘게 걸립니다. 우주 나이의 40배쯤입니다. 원판이 한 장 늘 때마다 횟수가 두 배쯤 되니, 원판 수가 조금만 늘어도 횟수는 감당할 수 없게 됩니다. 이렇게 $n$이 하나 늘 때마다 두 배가 되는 지수함수⁠(exponential function)⁠의 증가는 알고리즘의 비용을 따질 때 가장 먼저 피해야 할 적입니다(점근 표기법⁠(asymptotic notation)⁠, 「기계가 풀 수 없는 문제」 7절).

귀납법의 역사는 깁니다. 알카라지의 이항계수 논증과 게르손의 레비의 증명에 이미 그 모양이 보이고, 1575년 시칠리아 메시나의 수학자 프란체스코 마우롤리코는 첫 $n$개 홀수의 합이 $n^2$이라는 것(1 + 3 = 4, 1 + 3 + 5 = 9, …)을 앞의 경우에서 다음 경우로 넘어가는 방식으로 보였습니다. 파스칼은 『산술 삼각형론』에서 이 논증을 분명한 두 단계로 적어 삼각형의 성질을 증명했습니다. '수학적 귀납법'이라는 이름은 1838년 런던의 수학자 오거스터스 드모르간이 백과사전 항목에 쓰면서 자리 잡았습니다. 과학에서 말하는 귀납은 몇 가지 사례를 보고 일반 법칙을 짐작하는 것이라, 사례가 아무리 많아도 다음 사례에서 틀릴 수 있습니다. 드모르간은 수학적 귀납법이 이름과 달리 그런 짐작이 아니라, 전제가 참이면 결론도 반드시 참인 엄밀한 연역(이미 참이라고 인정한 것에서 논리만으로 결론을 끌어내는 추론)이라는 점을 강조했습니다.

19세기 말에는 귀납법이 증명의 요령에서 자연수⁠(natural number)⁠의 정의 자체로 올라섰습니다. 1888년 데데킨트는 『수란 무엇이며 무엇이어야 하는가』에서 자연수를 '1에서 시작해 다음 수로 넘어가기를 되풀이해 닿는 수들'의 모임으로 정의했고, 이듬해 토리노의 주세페 페아노가 자연수의 성질을 짧은 공리⁠(axiom)⁠들로 적었습니다. 공리는 증명 없이 출발점으로 받아들이는 명제입니다. 오늘날 흔히 다섯 개로 정리하는 이 공리 가운데 하나가 바로 귀납법, 곧 '1에서 성립하고, 어떤 수에서 성립하면 다음 수에서도 성립하는 성질은 모든 자연수에서 성립한다'입니다. 그런데 이 공리들만으로는 증명할 수 없는, 참인 조합론 명제가 있다는 것이 1977년에 밝혀졌습니다. 그 이야기는 「완전한 무질서는 없다」 8절에 있습니다.

귀납법이 왜 믿을 만한지를 두고는 철학자들의 답이 갈렸습니다. 예나의 프레게는 1879년 『개념 표기법』에서 '다음으로 넘어가기를 되풀이해 닿는다'는 관계를 순수한 논리의 말로 정의했고, 1884년 『산술의 기초⁠(basics)⁠』에서는 자연수를 '0에서 이렇게 닿는 수'로 정의했습니다. 그러면 귀납법은 따로 믿어야 할 원리가 아니라 정의에서 따라 나오는 정리가 됩니다. 수학을 논리 위에 세우려는 이 입장을 논리주의⁠(logicism)⁠라고 합니다. 파리의 앙리 푸앵카레는 1902년 『과학과 가설』에서 반대했습니다. 귀납법은 무한히 많은 경우를 한꺼번에 확신하게 해 주는데, 그 확신은 논리의 규칙에서 나오지 않고 '한 번 할 수 있는 일은 끝없이 되풀이할 수 있다'는 것을 아는 정신의 힘에서 나온다는 것입니다. 그는 칸트의 말을 빌려 귀납법을 '선험적 종합 판단⁠(synthetic a priori judgment)⁠', 곧 경험에 앞서 확실히 알면서도 정의를 풀어 쓰는 것 이상의 새 내용을 주는 판단의 본보기라고 불렀습니다. 다만 수학적 귀납법이 과학의 귀납과 달리 개연성이 아니라 확실성을 준다는 데에는, 드모르간처럼 두 사람 모두 의심이 없었습니다. 다툼은 그 확실성이 논리에서 오느냐 직관에서 오느냐였습니다. 이 다툼은 20세기 초의 수학 기초론 논쟁⁠(debate on the foundations of mathematics)⁠으로 이어지고, 프레게의 체계가 러셀의 역설⁠(Russell's paradox)⁠에 부딪힌 이야기는 「틀린 증명이 만든 수학」 6절에 있습니다.

5 · 편지 한 통과 다항식오일러의 생성함수

1740년 가을, 베를린의 수학자 필리프 나우데가 상트페테르부르크의 오일러에게 편지를 보냈습니다. 50을 서로 다른 자연수 일곱 개의 합으로 쓰는 방법은 몇 가지인가? 순서만 다른 것은 같은 것으로 칩니다. 일곱 개를 늘어놓는 방법을 모두 적어 보는 것은 끔찍한 일입니다. 오일러는 몇 달 뒤인 1741년 4월 페테르부르크 아카데미에서 답을 발표했습니다. 522가지입니다. 그해 여름 오일러는 프로이센 왕 프리드리히 2세의 초청을 받아 베를린으로 옮겨 가 25년을 머뭅니다.

이 절의 물음은 이것입니다. 어떤 수를 정해진 조각들의 합으로 쓰는 방법은 몇 가지일까? 작은 예로 5를 서로 다른 자연수의 합으로 쓰면 5, 4 + 1, 3 + 2의 3가지입니다(순서만 바꾼 1 + 4는 4 + 1과 같은 것으로 칩니다). 이런 목록은 수가 조금만 커져도 손으로 적을 수 없게 됩니다. 오일러는 목록 대신 곱셈을 했습니다.

오일러의 요령은 세기를 곱셈으로 바꾸는 것이었습니다. 출발점은 거듭제곱의 곱셈 규칙입니다. $x^2$('x의 제곱', x를 두 번 곱한 것)에 $x^5$를 곱하면 x를 모두 일곱 번 곱한 것이니 $x^2 \cdot x^5 = x^7$, 곧 곱하면 지수(오른쪽 위의 작은 수)가 더해집니다. 이 규칙을 쓰면 '조각을 더한다'를 'x의 거듭제곱을 곱한다'로 바꿀 수 있습니다.

그래서 조각 1을 쓸지 말지를 $(1 + x)$로, 조각 2를 쓸지 말지를 $(1 + x^2)$로, … 적고 모두 곱합니다. 괄호마다 1은 '그 조각을 쓰지 않음'($x^0 = 1$이니 합에 0을 보탬), $x^j$는 '조각 $j$를 씀'입니다. 괄호들을 곱해 전개하면, 항 하나는 괄호마다 둘 중 하나를 골라 곱한 것입니다. 그러니 항 하나하나가 조각을 고르는 방법 하나이고, 그 지수는 고른 조각의 합입니다. 같은 지수의 항들을 모으면, 합이 $n$이 되는 방법의 수가 $x^n$의 계수, 곧 $x^n$ 앞에 곱해진 수로 모입니다.

조각 1, 2, 3만으로 해 봅시다. 먼저 두 괄호를 곱하면 $(1+x)(1+x^2) = 1 + x + x^2 + x^3$입니다. 여기에 $(1+x^3)$을 곱하면, 앞의 네 항에 1을 곱한 것과 $x^3$을 곱한 것을 더해 $1 + x + x^2 + x^3 + x^3 + x^4 + x^5 + x^6$이 되고, 같은 항을 모으면

입니다. $x^3$의 계수 2는 3을 만드는 두 방법 '3'과 '1 + 2'를 센 것입니다. 앞의 두 $x^3$ 가운데 하나는 첫 두 괄호에서 $x$와 $x^2$를 고른 것(1 + 2)이고, 다른 하나는 셋째 괄호에서 $x^3$을 고른 것(3)입니다. 세고 싶은 수열을 다항식⁠(polynomial)⁠이나 무한히 이어지는 급수(항이 끝없이 이어지는 합)의 계수로 담아 두는 이 방법을 생성함수라고 합니다. 수열을 하나하나 다루는 대신, 수열 전체를 식 하나로 묶어 계산하는 것입니다.

조각을 여러 번 써도 된다면 조각 $j$의 인수는 $1 + x^j + x^{2j} + \cdots$, 곧 $j$를 0번, 1번, 2번, … 쓰는 경우의 합입니다. 이런 끝없는 합은 짧게 적을 수 있습니다. $y = x^j$라 두면 $(1 - y)(1 + y + y^2 + \cdots)$에서 $y$, $y^2$, …이 차례로 지워져 1만 남으므로, $1 + y + y^2 + \cdots = \frac{1}{1-y}$입니다. 이것이 등비급수⁠(geometric series)⁠이고, 조각 $j$의 인수는 $\frac{1}{1 - x^j}$로 적을 수 있습니다.

이 식에 실제 수 $x$를 넣으려면 합이 한 값으로 모여야(수렴⁠(convergence)⁠해야) 하고, 그것은 $|x| \lt 1$($x$가 −1과 1 사이)일 때입니다. 그러나 계수만 읽을 때는 수렴을 따지지 않아도 됩니다. $x$에 수를 넣지 않고 '계수를 담은 형식적인 식'으로 다루면, 위에서 항들이 차례로 지워진 계산은 계수끼리의 계산으로 그대로 성립합니다.

조각 1, 2, 3, …의 인수를 모두 곱하면 자연수 $n$을 순서를 무시하고 자연수의 합으로 쓰는 방법의 수가 계수로 나옵니다. 이 수를 분할수⁠(partition number)⁠라 하고 $p(n)$으로 적습니다. 예를 들어 4는 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1로 쓸 수 있으니 $p(4) = 5$입니다. 세는 대상을 에서 고르고, 인수를 하나씩 곱해 보세요. 처음으로 다음 인수 곱하기 모두 곱하기 아래 식은 지금까지 곱한 인수들과 그 전개이고, 노랗게 칠한 항이 만들려는 수 $n$의 항입니다. 왼쪽 막대는 계수, 오른쪽은 그 계수가 센 방법들을 하나씩 그린 것입니다.

만들려는 수 n = 에서, 인수 개를 곱한 지금 계수는 이고 모든 인수를 곱하면 입니다. 인수 하나를 곱하는 일은 '새 조각을 써도 된다'는 허락이고, 계수는 그 허락이 늘 때마다 오른쪽 그림에 새로 불이 들어오는 도형의 수만큼 자랍니다.

'1·2·5원 동전'을 고르면 거스름돈 문제, 곧 몇 원을 1원·2원·5원 동전으로 내는 방법의 수가 됩니다. 인수 세 개를 곱하는 계산을 들여다보면, 컴퓨터가 이 문제를 푸는 방법과 똑같습니다. 1원과 2원만으로 금액마다 내는 방법의 수를 표에 적어 두었다고 합시다. 여기에 $\frac{1}{1-x^5}$을 곱하는 것은 '5원짜리도 써도 된다'는 허락이고, 계산으로는 금액 $n$의 새 값을 '$n$의 옛 값 + $n-5$의 새 값'으로 고쳐 쓰는 것입니다(5원을 쓰지 않는 방법과, 5원 하나를 먼저 내고 남은 금액을 내는 방법). 작은 금액의 답을 표에 적어 두고 동전을 하나씩 추가하며 표를 고쳐 쓰는 것입니다. 이 방법을 동적 계획법⁠(dynamic programming)⁠이라고 부릅니다. 오일러의 곱셈은 200년 뒤의 알고리즘을 미리 쓴 셈입니다. '동적 계획법'이라는 이름은 1950년대 RAND 연구소의 수학자 리처드 벨먼이 붙였습니다. 같은 표 채우기가 '더하기'와 '곱하기'의 뜻만 바꾸면 경우의 수⁠(number of cases)⁠ 대신 가장 싼 길이나 가장 그럴듯한 해석을 계산한다는 이야기는 「같은 계산, 다른 덧셈」에 있습니다.

'사탕을 세 아이에게'는 똑같은 사탕 $n$개를 세 아이에게 나누는 방법입니다(한 개도 못 받는 아이가 있어도 됩니다). 아이 한 명의 몫은 0개, 1개, 2개, …이니 인수가 $1 + x + x^2 + \cdots = \frac{1}{1-x}$이고, 세 명이니 생성함수는 $\frac{1}{(1-x)^3}$입니다. 목록 없이 답을 얻는 길은 그림에 있습니다. 그림처럼 사탕 $n$개와 칸막이 2개를 한 줄에 늘어놓는 방법으로 생각하면 $n+2$자리 가운데 칸막이 자리 2곳을 고르는 문제가 됩니다. 첫 칸막이 앞의 ★이 첫째 아이, 두 칸막이 사이의 ★이 둘째 아이, 둘째 칸막이 뒤의 ★이 셋째 아이 몫입니다. 사탕 2개면 ★★||, |★★|, ||★★, ★|★|, ★||★, |★|★의 $\binom{4}{2} = 6$가지입니다. 일반적으로 $k$명에게 나누는 방법은 $\binom{n+k-1}{k-1}$가지입니다. 이 그림을 별과 막대⁠(stars and bars)⁠라고 부르며, 1950년 크로아티아 출신의 미국 확률론자 윌리엄 펠러의 교과서가 이 이름을 널리 퍼뜨렸습니다.

생성함수는 점화식과도 잘 맞습니다. 3절의 박자 무늬 수를 계수로 담은 식 $M_0 + M_1 x + M_2 x^2 + M_3 x^3 + \cdots = 1 + x + 2x^2 + 3x^3 + \cdots$을 $M(x)$라 합시다. 무늬는 빈 무늬이거나, 더 짧은 무늬 뒤에 한 박짜리 음절($x$) 또는 두 박짜리 음절($x^2$)을 붙인 것입니다. 이 말을 그대로 식으로 옮기면 $M(x) = 1 + (x + x^2)M(x)$이고, $M(x)$에 대해 풀면 $M(x)(1 - x - x^2) = 1$이므로

$\sum M_m x^m = \frac{1}{1 - x - x^2}$입니다. 왼쪽의 Σ('시그마')는 $m = 0, 1, 2, \ldots$의 항 $M_m x^m$을 모두 더하라는 기호입니다. 분모의 $x + x^2$가 바로 '한 박짜리 음절 또는 두 박짜리 음절'이라는 선택이고, 식 $M(x) = 1 + (x + x^2)M(x)$에서 $x^m$의 계수를 비교하면 3절의 점화식 $M_m = M_{m-1} + M_{m-2}$이 다시 나옵니다.

생성함수를 오일러가 처음 쓴 것은 아닙니다. 10년쯤 앞서 런던의 드무아브르는 피보나치 수열처럼 점화식을 따르는 수열을 방금처럼 분수식 하나로 묶는 '순환 급수⁠(recurrent series)⁠'를 다루었습니다. 오일러는 이 도구를 수의 분할에 들고 가서 『무한 해석 입문』(1748)의 한 장을 채웠고, 1750년 무렵에는 오각수 정리⁠(pentagonal number theorem)⁠라는 항등식을 증명했습니다. 곱 $(1-x)(1-x^2)(1-x^3)\cdots$을 끝없이 전개하면 항들이 서로 지워져 계수가 대부분 0이 되고

만 남는다는 정리입니다. 앞의 몇 항은 손으로 확인할 수 있습니다. $(1-x)(1-x^2) = 1 - x - x^2 + x^3$인데, 여기에 $(1-x^3)$을 곱하면 $x^3$의 계수가 $1 - 1 = 0$으로 지워집니다. 살아남는 지수 1, 2, 5, 7, 12, 15, …는 $k(3k-1)/2$에 $k = 1, -1, 2, -2, 3, -3, \ldots$을 넣은 수이고(이 가운데 1, 5, 12, 22는 점을 오각형 모양으로 쌓을 때의 점의 수인 오각수입니다), 계수는 부호가 두 개씩 번갈아 바뀌는 ±1입니다. 오일러의 '곱셈으로 세기'는 모든 자연수가 소수⁠(prime number)⁠의 곱으로 한 가지로만 쓰인다는 사실을 무한곱⁠(infinite product)⁠으로 적은 오일러의 곱 공식과 같은 발상입니다(「소수를 세는 사람들」 3절). 그 공식에서는 소수마다 '이 소수를 몇 번 곱할지'를 인수 하나로 적어 모두 곱하고, 전개하면 모든 자연수가 정확히 한 번씩 나옵니다.

'생성함수'(프랑스어로 fonction génératrice)라는 이름은 라플라스가 붙였습니다. 그는 1812년 『확률의 해석적 이론』에서 이 도구로 확률 계산에 나오는 점화식들을 풀었습니다.

분할수도 빠르게 자랍니다. $p(10) = 42$, $p(100) = 190{,}569{,}292$입니다. 20세기 초 영국의 군인 출신 수학자 퍼시 맥마흔은 손으로 $p(200) = 3{,}972{,}999{,}029{,}388$까지 계산했습니다. 1918년 케임브리지의 G. H. 하디와 라마누잔은 $p(n)$의 크기를 거의 정확히 주는 공식을 내놓아 맥마흔의 표와 맞추어 보았습니다. 그 공식의 첫 항만 보아도, $n$이 클 때 $p(n)$과 $\frac{1}{4\sqrt3\,n}e^{\pi\sqrt{2n/3}}$의 비는 1에 다가갑니다. 이 식은 'e(약 2.718인 수)의 $\pi\sqrt{2n/3}$제곱을 $4\sqrt3\,n$으로 나눈 값'이라고 읽습니다. $n$의 제곱근이 지수에 있으니, 2배씩 자라는 하노이의 탑보다는 느리지만 어떤 다항식보다도 빨리 자랍니다. 비가 1에 다가간다는 것은 차이가 작아진다는 뜻이 아니라 상대 오차(차이를 참값으로 나눈 비율)가 작아진다는 뜻입니다. $\sqrt n$에 비례하는 개수의 항을 더하면, $n$이 충분히 클 때 오차가 0.5보다 작아져 반올림만으로 정확한 값이 나옵니다. 다만 이 급수⁠(series)⁠는 항을 끝없이 더하면 오히려 수렴하지 않습니다. 독일에서 미국으로 옮겨 간 수학자 한스 라데마허는 1937년 이 공식을 손질해, 끝없이 더하면 정확히 $p(n)$으로 수렴하는 급수로 바꾸었습니다.

분할수에는 크기 말고 다른 비밀도 있습니다. 라마누잔은 세상을 떠나기 한 해 전인 1919년에, $p(4), p(9), p(14), \ldots$처럼 5로 나눈 나머지⁠(remainder)⁠가 4인 곳의 분할수가 모두 5의 배수⁠(multiple)⁠라는 것을 증명했습니다. 오일러의 곱셈 기호 안에 이런 정수론⁠(number theory)⁠이 숨어 있었던 것입니다.

6 · 괄호, 산길, 삼각형카탈랑 수⁠(Catalan number)⁠의 여러 얼굴

이 절의 물음은 이것입니다. 겉보기에 아무 관계도 없는 세 가지 목록, 괄호의 짝, 산길, 다각형 자르기가 왜 똑같은 길이일까? 그리고 그 길이를 목록 없이 어떻게 구할까?

1751년 베를린의 오일러는 수학자 크리스티안 골드바흐에게 편지를 썼습니다. 볼록한(안으로 움푹 들어간 곳이 없는) $n$각형을 서로 만나지 않는 대각선으로 삼각형들로 나누는 방법은 몇 가지일까요? 사각형은 대각선 두 개 가운데 하나를 고르니 2가지, 오각형은 5가지, 육각형은 14가지입니다. 오일러는 수열 1, 2, 5, 14, 42, 132, 429, …를 계산하고 그 일반항의 공식을 짐작해 적었지만 증명하지는 못했습니다. 1758년 할레의 수학자 요한 안드레아스 폰 제그너가 큰 다각형의 답을 작은 다각형들의 답으로 짓는 점화식을 찾았고, 1838년 파리의 수학자 외젠 카탈랑은 곱셈의 순서를 괄호로 정하는 방법의 수가 같은 수열이라는 것을 보였습니다. 이 수열은 뒤에 카탈랑 수라는 이름을 얻었습니다.

카탈랑 수가 특별한 까닭은 서로 전혀 달라 보이는 대상들을 똑같이 센다는 데 있습니다. 괄호 $n$쌍을 짝이 맞게 늘어놓는 방법, 오르막과 내리막 $n$번씩으로 된 산길 가운데 땅 밑으로 내려가지 않는 것, $n+2$각형의 삼각형 분할이 모두 같은 수입니다.

세 쌍으로 확인해 봅시다. 괄호 세 쌍을 짝이 맞게 늘어놓는 방법은 ((())), (()()), (())(), ()(()), ()()()의 5가지입니다. ())(()처럼 중간에 닫는 괄호가 먼저 넘치면 짝이 맞지 않습니다. 오각형($n + 2 = 5$)을 대각선으로 삼각형들로 자르는 방법도, 앞에서 본 대로 5가지입니다. 이 수들을 $C_n$으로 적습니다($C_0 = 1$, $C_1 = 1$, $C_2 = 2$, $C_3 = 5$, $C_4 = 14$, …). 아래 그림에서 같은 대상을 세 가지로 그린 것을 차례로 넘겨 보며, 괄호 한 쌍이 산길과 다각형의 어디에 해당하는지 색으로 짝지어 보세요. 쌍의 수 n = 에서 번호 의 대상을 보세요(번호는 0부터 매깁니다). 다음 ▶ ▶ 모두 훑기

대상은 모두 가지이고, 지금 보는 대상()을 괄호로 쓰면 입니다. 여는 괄호를 오르막으로, 닫는 괄호를 내리막으로 읽으면 산길이 됩니다. 괄호의 짝이 맞는다는 것은 어느 순간에도 닫는 괄호가 여는 괄호보다 많지 않다는 것, 곧 산길이 땅 밑으로 내려가지 않는다는 것입니다. 삼각형 분할과의 대응은 이렇습니다. 맨 앞의 괄호 쌍은 밑변 위에 선 삼각형이 되고, 그 괄호 안에 든 것은 삼각형 왼쪽의 작은 다각형을, 괄호 뒤에 오는 것은 오른쪽의 작은 다각형을 같은 규칙으로 채웁니다. 규칙을 거꾸로 따라가면 분할에서 괄호를 되찾을 수 있으니, 이 대응은 두 목록을 빠짐없이, 겹침 없이 하나씩 짝짓습니다. 그래서 두 목록의 길이가 같습니다.

이 규칙이 그대로 점화식입니다. 짝이 맞는 괄호 문자열은 맨 앞의 여는 괄호와 그 짝인 닫는 괄호로 '(안쪽) 뒷부분'처럼 쪼개집니다. 예를 들어 (())()는 안쪽이 (), 뒷부분이 ()입니다. 모두 $n$쌍이고 안쪽이 $i$쌍이면, 맨 앞 쌍을 빼고 남은 뒷부분은 $n-1-i$쌍입니다. 안쪽과 뒷부분은 각각 아무 짝 맞는 문자열이나 될 수 있으니, 안쪽이 $i$쌍인 경우는 곱의 법칙으로 $C_i \times C_{n-1-i}$가지입니다. $i = 0, 1, \ldots, n-1$의 경우는 서로 겹치지 않으니 합의 법칙으로 모두 더합니다. 세 쌍이면 $C_3 = C_0C_2 + C_1C_1 + C_2C_0 = 2 + 1 + 2 = 5$입니다. 일반적으로 적으면 왼쪽 식이고(Σ는 $i = 0$부터 $n-1$까지 더하라는 뜻), 오른쪽은 한 번에 구하는 공식입니다.

두 번째 공식은 산길을 세는 영리한 방법에서 나옵니다. 오르막 $n$번과 내리막 $n$번을 늘어놓는 방법은 모두 $\binom{2n}{n}$가지인데, 땅 밑으로 내려가는 '나쁜' 길은 처음 땅 밑으로 내려간 뒤의 부분을 위아래로 뒤집으면 오르막 $n-1$번, 내리막 $n+1$번짜리 길과 하나씩 짝지어집니다. 그러니 좋은 길은 $\binom{2n}{n} - \binom{2n}{n+1}$가지이고, 계산하면 위의 공식이 됩니다. 세 쌍이면 $\binom{6}{3} - \binom{6}{4} = 20 - 15 = 5$이고, 공식으로도 $\frac{1}{4} \times 20 = 5$입니다.

이 '뒤집기'는 19세기에 투표 문제⁠(ballot problem)⁠를 풀면서 다듬어졌습니다. 두 후보의 표를 세어 나가는 동안 한 후보가 끝까지 앞서 있을 확률을 묻는 문제입니다. 동전 던지기로 오르내리는 무작위 행보⁠(random walk)⁠가 원점 아래로 내려가지 않을 확률도 같은 셈입니다.

세 얼굴 말고도 얼굴은 많습니다. 곱셈 $a \times b \times c \times d$의 계산 순서를 정하는 방법, 가지가 둘씩 갈라지는 트리⁠(tree)⁠의 모양, 원 위의 점 $2n$개를 서로 엇갈리지 않는 줄로 짝짓는 방법도 모두 카탈랑 수입니다. 예를 들어 네 수의 곱셈 순서는 $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$, $a(b(cd))$의 5가지로, 곱셈 세 번의 순서를 괄호 세 쌍으로 적은 것이니 $C_3$입니다.

이 다섯 가지 괄호 방식은 수학의 뜻밖의 곳에서 다시 나옵니다. 보통의 곱셈은 결합법칙⁠(associativity)⁠ 덕분에 괄호를 어떻게 치든 값이 같습니다. 그러나 벡터 공간(화살표처럼 더하고 늘일 수 있는 것들의 모임)을 곱하는 텐서곱(기호 ⊗, '텐서⁠(tensor)⁠'라 읽습니다)에서는 $(a \otimes b) \otimes c$와 $a \otimes (b \otimes c)$가 글자 그대로 '같은' 것이 아니라, 정보를 잃지 않고 서로 옮겨 적을 수 있는 관계(동형⁠, isomorphism⁠)로만 이어집니다. 그런 곳에서는 한 괄호 방식에서 다른 방식으로 옮겨 적는 여러 길이 모두 같은 결과를 주는지 따져야 합니다. 1963년 매클레인은 네 대상의 괄호 방식 다섯 개가 이루는 오각형 하나(와 단위에 관한 삼각형 하나)만 맞으면 된다는 것을 보였고, 이것이 모노이드⁠(monoid)⁠ 범주⁠(category)⁠의 출발점입니다.

컴퓨터가 문맥 자유 문법(문장을 더 작은 덩어리로 나누어 가는 규칙들)으로 문장을 분석할 때 뜻이 여러 갈래로 갈리는 중의성⁠(ambiguity)⁠이 폭발적으로 늘어나는 까닭도 여기에 있습니다. 문장의 구조를 괄호로 묶는 방법이 카탈랑 수만큼 있기 때문입니다(「말을 세는 기계」). 2015년 MIT의 조합론 학자 리처드 스탠리는 카탈랑 수로 세어지는 대상 214가지를 모아 책 한 권을 냈습니다.

정리하면, 서로 다른 목록의 길이가 같다는 것을 보이는 가장 좋은 방법은 두 목록을 빠짐없이, 겹침 없이 하나씩 짝짓는 것, 곧 전단사⁠(bijective)⁠를 찾는 것입니다. 괄호와 산길과 삼각형 분할이 그렇게 짝지어졌습니다. 칸토어가 무한집합의 크기를 잰 방법도 이것이었습니다(「무한에도 크기가 있다」).

이 수열은 사실 유럽보다 먼저 청나라의 궁정에 나타났습니다. 내몽골 출신의 천문학자 밍안투는 천문과 역법을 맡은 관청인 베이징의 흠천감에서 일하며 1730년대 무렵부터 원의 호와 현을 연구했습니다. 호는 원 둘레의 한 조각이고, 현은 그 호의 두 끝을 잇는 선분입니다. 호를 몇 배로 늘렸을 때 그 현의 길이를 처음 호의 현 길이의 무한급수⁠(infinite series)⁠로 나타내는 연구였는데, 그 계수에 1, 2, 5, 14, 42, …가 들어 있습니다. 그의 책은 제자가 마무리해 1839년에야 나왔고, 그 계수가 카탈랑 수라는 것은 1988년에 와서야 중국의 수학사가가 알아보았습니다.

7 · 아무도 제자리에 없을 확률교란순열⁠(derangement)⁠과 포함배제

1708년 샹파뉴의 성에서 지내던 귀족 레몽 드 몽모르는 『우연의 게임 분석』이라는 책을 냈습니다. 여기에 '트레즈'(13)라는 카드 게임이 나옵니다. 대략 이런 게임입니다. 1부터 13까지 적힌 카드를 섞은 뒤 한 장씩 뒤집으며 "하나, 둘, 셋, …" 하고 부르다가, 부른 수와 카드의 수가 한 번이라도 맞으면 카드를 돌리는 쪽이 이깁니다. 한 번도 맞지 않을 확률은 얼마일까요? 몽모르는 스위스의 수학자 니콜라우스 베르누이(야코프 베르누이의 조카)와 편지를 주고받으며 이 문제를 풀었고, 오늘날 이것을 '만남의 문제⁠(problème des rencontres)⁠'라고 부릅니다.

현대판은 이렇습니다. 명이 모자를 맡겼는데 직원이 모자를 아무렇게나 돌려주었습니다. 곧 돌려주는 방법 하나하나가 모두 똑같은 확률로 일어납니다. 아무도 자기 모자를 받지 못할 확률은? 이 절의 물음이 이것이고, 답은 사람 수가 늘어도 0으로 줄어들지 않고 한 값에 머뭅니다.

세 명(1, 2, 3번)으로 먼저 셉시다. 모자를 돌려주는 방법은 $3! = 6$가지입니다. 1번 사람이 받은 모자, 2번이 받은 모자, 3번이 받은 모자를 차례로 적으면 123, 132, 213, 321, 231, 312입니다. 이 가운데 아무도 자기 모자를 받지 못한 것은 231과 312 둘뿐입니다(231은 1번이 2번 모자, 2번이 3번 모자, 3번이 1번 모자를 받은 경우). 그러니 확률은 2/6 = 1/3입니다. 이렇게 아무것도 제자리에 있지 않은 순열을 교란순열이라고 부르고, $n$명의 교란순열의 수를 $D_n$으로 적습니다($D_3 = 2$).

사람이 많아지면 확률은 어떻게 될까요? 한 사람이 자기 모자를 받을 확률 $1/n$은 작아지지만, 받을 기회가 있는 사람은 많아집니다. 어느 쪽이 이길지 짐작하기 어려우니 먼저 직접 섞어 봅시다. 왼쪽 그림에서 빨간 선(자기 모자를 받은 사람)이 하나도 없는 경우가 얼마나 자주 나오는지, 오른쪽 그림에서 노란 점이 어디로 모이는지 보세요. 한 번 섞기 ▶ 500번 섞기 처음부터

지금까지 번 섞어 아무도 자기 모자를 받지 못한 경우가 번, 비율은 입니다. 정확한 값은 교란순열 가지를 전체 순열 가지로 나눈 입니다. 섞을수록 실험 비율이 이 값으로 모이는 것은 큰 수의 법칙⁠(law of large numbers)⁠ 덕분이고, 이렇게 무작위 실험으로 값을 어림하는 것을 몬테카를로 방법⁠(Monte Carlo method)⁠이라고 합니다. 큰 수의 법칙은 같은 실험을 서로 영향 없이 많이 되풀이할수록 성공한 비율이 참 확률에 가까워질 가능성이 커진다는 정리입니다. 오른쪽 그림의 분홍 점들을 보면, 사람 수가 늘어도 확률이 0으로 떨어지지 않고 초록 점선 근처에 머뭅니다.

정확한 값은 어떻게 셀까요? 교란순열을 직접 세기는 어렵습니다. 반대로 '1번이 제자리에 있는 순열'은 쉽습니다. 1번을 고정하고 나머지를 늘어놓으면 $(n-1)!$가지입니다. 그래서 전체에서 '누군가 제자리에 있는 순열'을 빼기로 합니다.

세 명으로 해 봅시다. 전체 6가지에서 1번이 제자리인 것(2가지), 2번이 제자리인 것(2가지), 3번이 제자리인 것(2가지)을 빼면 6 − 6 = 0이 되어 너무 많이 뺐습니다. 모두 제자리인 123은 세 번이나 빠졌기 때문입니다. 그래서 두 명이 제자리인 경우를 다시 더합니다. 1·2번, 1·3번, 2·3번이 제자리인 순열은 각각 1가지(나머지 한 명도 제자리)이니 3을 더합니다. 그러면 123은 한 번 세고 세 번 빼고 세 번 더해져 한 번 센 셈이 되니, 세 명 모두 제자리인 1가지를 다시 뺍니다. 결과는 6 − 6 + 3 − 1 = 2로, 손으로 센 $D_3 = 2$와 같습니다.

이렇게 넘치게 빼고 다시 더하기를 번갈아 하는 방법이 포함배제 원리⁠(inclusion–exclusion principle)⁠입니다. 일반적으로 '고른 $k$명이 제자리인 순열'은 $n$명 가운데 $k$명을 고르는 방법 $\binom{n}{k}$가지마다 나머지 $n-k$명을 늘어놓는 방법이 $(n-k)!$가지입니다. 이것을 $k$가 짝수이면 더하고 홀수이면 빼서(그것이 $(-1)^k$의 역할입니다) $k = 0$부터 $n$까지 모읍니다. 두 번째 등식은 $\binom{n}{k}(n-k)! = \frac{n!}{k!\,(n-k)!}(n-k)! = \frac{n!}{k!}$에서 나옵니다.

양변을 $n!$로 나누면 확률 $D_n/n!$이 나옵니다. 위의 두 번째 식이 지금 고른 사람 수로 그 합을 적은 것입니다. 이 합은 $1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \cdots$처럼 부호가 번갈아 바뀌고 항이 빠르게 작아집니다.

이 합이 어디로 가는지는 수 $e \approx 2.71828$(자연로그⁠(natural logarithm)⁠의 밑)이 알려 줍니다. $e^x$는 끝없는 합 $e^x = 1 + x + \frac{x^2}{2!} + \cdots$(테일러 급수⁠, Taylor series⁠)로 쓸 수 있고, 여기에 $x = -1$을 넣으면 $e^{-1} = 1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots$입니다. 확률의 합은 바로 이 급수를 $k = n$에서 끊은 앞부분입니다. 그래서 사람이 많아지면 확률은 $1/e \approx 0.3679$로 다가갑니다. 급수의 항이 워낙 빨리 작아져서, $n$명일 때 1/e와의 차이는 $1/(n+1)!$보다 작습니다. 부호가 번갈아 바뀌고 크기가 줄어드는 급수에서는, 도중에 끊었을 때의 오차가 버린 첫 항보다 작기 때문입니다. 일곱 명 이상이면 반올림한 소수 넷째 자리까지 같습니다. 모자를 맡긴 사람이 열 명이든 백만 명이든 아무도 제 모자를 받지 못할 확률은 거의 37%이고, 적어도 한 명은 받을 확률은 거의 $1 - 1/e \approx 63\%$입니다. 몽모르의 게임에서 카드를 돌리는 쪽이 유리했던 까닭입니다. 흔히 '사람이 많을수록 누군가 자기 모자를 받을 확률은 1에 가까워진다'고, 또는 반대로 '0에 가까워진다'고 짐작하지만, 두 효과가 거의 정확히 맞서서 확률은 어느 쪽으로도 가지 않습니다.

이번에는 제자리에 있는 사람이 평균⁠(mean)⁠ 몇 명인지 봅시다. 같은 실험을 아주 많이 되풀이할 때 얻는 평균을 기댓값⁠(expected value)⁠이라 합니다. 세 명이면 여섯 순열에서 제자리인 사람 수가 123은 3명, 132·213·321은 1명씩, 231·312는 0명이니 평균은 (3 + 1 + 1 + 1 + 0 + 0) ÷ 6 = 1명입니다. 이 기댓값은 사람 수와 상관없이 정확히 1명입니다. 한 사람이 자기 모자를 받을 확률은 $1/n$이고, 각 사람이 평균 $1/n$명씩 보태는 셈이니 $n$명이면 $n \times 1/n = 1$입니다. 한 사람이 자기 모자를 받으면 다른 사람의 확률이 달라지듯 사람들의 사건⁠(event)⁠이 서로 얽혀 있어도, 기댓값은 그냥 더하면 됩니다(기댓값의 선형성). 연말에 이름 쪽지를 섞어 뽑는 마니또 놀이에서 누군가 자기 이름을 뽑아 다시 뽑아야 할 확률도 63% 안팎입니다. 세기와 확률은 이렇게 같은 동전의 양면입니다. 모든 경우가 똑같이 일어날 법할 때 확률은 '좋은 경우의 수 ÷ 모든 경우의 수'이고, 그 분자와 분모를 목록 없이 구하는 기술이 조합론입니다.

포함배제는 오랫동안 문제마다 새로 꺼내 쓰는 요령이었습니다. 1964년, 당시 MIT에 있던 잔카를로 로타는 논문 「조합 이론의 기초에 관하여 I」에서 이렇게 보였습니다. 대상들이 '포함된다' 같은 순서로 짜여 있으면 그 순서마다 뫼비우스 함수⁠(Möbius function)⁠라는 것이 있고(포함배제에서 번갈아 붙이던 +1과 −1을 일반적인 순서 구조로 넓힌 부호표라고 생각하면 됩니다), 교란순열의 포함배제도, 정수론의 뫼비우스 반전(약수⁠(divisor)⁠들에 걸쳐 더한 합에서 원래 값을 되찾는 공식)도, 그래프를 색칠하는 방법의 수도 모두 그 함수⁠(function)⁠ 하나로 계산됩니다. 순서 구조 위의 이 함수를 1930년대에 먼저 다룬 사람 가운데 하나가, 「짝을 찾는 알고리즘」의 결혼 정리로 이름을 남긴 필립 홀입니다. 1966년 로타가 프랭크 해러리와 함께 『조합 이론 저널』을 창간할 무렵, 흔히 요령 모음쯤으로 여겨지던 조합론은 독립⁠(independence)⁠된 분야로 자리를 잡아 가고 있었습니다.

8 · 수학 밖으로빛 알갱이, 유전 부호, 장교와 방진

이 절에서는 앞에서 만든 도구들이 수학 밖에서 무엇을 정했는지 봅니다. 물리학에서는 '무엇을 같은 것으로 볼까'가, 생물학과 암호에서는 곱의 법칙이, 컴퓨터 과학에서는 '가능성이 몇 가지인가'가 답을 정합니다.

1924년 영국령 인도의 다카 대학에 있던 물리학자 사티엔드라 나트 보스는 짧은 논문을 베를린의 아인슈타인에게 보냈습니다. 빛 알갱이(광자)를 에너지 상자들에 나누어 담는 방법을 셀 때, 알갱이들을 서로 구별하지 않고 상자마다 몇 개씩 들었는지만 세면 플랑크의 복사 법칙⁠(Planck's law)⁠이 곧바로 나온다는 내용이었습니다. 플랑크의 복사 법칙은 1900년 독일의 물리학자 막스 플랑크가 찾은 공식으로, 뜨거운 물체가 내는 빛의 세기가 색(파장)마다 어떻게 나뉘는지를 알려 줍니다. 아인슈타인은 논문을 직접 독일어로 옮겨 학술지에 실어 주었습니다. 나아가 같은 셈을 원자 기체에 적용해, 아주 낮은 온도에서 수많은 원자가 한꺼번에 가장 낮은 에너지 상태로 모여 하나의 덩어리처럼 움직이는 현상을 예측했습니다. 이것이 뒤에 '보스–아인슈타인 응축⁠(Bose–Einstein condensate)⁠'이라 불리는 현상입니다. 보스의 셈은 5절의 별과 막대 그대로입니다. 알갱이가 사탕, 에너지 상자가 아이이고, 알갱이 $n$개를 상자 $k$개에 담는 방법은 $\binom{n+k-1}{k-1}$가지입니다.

작은 예로 보면 차이가 분명합니다. 알갱이 두 개를 상자 두 개에 넣는 방법은, 알갱이에 이름표가 있다면 곱의 법칙으로 $2 \times 2 = 4$가지입니다. 19세기에 맥스웰과 오스트리아의 물리학자 루트비히 볼츠만이 기체를 다룰 때 쓴 고전적인 셈으로, 맥스웰–볼츠만의 셈이라고 부릅니다. 이름표가 없으면 '둘 다 왼쪽, 하나씩, 둘 다 오른쪽'의 3가지입니다(보스–아인슈타인). 별과 막대로는 $\binom{3}{1} = 3$입니다. 이름표가 있을 때의 '알갱이 가가 왼쪽, 나가 오른쪽'과 '나가 왼쪽, 가가 오른쪽'이 이름표가 없으면 '하나씩' 한 가지로 합쳐지기 때문입니다. 한 상자에 둘이 들어갈 수 없다면 1가지뿐입니다. 전자 같은 입자가 따르는 이 셈은 1926년 이탈리아의 엔리코 페르미와 영국의 폴 디랙이 세워 페르미–디랙의 셈이라 부릅니다. 양자역학에 따르면 자연이 실제로 쓰는 셈은 뒤의 둘뿐입니다. 보스–아인슈타인의 셈을 따르는 입자를 보스의 이름을 따 보손⁠(boson)⁠, 페르미–디랙의 셈을 따르는 입자를 페르미온이라고 부릅니다. 맥스웰–볼츠만의 셈은 입자가 상자에 비해 아주 드물어 한 상자에 둘이 들 일이 거의 없을 때 두 셈이 함께 다가가는 어림입니다. 어느 셈을 따르느냐에 따라 레이저, 초전도(아주 차가운 물질에서 전기 저항이 0이 되는 현상), 별의 구조가 달라집니다. 무엇을 '같은 것'으로 볼지가 세기의 첫 질문이라는 것을 물리학이 보여 준 셈입니다.

생물학에도 비슷한 셈이 있습니다. 1953년 DNA의 이중 나선이 밝혀진 뒤, DNA의 네 가지 글자인 염기(A, C, G, T)로 단백질을 이루는 스무 가지 아미노산을 어떻게 적는지가 문제가 되었습니다. 염기 두 개로 된 낱말은 $4^2 = 16$개뿐이라 모자라고, 세 개면 $4^3 = 64$개로 충분합니다. 그러니 낱말의 길이가 모두 같다면 적어도 세 글자여야 합니다. 이 셈은 1954년 무렵 물리학자 조지 가모프 등의 제안과 함께 흔히 소개됩니다. 실제로 유전 부호가 세 염기씩 읽힌다는 것은 1960년대 초의 실험으로 확인되었습니다. 64개 가운데 61개가 아미노산을 가리키니 한 아미노산을 여러 낱말이 가리키는 일이 흔하고, 나머지 3개는 '멈춤' 신호로 쓰입니다.

화학도 세기를 필요로 했습니다. 19세기 중반 화학자들은 분자식은 같지만 원자들이 이어진 모양이 다른 물질, 곧 이성질체⁠(isomer)⁠를 잇달아 찾아내고 있었습니다. 1874–75년 케임브리지의 아서 케일리는 탄소 원자는 손이 넷, 수소 원자는 손이 하나라는 규칙을 가지가 갈라지는 트리의 모양으로 바꾸어, 탄소 수마다 알케인(탄소와 수소로만 된 사슬 모양 분자, $\mathrm{C}_n\mathrm{H}_{2n+2}$)의 이성질체가 몇 가지인지 셌습니다. 탄소가 많은 경우의 값 몇 개는 틀렸지만, 화학 구조를 그래프로 세는 첫 시도였습니다. 1937년 취리히 연방 공과대학에 있던 헝가리 출신의 수학자 조지 폴리아는, 돌리거나 뒤집으면 같아지는 배치를 한 번만 세는 일반적인 방법을 발표하며 화학 화합물을 대표적인 예로 들었습니다. 무엇을 '같은 것'으로 볼지를 대칭의 군(돌리기, 뒤집기처럼 배치를 제 모양으로 겹쳐 놓는 동작들의 모임)으로 정해 두고 세는 이 방법을 오늘날 폴리아의 세기 정리라 부릅니다. 보스의 빛 알갱이에서처럼 여기서도 첫 질문은 무엇을 같은 것으로 보느냐입니다.

조선에서도 세기의 역사에 남을 결과가 나왔습니다. 숙종 때 여러 차례 영의정을 지낸 최석정은 1700년 무렵의 산학서 『구수략』에 9행 9열의 표 두 장을 겹쳐 놓은 방진을 실었습니다. 각 표에서는 가로줄과 세로줄마다 1부터 9까지가 한 번씩만 나오고(라틴 방진⁠, Latin square⁠), 두 표를 겹치면 81가지 짝이 모두 한 번씩 나옵니다(직교⁠, orthogonality⁠). 3 × 3으로 줄여 보면 이렇습니다. 가로줄이 123, 231, 312인 표와 123, 312, 231인 표는 둘 다 라틴 방진이고, 칸마다 두 수를 겹쳐 적으면 첫 줄은 11, 22, 33, 둘째 줄은 23, 31, 12, 셋째 줄은 32, 13, 21로 아홉 가지 짝이 모두 한 번씩 나옵니다. 1782년 페테르부르크의 오일러는 여섯 연대에서 여섯 계급의 장교를 한 명씩, 가로줄과 세로줄마다 연대와 계급이 겹치지 않게 6 × 6으로 세우는 '36명의 장교 문제⁠(thirty-six officers problem)⁠'를 내고 불가능하다고 추측했습니다. 이 추측은 1900년 프랑스의 아마추어 수학자 가스통 타리가 모든 경우를 따져 확인했습니다. 최석정의 방진은 오일러의 연구보다 반세기 넘게 앞선 직교 라틴 방진⁠(orthogonal Latin squares)⁠으로 오늘날 널리 인정받습니다. 라틴 방진은 1920년대 영국 로담스테드 농업 시험장의 로널드 피셔가 밭을 나누어 비료를 시험하는 실험 설계에 쓰면서 과학의 도구가 되었습니다(「담배와 폐암」).

1500년부터 오늘까지. 잉골슈타트의 인쇄된 삼각형에서 시작해, 파리와 베를린과 페테르부르크의 아카데미 사이를 편지가 오가며 18세기의 조합론이 자랐고, 같은 시기 베이징과 한양에서도 다른 질문에서 같은 수학이 나왔습니다. 20세기에는 마드라스와 다카에서 케임브리지와 베를린으로 간 편지가 분할수와 양자 통계⁠(statistics)⁠를 바꾸었습니다.

계산의 세계에서 세기는 비용표입니다. 영문 대소문자와 숫자 62가지로 된 여덟 자리 비밀번호는 $62^8 \approx 2.2 \times 10^{14}$가지라, 1초에 100억 개를 시험하는 컴퓨터라면 여섯 시간 남짓이면 모두 시험합니다. 자리를 하나 늘릴 때마다 62배씩 늘어나는 곱의 법칙이 암호의 안전을 떠받칩니다(「나머지로 지키는 비밀」).

카드 $n$장을 두 장씩 비교해 줄 세우는 일은, 가능한 순서 $n!$가지 가운데 하나를 예·아니오 질문('이 카드가 저 카드보다 작은가?')으로 가려내는 일입니다. 질문 하나의 두 답 가운데 어느 한쪽은 후보를 적어도 절반 남기니, 운이 나쁘면 적어도 $\log_2 n!$번은 물어야 합니다. 여기서 $\log_2 N$('로그 2의 N')은 '2를 몇 번 곱해야 $N$이 되는가'를 뜻합니다($\log_2 8 = 3$). 같은 말을 뒤집어 하면, 질문 $q$번의 답이 만드는 예·아니오의 줄은 $2^q$가지뿐이니 $2^q$이 $n!$보다 작으면 두 순서가 같은 답을 받아 구별되지 않습니다. 카드 3장이면 $3! = 6$가지 순서를 가려야 하는데, 질문 두 번으로는 답의 줄이 4가지뿐이니 적어도 세 번은 물어야 합니다. 스털링 공식($n!$의 크기를 어림하는 공식)으로 이것은 약 $n \log_2 n - 1.44\,n$이고, $n$이 클수록 $n \log_2 n$과의 비가 1로 다가갑니다(비교 정렬의 하한⁠, comparison sorting lower bound⁠). 어떤 정렬 방법도 넘을 수 없는 이 벽의 이야기는 「줄 세우기의 한계」에 있습니다.

세기는 정보의 단위도 정합니다. 비트는 0 또는 1을 적는 한 자리입니다. 비트 $b$개로는 곱의 법칙으로 $2^b$가지를 구별할 수 있으니, 가능한 메시지가 $N$가지이면 그중 하나를 가리키는 데 $\log_2 N$비트(정수⁠(integer)⁠가 아니면 올림한 수)가 필요합니다. 여덟 음절 운율 256가지 가운데 하나는 $256 = 2^8$이므로 정확히 8비트이고, 핑갈라의 번호 매기기가 바로 그 부호입니다. 메시지들이 고르게 나오지 않을 때 이 셈을 다듬은 것이 섀넌의 정보 엔트로피⁠(information entropy)⁠이고, 압축의 한계를 정합니다(「짧게 보내기」).

세기는 존재를 증명하기도 합니다. 생일이 365일에 고르게 흩어져 있다고 할 때, 23명이 모이면 생일이 같은 두 사람이 있을 확률이 절반을 넘습니다(생일 문제⁠, birthday problem⁠). 23은 365에 비해 작아 보이지만, 겹칠 수 있는 것은 사람이 아니라 두 사람의 쌍이고, 쌍은 $\binom{23}{2} = 253$개나 됩니다. 정확히는 모두의 생일이 다를 확률이 $\frac{365}{365} \times \frac{364}{365} \times \cdots \times \frac{343}{365} \approx 0.493$이라서(둘째 사람은 첫째와 다른 364일, 셋째는 363일, …), 겹칠 확률은 약 0.507입니다. 자료를 칸에 흩어 담는 해시 테이블⁠(hash table)⁠에서 충돌이 생각보다 일찍 생기는 까닭이 이것입니다.

칸보다 물건이 많으면 어느 칸엔가 두 개가 들어간다는 비둘기집 원리⁠(pigeonhole principle)⁠는 가장 단순한 세기이고, 모든 파일을 줄이는 압축기가 없다는 것처럼 무언가가 불가능하다는 것을 보이는 데도 쓰입니다(「불가능의 증명」 6절). 예를 들어 길이가 $n$비트인 파일은 $2^n$가지인데 그보다 짧은 파일은 모두 합해도 $1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$가지뿐이니, 모든 $n$비트 파일을 서로 다른 짧은 파일로 줄일 수는 없습니다.

에르되시는 1947년 세기만으로 존재를 보였습니다. 점 $n$개를 모두 선으로 이은 그림에서 선마다 빨강이나 파랑을 칠한다고 합시다. 한 색의 선으로만 서로 이어진 점 $k$개의 무리가 생기는 칠하기를 '나쁜' 색칠이라 하면, 에르되시는 $k \ge 3$이고 $n$이 $2^{k/2}$보다 작을 때 나쁜 색칠의 수가 전체 색칠의 수보다 적다는 것을 세었습니다. 그러니 나쁘지 않은 색칠이 적어도 하나 있습니다. 그런 색칠을 하나도 그려 보이지 않고 존재를 보인 것입니다(확률적 방법⁠, probabilistic method⁠).

정리하면, 세기는 무언가가 있다는 것(생일이 겹치는 쌍, 나쁘지 않은 색칠)과 없다는 것(모든 파일을 줄이는 압축기)을 둘 다 보여 줍니다. 충분히 큰 구조에는 반드시 질서가 생긴다는 램지 이론⁠(Ramsey theory)⁠과 이 증명법의 이야기는 「완전한 무질서는 없다」로 이어집니다.

9 · 이어지는 길세기가 닿는 곳

목록 없이 세는 요령은 수학과 컴퓨터 과학의 거의 모든 곳에서 다시 나타납니다.

• 확률: 파스칼과 페르마가 판돈을 나눈 방법은 이항계수를 세는 일이었고, 이항계수의 윤곽은 이항분포⁠(binomial distribution)⁠를 거쳐 종 모양 곡선이 됩니다(「도박판에서 온 편지」). 교란순열의 1/e은 확률과 해석학(극한⁠(limit)⁠과 무한급수를 다루는, 미적분⁠(calculus)⁠에서 자란 수학)이 만나는 가장 짧은 다리입니다.
• 알고리즘: 하노이의 탑의 $T_n = 2T_{n-1} + 1$처럼 알고리즘의 비용은 점화식으로 적힙니다. 반으로 나누어 푸는 병합 정렬⁠(merge sort)⁠의 비용 $T_n = 2T_{n/2} + n$이 $n \log_2 n$ 정도가 된다는 계산($n$이 2의 거듭제곱이고 $T_1 = 0$이면 정확히 $n \log_2 n$)이 정렬 알고리즘⁠(sorting algorithm)⁠ 비교의 출발점입니다(「줄 세우기의 한계」).
• 짝짓기: 두 무리를 짝짓는 방법의 수는 계승만큼 많아서 모두 시험할 수 없습니다. 목록을 뒤지지 않고 가장 좋은 짝을 찾는 방법은 「짝을 찾는 알고리즘」에서 이어집니다.
• 그래프: 오일러가 일곱 다리 문제에서 가능한 길을 모두 늘어놓지 않고 땅마다 닿는 다리의 수(꼭짓점⁠(vertex)⁠의 차수)만 센 것도 같은 정신입니다. 1889년 영국의 수학자 아서 케일리는 꼭짓점 $n$개에 이름을 붙인 트리가 $n^{n-2}$개라는 것을 세었습니다(「일곱 다리의 도시」). 같은 공식을 1860년 독일의 보르하르트가 행렬식(수를 정사각형으로 늘어놓은 표에서 정해진 규칙으로 계산하는 수 하나)으로 먼저 증명했습니다. 어떤 그래프든 그 안의 신장 트리(그래프의 점을 모두 잇되 고리가 없는 부분)를 행렬식⁠(determinant)⁠ 하나로 세는 키르히호프의 정리는 「라플라시안, 가장 많이 재사용된 식」 4절에 있습니다.
• 놀이: 돌무더기 놀이 님에서 이기는 규칙은 무더기의 크기를 이진법으로 적고 자리마다 1의 개수의 홀짝을 세는 일로, 1절 핑갈라의 표와 같은 이진법 위에 섭니다. 체스를 끝까지 따져 보는 일이 왜 불가능한지를 보인 섀넌의 어림도 곱의 법칙입니다(「이기는 쪽이 존재한다」).
• 타입⁠(type)⁠: 프로그래밍 언어에서 이진 트리⁠(binary tree)⁠ 타입은 '비었거나, 두 부분 트리가 달린 마디'로 정의합니다. 이 정의를 그대로 옮긴 식 $T = 1 + xT^2$을 생성함수로 풀면, 마디가 $n$개인 이진 트리의 수가 카탈랑 수로 나옵니다. 타입을 합과 곱으로 셈하는 이 생각이 대수적 자료형⁠(algebraic data type)⁠입니다(「증명은 프로그램이다」). 이 등식을 만족하는 타입 가운데 가장 작은 것, 곧 유한한 트리만 모은 것이 시작 대수이고, 트리를 아래에서부터 접어 값을 계산하는 fold가 하나뿐이라는 사실은 4절의 수학적 귀납법을 다른 말로 한 것입니다. 곱의 법칙과 합의 법칙이 세는 순서쌍⁠(ordered pair)⁠의 집합과 서로소 합집합⁠(disjoint union)⁠은 범주론⁠(category theory)⁠에서 곱과 쌍대곱⁠(coproduct)⁠이라 부르는 것이기도 합니다. 같은 성질이 최대공약수⁠(greatest common divisor)⁠와 교집합⁠(intersection)⁠과 '그리고'도 정한다는 이야기는 「화살표만으로 본 수학」 1–2절에 있습니다.
• 무한: 부분집합이 $2^n$개라는 1절의 셈을 무한집합으로 밀고 가면 칸토어의 정리, 곧 어떤 집합이든 그 부분집합 전체의 모임이 원래 집합보다 크다는 결론에 이릅니다. 그러니 가장 큰 무한은 없습니다(「무한에도 크기가 있다」).
• 정수론: 오일러의 분할 생성함수와 소수의 곱 공식은 같은 발상의 두 얼굴입니다. 곱으로 적힌 식을 전개하면 세고 싶은 대상이 계수로 나옵니다(「소수를 세는 사람들」).
• 거리: 격자 도시에서 가장 짧은 택시 길의 수는 가로 걸음과 세로 걸음의 순서를 고르는 이항계수이고, 교차로마다 그 수를 적으면 메루의 계단이 비스듬히 나타납니다(「까마귀와 택시」).