금지점 두 개를 피하는 경로가 −4개? 두 번 뺀 경로를 확인해요

(0,0)→(3,3), 오른쪽·위쪽만 이동하고 (1,1),(2,2)를 피해요. 20−12−12는 두 점을 모두 지난8경로를 두 번 빼요. 20−12−12+8=4입니다. 각 경로가 최종 식에서 몇 번 남는지 확인해 보세요.

지형을 따라 굽어 이어지는 실제 도로

사진: Sasha • Instagram.com/sanfrancisco sanfrancisco · CC0 · 원본 출처

좌표평면의(0,0)에서(3,3)까지 오른쪽 또는 위쪽으로 한 칸씩만 이동해요. (1,1)과(2,2)를 모두 지나지 않는 경로의 수를 구해 볼까요?

(63)−(21)(42)−(42)(21)=20−12−12=−4.\binom63-\binom21\binom42-\binom42\binom21=20-12-12=-4.

경로가 음수가 될 수는 없어요. 두 지점을 모두 지나는 경로를 두 번 제외한 것이 잘못이에요.

(1,1)을 지나는 경로는 시작에서 그 점까지2가지, 그 점에서 끝까지6가지여서12가지예요. (2,2)를 지나는 경로도12가지예요. 두 지점을 모두 지나는 경로는 세 구간마다 오른쪽 한 번·위쪽 한 번을 사용해요.

2×2×2=8,20−12−12+8=4.2\times2\times2=8,\qquad 20-12-12+8=4.

따라서 답은4가지예요. 좌표 순서 때문에 두 점을 모두 지나는 경우는 반드시(1,1), (2,2)의 순서예요. 두 순서를 임의로 곱해서16으로 세면 새로운 중복을 만들어요.

뺄셈식에서 각 경로가 몇 번 세어졌는지 표시해 볼까요? 어느 금지점도 안 지난 경로는1번 남고, 하나만 지난 경로는0번, 둘 다 지난 경로는1−1−1+1=0번 남아요. 음수라는 결과를 고치는 요령보다 이 계수 검사가 일반화에 도움이 돼요.

조건도 확인해요. 왼쪽·아래쪽 이동을 허용하면서 이동 횟수를 제한하지 않으면 현재의 여섯 칸 경로 목록을 사용할 수 없어요. 시작·끝만 같다고 같은 경우의 수 문제는 아니에요. 방향 제한이 있기에 오른쪽3번·위쪽3번의 배열로 경로를 바꿀 수 있어요.

두 금지점을 따로 제외하는 식에서 두 번 제외된 실제 경로 하나를 찾아봐요. 원인을 설명한 뒤 겹친 전체8가지의 곱셈식까지 연결해 봐요.

출처·착안: Colleen Young, 「Systematic Listing Strategies」. 문항과 예시 답안은 새로 작성했다.

이 글 공유하기

개인정보 및 방문 통계 안내