Permutation Cycle Decomposition (1) 썸네일형 리스트형 55. Permutation Cycle Decomposition 순열(Permutation)은 $1$ 이상 $n$ 이하의 정수가 한 번씩 등장하는 특수한 형태의 수열이다. $n$은 순열의 길이이며 $0$보다 큰 정수이다. 이 글에 나오는 순열과는 비슷하지만 약간 다르다. 특정한 조건을 만족하는 순열의 개수를 다음과 같은 공식으로 구할 수 있다. 길이가 $n$인 순열의 개수는 $n!$이다. 길이가 $n$인 순열 $a: \{a_1, a_2, \ldots a_n\}$ 중 $a_i=i$를 만족하는 $i$가 존재하지 않는 순열의 개수를 $f(n)$이라고 하면, $f(1)=0, f(2)=1$이고, $n \ge 3$인 경우 $f(n)=(n-1)(f(n-2)+f(n-1))$이다. 또한 그런 $i$가 $k$개 존재하는 순열의 개수는 $_n\mathrm{C}_k \times f(n-k.. 이전 1 다음
