HMMT 二月 2000 · POW 赛 · 第 1 题

HMMT February 2000 — POW Round — Problem 1

A derangemen t of a string of distin t elemen ts is a rearrangemen t of the string su h that no elemen t app ears in its original p osition. F or example, BCA is a derangemen t of ABC. D represen ts the n um b er of derangemen ts of an y string omp osed of n distin t n elemen ts. D = 1 and D = 2. 2 3 (a) What are D and D ? 4 5 (b) Ho w man y derangmen ts are there of the string ABCDEF G? ( ) Find a re ursiv e relationship for D in terms of the previous t w o terms ( D and n n 1 D ). n 2 (d) Find a re ursiv e relationship for D in terms of only the previous term, D . n n 1

解析

(a) D = 9 ; D = 44 4 5 (b) This is D = 1854 7 ( ) D = ( n 1)( D + D ) n n 1 n 2 n (d) D = n D + ( 1) n n 1