[차현우] 실력편 확률과 통계 (2014) - 순열 |
3. 같은 것이 있는 경우의 순열 4. 원순열_00:10:04 |
안녕하세요 선생님. 최단 경로 문제를 풀 때마다 궁금해서 질문을 드립니다. 중간지점을 세우는 이유는 무엇이며 세운다고 한다면 점의 위치는 어떻게 정해야 할까요? 그리고 저는 이 문제를 풀 때 가능한 경우가 (오른쪽*6) & (위로*4) 라고 생각해서 (10!)/(6!*4!)로 풀었는데 값이 210으로 틀리게 되었습니다. 왜 이렇게 풀면 답이 다르게 나오는 건가요? 감사합니다. |
물론 빈 곳이 없이 완전한 직사각형의 형태로 나왔다면, 학생의 풀이처럼 처음부터 끝까지 같은 것이 있는 순열로 생각하면 되지만,
이 문제의 경우 완전한 직사각형의 형태가 아닌 아래부분이 비워져있는 직사각형입니다.
이러한 상황에서 10!/6!4! 으로 계산한다면,
존재하지 않은 길로 가는 상황이 포함됩니다.
예를 들면, (오오오오위위위위오오) 라는 방법은
처음에 오른쪽으로 네번 가야하는데, 처음에는 오른쪽으로 3번까지만 전진이 가능하기 때문에,
해당 방법은 실제로는 불가능한 방법인 것입니다.
따라서 다른 방법 중에 중간지점을 설정하는 방법을 생각한 것인데,
실제로 존재하지 않는 경로를 생각하지 않으면서,
모든 경로의 가짓수를 다 생각할 수 있게 됩니다.
중간 지점을 설정하는 방법은 강의에서 설명한 것처럼 시작점으로 부터 같은 거리만큼 떨어진 모든 점들을 다 중간지점으로 생각하시면 되는데, 각 지점 중 반드시 하나의 지점만을 지나야 하기 때문에 중복되거나 빠지는 상황이 발생하지 않게 되며,
일반적으로는 같은 거리만큼 떨어진 점들 중에 실제로 존재하지 않는 경로가 있도록 설정한다면 가장 좋습니다. |