|
In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. The number of derangements of a set of size ''n'', usually written ''Dn'', ''dn'', or !''n'', is called the "derangement number" or "de Montmort number". (These numbers are generalized to rencontres numbers.) The subfactorial function (not to be confused with the factorial ''n''!) maps ''n'' to !''n''.〔The name "subfactorial" originates with William Allen Whitworth; see .〕 No standard notation for subfactorials is agreed upon; ''n''¡ is sometimes used instead of !''n''.〔Ronald L. Graham, Donald E. Knuth, Oren Patashnik, ''Concrete Mathematics'' (1994), Addison–Wesley, Reading MA. ISBN 0-201-55802-5〕 The problem of counting derangements was first considered by Pierre Raymond de Montmort〔de Montmort, P. R. (1708). ''Essay d'analyse sur les jeux de hazard''. Paris: Jacque Quillau. ''Seconde Edition, Revue & augmentée de plusieurs Lettres''. Paris: Jacque Quillau. 1713.〕 in 1708; he solved it in 1713, as did Nicholas Bernoulli at about the same time. == Example == Suppose that a professor has had 4 of his students – student A, student B, student C, and student D – take a test and wants to let his students grade each other's tests. Of course, no student should grade his or her own test. How many ways could the professor hand the tests back to the students for grading, such that no student received his or her own test back? Out of 24 possible permutations (4!) for handing back the tests, there are only 9 derangements: :BADC, BCDA, BDAC, :CADB, CDAB, CDBA, :DABC, DCAB, DCBA. In every other permutation of this 4-member set, at least one student gets his or her own test back. Another version of the problem arises when we ask for the number of ways ''n'' letters, each addressed to a different person, can be placed in ''n'' pre-addressed envelopes so that no letter appears in the correctly addressed envelope. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「derangement」の詳細全文を読む スポンサード リンク
|