좌표평면의(0,0)에서(3,3)까지 오른쪽 또는 위쪽으로 한 칸씩만 이동한다. (1,1)과(2,2)를 모두 지나지 않는 경로의 수를 구하라.
경로가 음수가 될 수는 없다. 두 지점을 모두 지나는 경로를 두 번 제외한 것이 잘못이다.
(1,1)을 지나는 경로는 시작에서 그 점까지2가지, 그 점에서 끝까지6가지여서12가지다. (2,2)를 지나는 경로도12가지다. 두 지점을 모두 지나는 경로는 세 구간마다 오른쪽 한 번·위쪽 한 번을 사용한다.
따라서 답은4가지다. 좌표 순서 때문에 두 점을 모두 지나는 경우는 반드시(1,1), (2,2)의 순서다. 두 순서를 임의로 곱해서16으로 세면 새로운 중복을 만든다.
뺄셈식에서 각 경로가 몇 번 세어졌는지 표시해 보자. 어느 금지점도 안 지난 경로는1번 남고, 하나만 지난 경로는0번, 둘 다 지난 경로는1−1−1+1=0번 남는다. 음수라는 결과를 고치는 요령보다 이 계수 검사가 일반화에 도움이 된다.
조건도 확인한다. 왼쪽·아래쪽 이동을 허용하면서 이동 횟수를 제한하지 않으면 현재의 여섯 칸 경로 목록을 사용할 수 없다. 시작·끝만 같다고 같은 경우의 수 문제는 아니다. 방향 제한이 있기에 오른쪽3번·위쪽3번의 배열로 경로를 바꿀 수 있다.
교사는 두 금지점을 따로 제외하는 식을 먼저 제시하고 두 번 제외된 실제 경로 하나를 찾게 할 수 있다. 학생이 원인을 설명한 뒤 겹친 전체8가지의 곱셈식까지 연결하는지 확인한다.
출처·착안: Colleen Young, 「Systematic Listing Strategies」. 문항과 예시 답안은 새로 작성했다.