OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY VOLUME XXI. No. XVIII. pp. 467-481. THE PROBLEM OF DERANGEMENT' IN THE THEORY BY MAJOR P. A. MACMAHON, R.A., Sc.D., LL.D., F.R.S. HONORARY MEMBER CAMBRIDGE PHILOSOPHICAL SOCIETY [WITH TITLE-PAGE, CONTENTS AND GENERAL INDEX TO VOL. XXI.] CAMBRIDGE: AT THE UNIVERSITY PRESS M.DCCCC.XII. ADVERTISEMENT THE Society as a body is not to be considered responsible for any facts and opinions advanced in the several Papers, which must rest entirely on the credit of their respective Authors. THE SOCIETY takes this opportunity of expressing its grateful acknowledgments to the SYNDICS of the University Press for their liberality in taking upon themselves the expense of printing this Volume of the Transactions. XVIII. The Problem of 'Derangement' in the Theory of Permutations. By Major P. A. MACMAHON, R.A., Sc.D., LL.D., F.R.S. [Received May 1, 1912. Read May 6, 1912.] SECTION I. 1. IN a paper entitled 'A Certain Class of Generating Functions in the Theory of Numbers,' Phil. Trans. Roy. Soc., 1894, A. pp. 111-160, I have given a solution of the general problem of 'derangement' in the form of a symmetric function generating function. It was therein established that the number of permutations of the assemblage of letters ... which are such that exactly m of the letters are in the places they originally occupied, is equal to the coefficient of the term It was also shewn that the same number is the coefficient of the term amxx,... X or of am (§§2... n), in the notation of symmetric functions, in the development of the algebraic fraction 1 1-a2a,+(a-1) (a+1) Σx12- (a-1) (a + 2) ΣX1 X2 X3 + ... + (-)" (a− 1)"1 (a + n − 1) x1Xq... Xn − ΣX1X9X3+ This does not involve the numbers 1, 2, ... En and is the condensed generating function. If the number in question be denoted by {m; ËË ... Ë} the condensed generating function is clearly Σ {m; §i§2 ..... §n} (§1§2 .... §n) aTM. ... I propose, in this short paper, to submit the generating function to examination so as to determine the properties of the number 1 − ap1 + ( a − 1) (a + 1 ) p2 − ( a − 1 )}2 (a + 2) μs + ... - +(-)" ( a − 1 − (a + n − 1) Pa When, in the generating functions, we put a = 0 the numbers generated are and the functions become and 0: éé ... é} ; (Xz + Fz + ... + In)E : (X2 + Xz + ... + In )ts ... ( X1 + £g + ... + £#−1)£*, 1 1 - p2 - 2p2 - ... — (n − 1) Pn If = = ... == 1 some properties of the numbers are obtained in a very simple ć ć manner from the redundant function when (1) (1) is multiplied out so as to be expressed as a linear function of monomial symmetric functions, the coefficient of x,x,... En or of pn is seen to be for, retaining a in the redundant generating function and putting Developing this expression, so as to obtain the coefficient of pn, we find It is readily seen à priori that this result is correct; for we can select the m letters, which are to remain undisplaced, in ways; and, for each of these selections, the (m) remaining letters can be permuted so as to be all displaced in {0; 1n-m} ways. The whole of the permutations can be found by summing {m; 1"} from m = 0 to m=n. Hence the well known formula The reader is reminded that the early values of {0; 1"} are 1, 0, 1, 2, 9, 44, 265, 1854, 14833, .... From the above results it is easy to shew that {0; 1"} = (n - 1) [{0; 1′′−1} + {0; 1"-2}], both of them well known relations. 4. We will now consider the condensed generating function 1 1-p2-2p-3p. -... - (n - 1) Pn ' wherein (0; 12... En} is the coefficient of the symmetric function (§§2... §n). ... We may regard 1, 2, En as numbers in descending order of magnitude and n as indefinitely great. The numbers §1, §2, ... §n may be any integers, zero not excluded, but there are certain symmetric functions that, from à priori considerations, must be absent. For clearly 3+ (0; 12... En} = 0, if &1> §2++...+n. For example such functions as (21), (421), ... do not present themselves in the development. In the first instance we will restrict ourselves to the numbers {0; 18} which we will write P for convenience. On the right-hand side to find the coefficient of (1") or pn the relevant terms are PnPn-Pn-2P2Pn-2-2Pn-3P3Pn-3-... - (n − 3) P2Pn-2P2 - (n-2) P1Pn-1P1 − (n − 1) Pn, |