사진정리하다가, 몇 년전에 싸이에 올렸던 사진이 나와서, 재구성함.



-----------------------------



아래와 같이 정사각형 n x n 격자 길을 생각하자.

가령 아래의 경우 4 x 4 이라고 하자.



이때,  start 에서 end 까지 대각선을 넘지 않는 최단거리의 수는?  ( n 에 대한 식으로 나타내시오 )

아래 그림에서 보자면, 위쪽을 기준으로 파란색 대각선을 넘어서는 안되는 것이다. 즉, 빨갛게 칠해놓은 영역은 지나가면 안된다.


가령, 아래 그림에서 초록색 경로는 굿, 빨간색 경로는 대각선을 넘었으므로 낫굿 되겠다.



답을 n 에 대한 수열로 구해보자.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
---------  여기서 부터는 예시 답안 이므로, 직접풀어보고싶은 사람은 안보는게 좋음 ---------------------
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

다양한 풀이가 가능하다.
점화식을 이용해서 풀수도 있고, 계차수열을 이용해서 풀 수도 있다.

그중에서 가장  맘에드는 방법은 대칭을 이용하는 방법이다.
앞에서 예로든 경로중에, 대각선을 넘어간 경로를 보면...


노란색 별로 표시한 부분을 밟았기 때문이라고 생각할 수 있다. 결과적으로 대각선을 넘는 모든 나쁜(?) 경로들을 보면 대각선에서 한칸 내려온 선분을 최소한 한번은 밟게 되어있다는 것을 알 수 있다.

이제, 규칙을 위반하는 경로들이 위 그림에 표시한 노란선 l 을 밟는 순간까지를 노란선에 대해 대칭이동 시켜보자.


( 주의! 처음 선을 넘은순간까지만 대칭이동 하도록 한다. )

Note.  대각선을 넘은 모든 경로는 그림에 보라색으로 표시한 빡스 (가로 n-1 , 세로 n+1 ) 안에 경로가 모두 들어오게 된다.
또한, 그 빡스안에서 만드는 모든 경로는 다시 노란색선에 대칭이동시켜보면, 모두 노란선을 밟는다.
따라서, ' 빡스안의 모든 경로의 수 = 대각선을 넘은 경로의 수 " 가 된다.

그러므로, 대각선을 넘은 경로의 수는   가로 n-1 , 세로 n+1 인 격자길을 지나는 최단경로의 수 이다.

즉, 규칙위반하는 경로의 수는  C(  n-1 + n+1   ,   n-1   )    =     C(  2n , n-1  )   이 된다.

그러므로 대각선을 넘지 않는 경로의 수는 

C(  2n   ,  n   )   -    C(  2n   ,   n-1  )    =     C(  2n , n  )  -   (n/n+1)  C(  2n  , n  )   =     C( 2n, n )  /  n+1   이 된다.

이것은, 문자열에 괄호를 씌우는 방법의 수인, 카탈란 수열과 같다.



수론이랑 특수함수쪽에서 (2n, n) 요고 심심찮게 나오는거 같다.



계차수열 이용해서 푸는 방법과, 조합론적으로 점화식 세워서 푸는 법 등 다양한 풀이법에 대해 생각해보면 좋을것 같다.