[조합론] 대각선을 넘지않고 갈수있는 최단경로의 수 - 카탈란 수
Math2010. 8. 28. 18:00 |사진정리하다가, 몇 년전에 싸이에 올렸던 사진이 나와서, 재구성함.
-----------------------------
아래와 같이 정사각형 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) 요고 심심찮게 나오는거 같다.
계차수열 이용해서 푸는 방법과, 조합론적으로 점화식 세워서 푸는 법 등 다양한 풀이법에 대해 생각해보면 좋을것 같다.
-----------------------------
아래와 같이 정사각형 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) 요고 심심찮게 나오는거 같다.
계차수열 이용해서 푸는 방법과, 조합론적으로 점화식 세워서 푸는 법 등 다양한 풀이법에 대해 생각해보면 좋을것 같다.