[모듈식 확률과 통계] 1.경우의 수 (9)최단거리 문제 (같은 것이 있는 순열 관점)

[확률과통계]-[1.경우의 수]-[(8)순열과 조합]-[(9)최단거리 문제 (같은 것이 있는 순열 관점)]

 

최단거리 문제 (같은 것이 있는 순열 관점)

 

바둑판모양의 도로가 있습니다. 가로선과 세로선들이 도로입니다. 도로의 한쪽 끝에서 반대편 끝까지 이동할 때, 최단거리로 이동할 수 있는 경우의 수를 구하는 문제입니다. 풀이 방법이 두가지가 있습니다. 

 

1) 같은 것이 있는 순열 관점

2) 합의 법칙 관점

 

오늘은 첫번째 방법을 설명하겠습니다. 

 

아래와 같은 경우가 최단거리입니다. 

 

 

최단거리의 특징 살펴봅시다. 가로방향의 한칸 길이를 a, 세로방향 한칸 길이를 b라고 놓는다면 아래와 같이 표현할 수 있습니다. 

 

최단거리의 특징이 어떤가요. a가 5개, b가 4개입니다. 바둑판의 가로방향 칸의 수와 세로방향 칸의 수입니다. 다른 최단거리들은 이렇게 찾아낼 수 있습니다. 아래 문자를 나열하는 경우의 수입니다. 

 

a,a,a,a,a,b,b,b,b

 

다라서 아래와 같이 계산됩니다. 같은 것이 있는 순열입니다. 

 

 

일반화시켜봅시다. 가로로 m칸, 세로로 n칸인 도로망 한쪽 끝에서 반대편 끝으로 가는 최단거리의 수는 아래와 같습니다. 

 

$\frac{(m+n)!}{m!n!}$