교란순열 썸네일형 리스트형 교란순열 교란순열의 개수를 구해보자 교란순열이란 원래 위치에 있는 원소가 하나도 없는 순열이다. 사람들이 각각 자신의 모자를 벗었다가 아무 모자나 다시 쓰는데 모든 사람이 자기 것이 아닌 모자를 쓰는 순열이라고 할 수 있다. 길이가 n 인 순열에서 교란순열의 개수를 어떻게 알 수 있을까? 교란 순열의 개수를 구하는 공식은 $$n! \sum_{k=0}^n \frac{(-1)^k}{k!}$$ 이를 유도해 보자 가장 쉽게 생각해서 모든 순열개수 n!에서 교란순열이 아닌 수열의 개수를 빼주면 된다. 한 개 이상의 수가 원래 자리에 있는 순열의 개수를 구해보면 4C1*3!이다 하지만 이렇게 구한 수를 이용해서 4!- 4C1*3!을 하게 된다면 2개 이상의 수가 원래 자리에 있는 순열은 중복해서 빠지게 된다. 그렇기 때문에.. 더보기 이전 1 다음