문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 완전순열 (문단 편집) == [[점화식]]과 일반항 == [math(1)]부터 [math(n)]까지의 자연수를 한 줄 써 놓고, 아랫줄에도 한 줄 더 쓴다. 윗줄의 숫자들을 아랫줄의 숫자들로 하나하나씩 대응할 때 자기 자신을 제외한 다른 숫자로 대응을 하면 된다. 이렇게 대응하는 방법의 수를 센 것이 [math(D_n)]이다. 먼저 [math(1)]을 [math(2)]부터 [math(n)]까지 총 [math((n-1))]개의 자연수 중 하나로 대응해야 한다. 이때 [math(1)]이 [math(k)]에 대응된다고 하면 이후의 대응을 아래의 두 가지 경우로 나눌 수 있다. 1. [math(k)]가 [math(1)]에 대응되는 경우, [math(1)]과 [math(k)]는 서로 짝을 이루었고 나머지 [math((n-2))]개를 교란하면 되므로 그 경우의 수는 [math(D_{n-2})]. 1. [math(k)]가 [math(1)]에 대응되지 않는 경우, [math(k)]와 [math(1)]을 같은 것으로 취급해서 [math((n-1))]가지를 교란하는 경우와 같으므로 그 경우의 수는 [math(D_{n-1})]. [math(k)]로 가능한 수는 [math(1)]을 제외한 [math((n-1))]가지가 있으므로 전체 경우의 수는 [math(D_n= (n-1) \left( D_{n-1}+D_{n-2} \right))] 점화식을 얻으면 일반항에 한 걸음 다가간 것이다. 매우 교묘하게도, 적절히 이항해서 위 점화식을 다음과 같이 변형해주고 [math(D_n - nD_{n-1} = - \left\{D_{n-1} - \left( n-1 \right) D_{n-2} \right\})] 좌변을 [math(a_n)]으로 놓으면, 우변은 [math(-a_{n-1})]이 되므로 수열 [math(a_n)]은 공비가 [math(-1)]인 등비수열이다. [math(a_2 = D_2 -2D_1 = 1)]이므로 [math(a_n= \left( -1 \right)^n)]이다. 따라서 [math(D_n - nD_{n-1} = \left( -1 \right)^n)] 로 정리할 수 있다. 이제 양변을 [math(n!)]로 나누면 [math(\dfrac{D_n}{n!} - \dfrac{D_{n-1}}{(n-1)!} = \dfrac{\left( -1 \right)^n}{n!})] [math(\dfrac{D_n}{n!} = b_n)]라 놓으면 식은 [math(b_n - b_{n-1} = \dfrac{\left( -1 \right)^n}{n!})]이 되며 이는 전형적인 점화식 꼴이다. 하나씩 대입하면서 더해나가면 [math(\displaystyle b_n = b_1 + \sum_{k=2}^n \frac{\left( -1 \right)^k}{k!})] [math(\displaystyle \frac{D_n}{n!} = \frac{D_1}{1!} + \sum_{k=2}^n \frac{\left( -1 \right)^k}{k!} = \sum_{k=2}^n \frac{\left( -1 \right)^k}{k!})] 이 되는데 [math(\dfrac{\left( -1 \right)^0}{0!} + \dfrac{\left( -1 \right)^1}{1!} = 0)]이므로 [math(k=0)]부터 더해나가도 된다. 결과적으로 일반항은 다음과 같다. ||[math(\displaystyle\ D_n = \sum_{k=0}^n \frac {n! \left( -1 \right)^k}{k!} \ (n \ge 1))] || [math(\dfrac{n!}{k!} = {}_n{\rm P}_{n-k})]이므로 위 식은 [math(\displaystyle \sum_{k=0}^n {}_n{\rm P}_{n-k} \left( -1 \right)^k)]로도 나타낼 수 있으며 [math(n \ge 2)]일 경우 [math(k=0)]인 항과 [math(k=1)]인 항을 더한 값이 [math(0)]이 되므로 순열을 이용한 표기로는 ||[math(\displaystyle D_n = \sum_{k=2}^n {}_n{\rm P}_{n-k} \left( -1 \right)^k \ (n \ge 2))] || 가 된다. 또한 [math(\displaystyle e^x = \sum_{k=0}^\infty \frac{x^k}{k!})]이므로 [math(\displaystyle \lim_{n \to \infty} \frac{D_n}{n!} = \frac 1e)]이며 이를 통해 [math(D_n)]은 [math(\dfrac{n!}{e})]의 반올림 값임을 알 수 있다. 위 일반항은 [[포함·배제의 원리]]로도 유도가 가능하다. [math(n)]개의 물체를 배열하는 경우의 수가 [math(n!)]이고 이 중 부동점의 개수가 [math(k)]개 이상인 배열의 개수는 [math(\dfrac{n!}{k!})]개이므로 포함·배제의 원리를 적용하면 원하는 결과를 얻는다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기