이동·교통 확률과통계
바둑판 길에서 가장 짧은 길은 몇 가지일까 · 이항계수
동쪽 4블록, 북쪽 3블록 가는 최단 경로는 ₇C₃ = 35가지다
- ₇C₃ = 35 동 4, 북 3 블록의 최단 경로
- 2⁷ = 128 일곱 번 움직이는 모든 경로
- 왼쪽 + 아래 교차로마다 경로 수를 구하는 덧셈
바둑판처럼 길이 난 동네에서 집에서 학교까지 동쪽으로 4블록, 북쪽으로 3블록을 가야 한다. 돌아가지 않는 가장 짧은 길은 모두 몇 가지일까. 어떤 최단 경로든 「동」 4번과 「북」 3번을 어떤 순서로 섞은 것이다. 예를 들어 동동북동북북동처럼.
최단 경로를 고르는 일은 일곱 칸 중 세 칸을 고르는 일과 같다.
그러니 일곱 번의 이동 가운데 「북」이 들어갈 세 자리를 고르는 방법의 수와 같다. 7개에서 3개를 고르는 조합 ₇C₃ = 7 × 6 × 5 ÷ (3 × 2 × 1) = 35가지다. 「동」 4자리를 골라도 ₇C₄ = 35로 같다. 같은 것이 있는 순열로 7! ÷ (4! × 3!)을 계산해도 35가 나온다.
이 수는 이항정리의 계수이기도 하다. (a + b)⁷을 전개하면 a⁴b³의 계수가 ₇C₃ = 35다. 일곱 개의 괄호에서 각각 a(동)나 b(북)를 하나씩 골라 곱하는 일이, 일곱 번의 갈림길에서 동이나 북을 고르는 일과 같기 때문이다. 일곱 번 움직이는 모든 경로는 2⁷ = 128가지이고, 이것은 계수를 모두 더한 값이다.
교차로마다 「여기까지 오는 최단 경로 수」를 적어 보면 파스칼의 삼각형이 나온다. 각 교차로의 수는 바로 왼쪽과 바로 아래 교차로의 수를 더한 값이다. 공사 중이라 막힌 교차로가 있으면 그 칸을 0으로 두고 같은 덧셈을 이어 가면 된다. 내비게이션이 대안 경로를 찾을 때도 이런 계산을 응용한다.