when t1, to, &c., are put equal to unity, is equal to the coefficient of the same term in the product P2 ... P2 † (2α2+a2+...+a,)31(2α2+2α2+...+a,)22... (22+2α2+...+2a,). This result gives a direct connexion between the number of compositions and the permutations of the letters in the product a "a" a. Selecting any permutation, suppose that the letter a occurs q, times in the last Pr+Pr+1+ +p, places of the permutation ; the coefficient in question may be represented by Σ291+2+...+¶s, the summation being for every permutation, and since q1=P, this may be written ... 2P1-1292+93+...+98. Ex. Gr. For the bipartite 22, P1 =P2=2, and we have the following scheme : T3 n Hence F(22)=2(22+2+2+2+2+2°)=26. We may regard the fraction 1 }. {1−t1(2a1+as+...+as)} {1−t2(2a1+2a2+...+as)} ... {1 −ts(2a1+2a2+...+2a,)} as a redundant generating function, the enumeration of the compositions being given by the coefficient of The transformation of the pure generating function into a factorized redundant form supplies the key to the solution of a large number of questions in the theory of ordinary permutations, as will be seen later. [The transformation of the last section involves The Theory a comprehensive theory of Permutations, which of Permuit is convenient to discuss shortly here. tations. If X1, X2, X3, Xn be linear functions given by the matricular relation ... that portion of the algebraic fraction, which is a function of the products s11, S2, S3X3· ... Snxn only is (1 − αnnSnXn) | |(1 − α1181x1)(1 − ɑ22S2X2)(1 − α33§3X3) where the denominator is in a symbolic form and denotes on expansion 1-111+Σ|α11a22|8182X1X2-...+(-)n | α11a22a33.....Ann | $182...SnX1X2.......In, where laul, a11a22,... |α11α22... ann denote the several co-axial minors of the determinant a 1 1 1 1 α 1 1 1 α 1 1 1 a 1 ... 1-aΣx1+(a−1)(a+1)Σx1x2−..+(−)" (a− 1)n-1(a+n − 1)x1x2...In. It is clear that a large class of problems in permutations can be solved in a similar manner, viz., by giving special values to the elements of the determinant of the matrix. The redundant product leads uniquely to the real generating function, but the latter has generally more than one representation as a redundant product, in the cases in which it is representable at all. For the existence of a redundant form, the coefficients of x1, x2, in X1X21 the denominator of the real generating function must satisfy 2n − n2 + n − 2 conditions, and assuming this to be the case, a redundant form can be constructed which involves n-1 undetermined quantities. We are thus able to pass from any particular redundant generating function to one equivalent to it, but involving n-1 undetermined quantities. Assuming these quantities at pleasure we obtain a number of different algebraic products, each of which may have its own meaning in arithmetic, and thus the number of arithmetical correspondences obtainable is subject to no finite limit (cf. MacMahon, loc. cit., pp. 125 et seq.)] the collection, termed the parts of the partition, in descending order of magnitude, and to indicate repetitions of the same part (3213). Euler's pioneering work in the subject rests on the observaby the use of exponents. Thus (32111), a partition of 8, is written tion that the algebraic multiplication x x x x x x ... =2a+b+c+... is equivalent to the arithmetical addition of the exponents with p integers drawn from the series a, b, c, a, b, c, He showed that the number of ways of composing n ..., repeated or not, is equal to the coefficient of Pan in the ascending expansion of the fraction (1 − x)(1 − x2) (1 − 2)* To explain this we have two lemmas :1 Lemma 1.-The coefficient of i.e., after Cauchy, the residue in the ascending expansion of (1-e)-is-1. For when i is unity, it is obviously the case, and (1 − ex)—'—1 − (1 − c≈)−6 + e¤(1 − ex)−−1 Here the residue of d da (1 is zero, and therefore the residue of (1-e)-, is unchanged when i is increased by unity, and is, therefore, always-1 for all values of i. Lemma 2.-The constant term in any proper algebraical fraction developed in ascending powers of its variable is the same as the residue, with changed sign, of the sum of the fractions obtained by substituting in the given fraction, in lieu of the variable, its exponential multiplied in succession by each of its values (zero excepted, if there be such), which makes the given fraction infinite. For write the proper algebraical fraction Let a, be a value of x which makes the fraction infinite. The residue of ΣΣΣ + Σ is equal to the residue of ΣΣΣ. part i parts or fewer and having the largest remains the same when the equal to j The study of this representation on a lattice (termed by Sylvester the "graph ") yields many theorems similar to that just given, and, moreover, throws considerable light and when μ, the residue vanishes so that we have to consider upon the expansion of algebraic series. ... -P Sylvester, Franklin, Durfee, Ely, and others, have evolved a Constructive Theory of Partitions, the object of which is the contemplation of the partitions Sylvester's themselves, and the evolution of their properties graphical from a study of their inherent characters. It Method. is concerned for the most part with the partition of a number into parts drawn from the natural series of numbers 1, 2, 3.... Any partition, say (521) of the number 8, is represented by nodes placed in order at the points of a rectangular lattice, when the partition is given by the enumeration of the nodes by lines. If we enumerate by columns we obtain another partition of 8, viz., (3213), which is termed the conjugate of the former. The fact of conjugacy was first pointed out by Ferrers. If the original partition is one of a number n in i parts, of which the largest is j, the The coefficient of aan in the expansion of 1 1-a.1-ax.1−ax2. + 22 a3 ...1-axt denotes the number of ways of composing n with j or fewer parts, none of which are greater than i. The expansion is known to be ...1-2+ε -a3. 1 -x.1-x2....1-x It has been established by the constructive method by F. Franklin (Amer. Jour. of Math. vol. v. p. 254), and shows that the generating function for the partitions in question is which, observe, is unaltered by interchange of i and j. (1-x)(1-x)(1-23)... ad inf. =Σ( − Ÿæ1(3)2+1), known as the "pentagonal number theorem," which on interpre- To illustrate an important dissection of the graph we will consider those graphs which read the same by columns as by lines; these are called self-conjugate. Such a graph may be obviously dissected into a square, containing say 2 nodes, and into two graphs, one lateral and one subjacent, the former. The former graph is limited latter being the conjugate of the to contain not more than @ parts, but is subject to no other condition. Hence the number of self-conjugate partitions of n which are associated with a square of 02 nodes, is clearly equal to the number of partitions of (n-02) into 0 or few parts, i.e., it is the coefficient of x(n−02) in of a0xn in the product (1+ax)(1+ax3)(1+ax3) ... (1+ax2s+1)..., | every line of route which proceeds from the origin in the positive and thence the coefficient of ae in this product is directions of the axes. ... Again, if we restrict the part magnitude to i, the largest angle of nodes contains at most 2i-1 nodes, and based upon a square of 02 nodes we have partitions enumerated by the coefficient of aox" in the product (1+ax)(1+ax3)(1+ax3) ... (1+ax2i-1); moreover the same number enumerates the partition of 1(n − 02) into 0 or fewer parts, of which the largest part is equal to or less than i – 0, and is thus given by the coefficient of x-2) in the expansion of 1-xi-0+1.1−xi−0+2.1−xi-0+3....1-xi 1-x. .1-x2.1-x3.... 1 - xə - x2i-20+2.1 − x2i-20+4 .1-x2i 1-x2.1-x. 1 − x6. ... or of x" in hence the expansion 1-220 (1+ax)(1+ax3)(1+ax3)... (1+ax2i-1) જીફ There is no difficulty in extending the graphical method to three dimensions, and we have then a theory of a special kind of partition of multipartite numbers. Of such kind is the partition to three Dimensions. This brings in view the modern notion of a partition, which has enormously enlarged the scope of the theory. We consider any number of points in plano or in solido connected (or not) by lines in pairs in any desired manner and fix upon any condition, such as is implied by the symbols,, >, =<, 4, , as affecting any pair of points so connected. Thus in ordinary unipartite partition we have to solve in integers such a system as , az + b 3 + c3 + y one factor appearing at each point of the lattice. In general, partition problems present themselves which depend upon the solution of a number of simultaneous relations in integers of the form the coefficients λ being given positive or negative integers, and in some cases the generating function has been determined in a form which exhibits the fundamental solutions of the problems from which all other solutions are derivable by addition. (See MacMahon, Phil. Trans. R.S. vol. cxcii. (1899), pp. 351-401; and Trans. Camb. Phil. Soc. vol. xviii. (1899), pp. 12–34.) The number of distributions of n objects (P1P2P3...) into parcels (m) is the coefficient of bm (P1P2P3...)x" in the development of the fraction. and picking out the coefficient of bm xn we find Eh, h h .... ti tą tз where Στ=η, Στί=n. The quantities h are symmetric functions of the quantities a, ß, Y,... which in simple cases can be calculated without difficulty, and then the distribution function can be formed. Ex. gr.-Required the enumeration of the partitions of all multipartite numbers (P1P2P, ...) into exactly two parts. We find and paying attention to the fact that in the expression of h2, the term his absent when r is uneven, the law is clear. The the descending order of magnitude of part being maintained along generating function is Taking h2x2+hòh ̧ï3 + (h4+h2)x2 + (h ̧h2+hgh2)x+(h ̧+2h ̧h2) x® | and the law by which the operation is performed upon the product shows that the solutions of the given problem are enumer+(hol+lgh,+hạng)x +(kg+2hh+h+ ated by the number A, and that the process of operation actually represents each solution. 2 h ̧+hq=h ̧+ {(2)+(12)}2 =2(4)+3(31)+4(22)+5(212)+7(14), ... the term 5(212) indicates that objects such as a, a, b, c can be partitioned in five ways into two parts. These are ala, b, c ; bla, a, c; cja, a, b; a, a|b, c; a, bla, c. The function hys has been studied. (See MacMahon, Proc. Lond. Math. Soc. vol. xix.) Putting x equal to unity, the function may be written (h2+hs + he + ...)(1 + h1 + h2+h+h+...), a convenient formula. The method of Differential Operators, of wide application to problems of combinatorial analysis, has for its leading idea the designing of a function and of Method of a differential operator, so that when the operaDifferential tor is performed upon the function a number Operators. is reached which enumerates the solutions of the given problem. Generally speaking, the problems considered are such as are connected with lattices, or that it is possible to connect with lattices. and differentiating we obtain a sum of n terms by striking out an x from the product in all possible ways. Fixing upon any one of these terms, say x.f.x.x...., we again operate with d by striking out an x in all possible ways, and one of the terms so reached is x.‡.x..x..... Fixing upon this term, and again operating and continuing the process, we finally arrive at one solution of the problem, which (taking say n=4) may be said to be in correspondence with the operator diagram— the number in each row of compartments denoting an operation of dr. Hence the permutation problem is equivalent to that of placing n units in the compartments of a square lattice of order n in such manner that each row and each column contains a single unit. Observe that the method not only enumerates, but also gives a process by which each solution is actually formed. The same problem is that of placing n Rooks upon a chess-board of n compartments, so that no Rook can be captured by any other Rook. Regarding these elementary remarks as introductory, we proceed to give some typical examples of the method. Take a lattice of m columns and n rows, and consider the problem of placing units in the compartments in such wise that the sth column shall contain λ, units (s=1, 2, 3,... m), and the tth row Pe units (t=1, 2, 3,... n). Writing 1+a1x+α2x2+ +. =(1+a1x)(1+a ̧x)(1 +αçx)... 1 P! ... ... and Dp==(α2+ada2+a2da3+...)”, the multiplication being symbolic, so that D, is an operator of order p, the function is ወአአአ “ ...” and the operator Dp ̧DD ... D2 The number DD... Daλ‚aλз P2 am enumerates the solutions. For the mode of operation of D, upon a product reference must be made to the section on "Differential Operators" in the article ALGEBRAIC FORMS. Writing 1 1 viz., every solution of the problem. Observe that transposition of the diagrams furnishes a proof of the simplest of the laws of symmetry in the theory of Symmetric Functions. For the next example we have a similar problem, but no restriction is placed upon the magnitude of the numbers which may appear in the compartments. The function is now ha2 hag... ham ham being the homogeneous product sum of the quantities a, of order λ. The operator is as before Dr Dr2... Dpm and the solutions are enumerated by Dr Dr2 Dp Putting as before λ=3, λ=2, A3=1, P1=2, P2=2, P3=1, P4=1, the reader will have no difficulty in constructing the diagrams of the eighteen solutions. The next and last example of a multitude that might be given shows the extraordinary power of the method by solving the famous problem of the "Latin Square," which for hundreds of years had proved beyond the powers of mathematicians. The problem consists in placing n letters a, b, c,. ...n in the compartments of a square lattice of n2 compartments, no compartment being empty, so that no letter occurs twice either in the same row or in the same column. The function is here AUTHORITIES. - MACMAHON. "Combinatory Analysis: A Review of the Present State of Knowledge," Proceedings London Mathematical Society, vol. xxviii. London, 1897. Here will be found a bibliography of the Theory of Partitions.-WHITWORTH. Choice and Chance.-Lucas. Théorie des Nombres. Paris, 1891. -CAYLEY. Collected Mathematical Papers, Cambridge, 1898, vol. ii. p. 419; vol. iii. pp. 36, 37; vol. iv. pp. 166-70; vol. v. pp. 62-65, 617; vol. vii. p. 575; vol. ix. pp. 480-83; vol. x. pp. 16, 38, 611; vol. xi. pp. 61, 62, 357-64, 589-91; vol. xii. pp. 217-19, 273-74; vol. xiii. pp. 47, 93-113, 269.-SYLVESTER. American Journal of Mathematics, vol. v. pp. 119, 251.—MACMAHON. Proceedings London Mathematical Society, vol. xix. p. 228 et seq.; Phil. Trans. Royal Society of London, vol. clxxxiv. pp. 835-901; vol. clxxxv. pp. 111-60; vol. clxxxvii. pp. 619-73; vol. cxcii. pp. 351-401; Trans. Camb. Phil. Soc. vol. xvi. pp. 262-90. (P. A. M.) Comets. All comets move in orbits that are conic sections-ellipses, parabolas, or hyperbolas. The periodic comets move in elliptic orbits, and are usually seen at more than one return. Non-periodic comets move in parabolas (or in hyperbolas), and are seen at only one return. comets of each calendar year are provisionally designated as 1895 A, 1895 B, 1895 C, &c., the letters A, B, C, &c. indicating the order of discovery. The name of the dis The |