2009/11/28 12:48
A, B, C, D ... N 이라는 사람들이 있습니다.
이 사람들은 다들 모자를 쓰고 있는데, 한 집에서 파티를 한 후
사람들이 모자를 가지고 자신의 집으로 가게 됩니다.
이 때 규칙이 있는데, 자신이 자신의 모자를 가져가면 안된다(완전순열)입니다.
총 x명이 있다고 친 후, x명이 파티를 한 후 집으로 갈 때
모자를 가져가는 방법의 가지 수를 f(x) 라고 합니다.
이 때, A가 집으로 갑니다. A는 가장 처음에 모자를 가져가는 사람이라고 하겠습니다.
A가 누가되건, 그건 중요한게 아닙니다. 모두들 현재 ''동등한'' 상황에 쳐해있죠.
그러니까 먼저 뽑는 사람이 누구냐는 것은 중요하지 않습니다.
A의 가 모자를 선택할 수 있는 가지수는 x-1C1 가지 입니다.
그리고 A가 선택한 모자의 주인을 B라고 명명하겠습니다.
이 때 크게 2가지 경우로 나눌 수 있죠.
i) B가 A의 모자를 가져간다
이 때는 x-2명의 사람들이 처음부터 B와 A가 없었다고 하고
계속 파티를 진행 한 후에 순서대로 떠나면 되겠죠?
그러니까 나머지 사람들, 즉 x-2명이 모자를 가져가는 방법의 수는
f(x-2)가 됩니다.
ii) B가 A의 모자를 가져가지 않는다.
이 말을 좀 더 다르게 해석해보겠습니다.
남아있는 모자 중 없는 모자는 A가 가져간 B의 모자입니다.
즉, A가 B의 모자를 가져갔는데 B가 A의 모자를 가져가지 않는다는 것은
남아있는 A의 모자가 B의 모자와 같은 역할을 하고 있다고 볼 수 있습니다
(각각의 모자는 자신의 주인이 자신을 뽑지 못하도록 하는 역할을 하고 있습니다)
그러니까 A가 없었다고 치고, B의 모자도 원래 없었다고 친 후
A의 모자를 B의 것이라고 우기면 (...) 총 x-1명이 계속해서 게임을 진행하는
꼴이 되겠죠.
그리하여, 남은 사람 x-1명이 모자를 가져가는 방법의 수는 f(x-1)입니다
즉, i), ii)에 의해서 A가 B의 모자를 가져갔을 경우
f(x-2)+f(x-1)의 가지수가 발생하게 된다는 것을 알 수 있습니다.
이 때, B가 될 수 있는 가지수는, A가 뽑을 수 있는 모자의 가지수와 같습니다.
그러니까 B가 될 수 있는 사람의 가지수는 총 x-1가지 (x-1C1) 입니다
(A는 가지수를 왜 안세고, B는 세는지를 파악하세요)
이 값을 곱해준다면
(x-1){f(x-2)+f(x-1)}
이 값은 어떤 값과 같냐구요? 바로 f(x)입니다.
가장 첫번째로 모자를 뽑아 파티장을 나가는 A를 기준으로하여
모든 경우를 다 정리했기 때문이죠.
f(x) = (x-1){f(x-2)+f(x-1)}
이 값의 정리는 점화식 파트를 참고하시면 하실 수 있으므로 생략.
중요한건 점화식 정리 연습이 아니라 점화식을 떠올리는 발상이니까요.
이 사람들은 다들 모자를 쓰고 있는데, 한 집에서 파티를 한 후
사람들이 모자를 가지고 자신의 집으로 가게 됩니다.
이 때 규칙이 있는데, 자신이 자신의 모자를 가져가면 안된다(완전순열)입니다.
총 x명이 있다고 친 후, x명이 파티를 한 후 집으로 갈 때
모자를 가져가는 방법의 가지 수를 f(x) 라고 합니다.
이 때, A가 집으로 갑니다. A는 가장 처음에 모자를 가져가는 사람이라고 하겠습니다.
A가 누가되건, 그건 중요한게 아닙니다. 모두들 현재 ''동등한'' 상황에 쳐해있죠.
그러니까 먼저 뽑는 사람이 누구냐는 것은 중요하지 않습니다.
A의 가 모자를 선택할 수 있는 가지수는 x-1C1 가지 입니다.
그리고 A가 선택한 모자의 주인을 B라고 명명하겠습니다.
이 때 크게 2가지 경우로 나눌 수 있죠.
i) B가 A의 모자를 가져간다
이 때는 x-2명의 사람들이 처음부터 B와 A가 없었다고 하고
계속 파티를 진행 한 후에 순서대로 떠나면 되겠죠?
그러니까 나머지 사람들, 즉 x-2명이 모자를 가져가는 방법의 수는
f(x-2)가 됩니다.
ii) B가 A의 모자를 가져가지 않는다.
이 말을 좀 더 다르게 해석해보겠습니다.
남아있는 모자 중 없는 모자는 A가 가져간 B의 모자입니다.
즉, A가 B의 모자를 가져갔는데 B가 A의 모자를 가져가지 않는다는 것은
남아있는 A의 모자가 B의 모자와 같은 역할을 하고 있다고 볼 수 있습니다
(각각의 모자는 자신의 주인이 자신을 뽑지 못하도록 하는 역할을 하고 있습니다)
그러니까 A가 없었다고 치고, B의 모자도 원래 없었다고 친 후
A의 모자를 B의 것이라고 우기면 (...) 총 x-1명이 계속해서 게임을 진행하는
꼴이 되겠죠.
그리하여, 남은 사람 x-1명이 모자를 가져가는 방법의 수는 f(x-1)입니다
즉, i), ii)에 의해서 A가 B의 모자를 가져갔을 경우
f(x-2)+f(x-1)의 가지수가 발생하게 된다는 것을 알 수 있습니다.
이 때, B가 될 수 있는 가지수는, A가 뽑을 수 있는 모자의 가지수와 같습니다.
그러니까 B가 될 수 있는 사람의 가지수는 총 x-1가지 (x-1C1) 입니다
(A는 가지수를 왜 안세고, B는 세는지를 파악하세요)
이 값을 곱해준다면
(x-1){f(x-2)+f(x-1)}
이 값은 어떤 값과 같냐구요? 바로 f(x)입니다.
가장 첫번째로 모자를 뽑아 파티장을 나가는 A를 기준으로하여
모든 경우를 다 정리했기 때문이죠.
f(x) = (x-1){f(x-2)+f(x-1)}
이 값의 정리는 점화식 파트를 참고하시면 하실 수 있으므로 생략.
중요한건 점화식 정리 연습이 아니라 점화식을 떠올리는 발상이니까요.
