THE UN IV ER SIT Y OF MI CHI GAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Mathematics A COMBINATORIAL METHOD FOR PRODUCTS OF TWO MULTIPLE i-STATISTICS WITH SOME GENERAL FORMULAE P.,'. "Dwyer D. S. Tracy ORA. Project.3o4640o under contract with: NATIONAL SCIENCE FOUNDATION GRANT G-18870 WASHINGTON, D.C. Also circulated as an Office of Naval Research Technical Report administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR June 1962

NOTE The research of D. S. Tracy was supported by the Office of Naval Research under Contract No. Nonr 1224(41), administered as ORA Project 04597.

TABLE OF CONTENTS Page LIST OF TABLES v 1. INTRODUCTION AND SUMMARY 1 2. NOTATION AND BASIC MATERIAL 3 5. THE DIRECT METHOD USING ARRAYS 7 4. FURTHER CONDENSATION OF THE DIRECT METHOD 13 5. BACKGROUND FOR A COMBINATORIAL METHOD 15 6. SOME GENERAL THEORY 21 7. THE STEPS OF THE GENERAL METHOD WITH ILLUSTRATION 25 8. ALGEBRAIC COEFFICIENTS 29 9. SOME GENERAL FORMULAE 37 REFERENCES 53 iii

LIST OF TABLES Table Page I. An Illustration of the Direct Method Using Arrays 9 II. Calculation of k21k2 Using Arrays 13 III. k21k2 With Use of Distinct Units 16 IV. Condensed Direct Method for kplp2k2 18 V. Combinatorial Method for kplp2k3 26 V~~~~~~2

I e INTRiO DUCTTON AND SUMbMARY Wishart has applied [1952a] and Kendall has justified [1952] the application of a combinatorial method to products of -statistics. This combinatorial method is, with appropriate modification, that introduced by Fisher [19291 and formalized by Kendall [1940a], [1940b], [1940c]. But no one has shown how a combinatorial method can be applied to products of multiple - statistics such as-, lQ 2 and i,i. Wishart obtained formulae for such products for all cases throug the 6th order [1952a] by algebraic manipulation of the results for the products of the. -statistics. Tukey has suggested E1956] that the products can be obtained by direct calculation and has provided certain principles and tabular aids which are useful when the product consists of two factors. As illustrations, he has provided the details for the direct calculation of ADAA and'( i ~ As opposed to the algebraic method and the direct method of calculation of formulae for products of multiple A -statistics, there is need for a combinatorial method. This paper not only provides a combinatorial method for products of two multiple - -statistics but also presents general formulae resulting from the application of the method. An advantage of a combinatorial method is that it concentrates on the essential calculatiorn without demanding a lot of superfluous writing as in the algebraic method and with the direct method, A combinatorial method might also be considered superior to the other methods (a) if it expresses the results in a systematic form so that there is reasonable assurance that no term will be missed, and (b) if it is adaptable to the expression of general formulae such as (+,. H.i, *i' e2, etc. The purpose of this paper is to provide the funrdamnental basis for such a combinatorial method, The developmental plan of the paper is similar to that of Fisher [1929] in which the direct method is transformed, by a suitable notation and argument, to a combinatorial method, 1~

2, NOTATION AND BASIC MATERIAL We use a notation which, in general, is similar to the usage of Fisher [1929], Irwin and Kendall [1944], Kendall [1940a, b, c]; [1952], Tukey [1954], Wishart [1952a], [1952b], Abdel-Aty [1954], Barton, David, and Fix [1960], Barton and David [1961]. We denote the sample size by n and the finite population size by N. We also consider an infinite population of which the finite population may be considered to be a sample of size N. Then 4 represents the H k -statistic of the sample, kt the corresponding value for the finite population and X the t6 cumulant for the infinite population. The corresponding moment (about an arbitrary origin) of the infinite population is Ai. We use the sample augmented symmetric functions [Kendall and Stuart, 1958] 7- Xt X x P XE x k and their symmetric means [Tiakey, 1956 p. 38] <f,> = n n-i)(n-I) (2.1) Following Tukey [1956, p. 38], these averages may be referred to as angle brackets or brackets, Now a basic theorem of both old and new finite sampling theory [Dwyer, 1938, p. 112], [Thkey, 1950, p. 504] is that / ~-r.. ><-. NU (2.2) 3

so that, in the new notation, the expected value of the sample bracket is the corresponding population bracket. If the sampling is from an infinite population, or from a finite population with replacement, we have at once ~E <+l~~~~l~,+ E( -= ) ) Ech ~ I (2.3) where the I's are moments about the origin. The sample bracket then is both the estimate of the corresponding finite population bracket and of the corresponding moment product for the infinite population. The methods and formulae of this paper feature a combinatorial coefficient for a partition of )- which is the number of ways that the distinct units of f may be collected into distinct parcels described by the specified partition of ). For example, the combinatorial coefficient of the partition 22 is 3. The general formula for the combinatorial coefficient of the 1 part partition p'... gf is which features the A different parts of the partition rather than the ~ parts. In the analysis below it is the number of parts rather than the number of different parts which is important, so with.4 - f we use ( J,, t,..., )* or ( ~, 2... ft ) to indicate the partition coefficient. Thus (2,21,1) 2t (2 11) _5 2 t! In this notation, the formula for cumulants in terms of moments [Kendall and Stuart, 1958, p. 70] appears as We- X 2 (-H) (to! (+, -*+s)r, pd ~ te (2.4) where the second summation applies to every $ part partition of. *The ( i..) is adapted from a common notation for the binomial coefficient. For two-part partitions,'the partition coefficients are the binomial coefficients except when p, =A.

Following Fisher [1929, p. 203] we define At to be sample functions such that E(g*).- )-. Then (2.3) and (2.4) give where 2 holds for all partitions. Thus * is defined in terms of partition brackets, partition coefficients and number of partition parts. It is well-known [Fisher, 1929], [Kendall and Stuart, 1958, p. 282] that the value of i-, >Ji is independent of the choice of origin. The multiple 4 -statistics* are designed to have the basic property of being estimators of products of cumulalats [Dressel, 1940]. We follow Tukey [1956, p. 52] in defining them by a symbolic multiplication of the i's in which conventional products of brackets are replaced by brackets enclosing the product factors. Thus 2. Z 2<22.>- 2.<211) ~-+- <JI, and in general using (2.5) with t4, the number of parts of a partition of ~ -9<A F smt etd e lcmnto -_>) where the first summation extends over all combinations of partitions of,, partitions of 1i, etc. This expresses the multiple - -statistic in terms of combinatorial coefficients and brackets and is essentially the same formula as that given by Wishart [1952a, p. 1]. It follows at once that *'Also called generalized 4 -statistics [Wishart, 1952a], polykays [Tukey, 1956], and -statistics [Kendall and Stuart, 1958],

so {,I.. is an unbiased estimate of K,..L. ~ Also,,)~ ()Lt'4 )(-J' -'' ) 2' (2.7) and this is just fX~... by virtue of (2.4). So {... is an unbiased estimate of p, ~.....1 An important property of $:... is that it is independent of the location of the origin when each st script is greater than unity [Tukey, 1956, p. 42].

3. THE DIRECT METHOD USING ARRAYS The objective is to provide formulae for products of multiple' -statistics in terms of linear functions of such statistics. Then expectation or estimation formulae, with N either finite or infinite, are immediately available. The direct method consists in (a) expressing each multiple i-statistic as a linear function of brackets using (2.6), (b) multiplying out the brackets and (c) converting the resultant brackets to multiple & -statistics. For example, the first step in obtaining Zk*2. is q&5 k= f<r ~.<tJ~JL42~-zIJ'] (3-1) The second step consists in multiplying the brackets. Thus 42\)( L - = 4))> 3)+ 1 <3). +1 since A A ot $ 4 pi S I'd i as shown in the bracket or >,-coefficient row of Table I. The n-coefficient of the bracket is obtained by dividing the number of terms in the bracket by the product of the numbers of terms in the brackets whose product is being formed. Thus the n-coefficient of <212> is (el)(,-2 ~ [ X VI-)lln] - n a. Tukey has provided a table [1956, p. 47] to assist in this. We propose the use of arrays, similar to those introduced by Fisher [1929] and used by Wishart [1952a], for indicating the results of the second step. The general formula for the n-coefficient of any P -rowed array in the expansion of *,z ~..'.- is )(- where ~ is the total number of parts of the partitions of the ~ and 6 is the total number of parts of the partitions of the 1 o The brackets from 21 are placed in the first column, those from 2 in the second, and all possible pairings of subscripts, except for permutations by rows, are recorded. Thus the terms in the product <21>< 2> are given by 7

22t- 4 20o2 20 2 10 1 12j3 101 0212 with n-coefficients of l/n, l/n, (n-2yn, resepctively, and with the resulting brackets indicated by the marginal column. The arrays resulting from (3.1) are shown in Table I. In general the arrays appear in the order indicated by the expansion of (3.1) except that, for convenience in the later steps, they are grouped according to the number of rows. The coefficient, obtained from (3.1), is shown in the row directly below the arrays. To avoid extensive repetition, equivalent arrays resulting from the permutations of the second column have been grouped together and a compensatory combinatorial coefficient supplied in the row so labeled. The n-coefficient is obtained in the manner described above or by Tukey's table 11956, p. 47]. The product of these coefficients is a coefficient of the bracket indicated by the marginal column. There may be more than one array leading to the same bracket. The result after the first two steps of the direct method is I I+ <32,> - -1- 2(.22 ) (uK I I:l 1 AZ Y, tn -,)'n _L~(,,-0 d- 3> These results are equivalent to those obtained by Tukey [1956, p. 471 by the direct algebraic method though, since he does not use arrays, the coefficient of a specified array cannot be identified in his results. In the direct method using arrays, we do not collect the coefficients of arrays having the same marginal partition (bracket) at this stage, but continue with the development by examining the contribution of each individual array. The third step in the derivation calls for the expansion of the various brackets in terms of multiple *-statistics. Tables are available [Tukey, 1956, p. 44], [Abdel-Aty, 1954], [David and Kendall, 1949] for assisting in this. Instead of using these, we use the device [Kendall, 1952, p. 15] of introducing the parent cumulants and obtaining the final formula by estimation. We can take the expectation of the results in terms of brackets by (2.3) to obtain equivalent results in terms of Ha's. In our example, for instance, the results become 1 i ] - I(, iZ) 2 E Aq 4-yliirlI ~- r-r

TABLE I AN ILLUSTRATION OF THE DIRECT METHOD USING ARRAYS k2k2 = [< 21 > -< 111 >] [< 2 > - < 11>] = < 21 >< 2 > - < 21 >< l > - < 111 >< 2 > + < 111 > < 11 > 221 4 20 2 2 321 21 3 12 3 20 2 20 2 112 20 2 10 1 11 2 101 10 1 12 3 11 2 10 1 10 1 10 1 11 2 112 10 1 10 1 101 101 Arrays ||01 1 10 1 02 2 01 1 101 1 0 1 10 1 10 101 01 1 02 2 01 1 01 1 011 Formula Coeff. 1 1 -1 -1 -1 1 -1 1 -1 -1 1 1 Comb. Coeff. 1 1 2 2 3 1 2 6 1 1 6 1 -Coeff. |~1 1 1 n-2 1 n-2 n-2 1 (n-2)(n-3) n-3 n-3 (n-) (n-4) n n n(n-1) n(n-1) n n n(n-1) n(n-1) n(n-1) n n(n-1) n(n-1) racket or |1 1 -2 -2(n-2) -3 n-2 -2(n-2) 6 -(n-2)(n-3) -n-3 6(n-3) (n- (n-4) ~O /~~~ -Coeff. - ---- \ >-Coeff. |n n n(n-1) n(n-1) n n n(n-1) n(n-1) n(n-1) n n(n-1) n(n-) 11 2 2 1 2 1 1 1 1 1 1 2 1 1 2 1 1 1 1 2 1 5 1 1 2 Transformation 1 1 2 Coefficient 1 1 1 1 1 1 1 1 2 1 11 11 1~~~ 1 1 -2 2 or,-Coeff. n - 0 1 0 2 0 0 0 n n n(n-1) n-i0 0

Then we can expand the -I's in terms of the'' s and take estimates of each side to obtain the desired formula, The real task is the one of changing from IL's to A's. In the direct method the usual formulae [Kendall and Stuart, 1958, p. 68] can be used for changing from e's to A's. In general, except for the most trivial cases, the algebra is extensive though it can be reduced somewhat by use of modulo unit parts [Tukey, 1956]. In adapting the transformation from's to ~'s using arrays, we need to distinguish the two components of the A.'s corresponding to the two columns of the arrays. This can be done by using a multipartite notation. Thus the r/ of the first row of the first array of Table I is treated as the bipartite By. Then the expansion in terms of bipartite )'s is tL' -;2 +2 4(1 X2. +2 X4 z > )2. XZo ~oz + Z ski 4- KtO X+ 1 Kgo 4 -X2X130 4+j4 >(ik, to>S XMX',K, + (3.2) and the transform of /2zto becomes the right side of (3.2) multiplied by -lKo ~ The paired subscripts identify the rows of the different arrays of Table I. The coefficients of (3.2) are then written in the row under the bracket coefficients. Similar transformation coefficients for the /I's indicated by the other arrays are written in the rows below. Coefficients from the unipartite expansions are available for checking. The calculation of the X -coefficient corresponding to each array is then direct. We simply multiply the transformation coefficient (as indicated in each column) by the L.-coefficient (as indicated by the column of the diagonal term) and form the sum. From the results in Table I we see that E(R,+K,) = ),+, - x )K} >~, + - i-X*This expansion may be obtained from the multipartite a'iImi: X',,,+ - KODOI KI 00a + fly> RA'ON'lt4,'ooio - 1Ol 0o OJ0 4. 1OW0 - by combining the first pair of subscripts to form a new first subscript and the second pair of subscripts to form a new second subscript. 10

so that, taking estimates, we have -a a. = |f3 r) - j l ~{r;)v3 + 41 t - Wishart [1952a] and Tukey [1956] have written the result in the form,1_l = n4 41 + ( Arn-l ) ( <}_ )4- 1, Formula (3.3) is in good form for approximation with large n and it does show the contribution of each array. The illustration in Table I presents the rather complete details of the direct method using arrays. The establishment of general principles which are applicable to the contributions of a given array makes possible considerable further condensation and the development of a true combinatorial method. 11

4. FURTHER CONDENSATION OF THE DIRECT METHOD Examination of Table I shows that the -_coefficient of every array having a marginal partition with two or more unit parts is zero. This is in agreement with Tukey's result [1956] which states that the coefficient of every X... having more unit subscripts than the set of original subscripts is zero. We now use Tukey's result to condense the results of Table I. The process is in a sense equivalent to Tukey's algebraic direct development in which he used modulo unit parts [1956, p. 43]. The amount of work is greatly shortened for this problem in that no entry in any column corresponding to an array with more than one marginal unit subscript need be computed. The condensed calculation is shown in Table II. TABLE II CALCULATION OF 4 2l1 USING ARRAYS (Marginal Partitions With More Than One Unit Subscript Omitted),,;, = [<21>2 - (<111][2 > - <11 >] 22 4 20 2 21 13 20 2 20 2 11 2 Array 10 1 12 3 11 2 10 1 11 2 11 2 02 2 01 1 10 1 Formula Coeff. 1 1 -1- 1 -1 1 Comb. Coeff. 1 1 2 1 2 6 n-Coeff. 1 1 n-2 n-2 1 n n n(n-l) n n(n-l) n(n-1) |-Coeff. | 1 1 -2 n-2 -2(n-2) 6 n n n(n-1) n n(n-1) n(n-1) 1 1 2 1 1 2 1 1 2 Separations Coefficient 1 |&-Coeff. | 1 1 -2 21 n n n(n-l) n-l 13

The results are those of Table I. It can be seen from Table I, and it is very noticeable in Table II, that the — coefficient of the 20 term is 01 also zero. This fact is not covered by Tukey's rule but it does follow from our rule of proper parts, established in Section 8, that the coefficient is zero for any array which has at least one row with a simple non-zero element which is a proper part* of a partition of some integer subscript. Since the 1 in the third row of the partition above is a proper part of the 2, the coefficient is zero and the array need not be considered. Tukey's rule as applied to array coefficients follows as a corollary of this general rule since any additional unit subscript must come from a row with a single proper unit part. In more general problems, the condensation resulting from the application of rule of proper parts is extensive. The array i&, though having a combinatorial coefficient of 6, has a -coefficient of only 2/(n-1) because only two of the six arrays, resulting from the matching of the unit parts of 2 in 2 with unit parts of 21, do not have rows with unit proper parts. Thus the six arrays obtained by permuting the unit elements of the second column are not really equivalent. A true combinatorial method in which each array makes a fixed contribution to the total result needs a more precise notation and appropriate modifications. *A proper part of a partition of an integer is any positive integral value less than the integer,

5. BACKGROUND FOR A COMBINATORIAL METHOD We first introduce a different terminology for the transformation coefficients. The various arrays which are obtained by separating the elements of the rows of a given array into more rows are called the separations [Fisher, 1929] of the given array. The transformation coefficient is then the number of ways the elements of the rows of a given array may be separated to form a new array. This number may be called a separations coefficient as indicated in Table II. Alternately the columns of Table I (and Table II) show all the arrays which have a given array as a separation together with the number of ways the separation can be made. The arrays represented by the columnar entries may be called amalgamations which are obtained by adding the rows of the given array in all possible ways. More specifically the arrays of Table I and Table II may be called conditional amalgamations since the rows may be amalgamated only to form arrays which are possible in accord with the conditions of the problem. In the expansion of k,,, for example, no 3 may appear so it is possible to amalgamate the rows in all possible ways except that no 3 may appear in the first column. These are just the amalgamations revealed by Table I and Table II. A significant part of the work deals with the calculation of the separations coefficient to be associated with each amalgamation. The calculation of this coefficient can be eliminated if the arrays are so defined that there is just one way in which one array can be separated to form another specific array. This can be achieved by considering elements of arrays composed of distinct units. Thus in 4., we let e,, e. be the unit elements of 2 and e3 the unit element 1. In 4) we use et, es to be the unit elements of 2. Then the array 11, with combinatorial coefficient 2, represents either of the arrays 2-I - Gae e2 z en, e.3 em Each of these arrays is unique and can be separated to form another unique array in only one way. Hence every non-zero separations coefficient is 1. The number of distinct arrays in Table II (the sum of the combinatorial coefficients) neglecting the penultimate array (which has a coefficient zero) is 11. Now four of the last six have a coefficient of zero since the proper part E., ez, e, or es appears alone in a row. Hence there are but 7 arrays with distinct units having non-zero coefficients. These are shown in Table III. The algebra is simple since each conditional amalgamation has unity as coefficient. The results of equivalent arrays of distinct units are then collected to obtain the previous results. 15

TABLE III ~l~4 WITH USE OF DISTINCT UNITS el+e2 e4+e5 el+e2 0 el+e2 e4 el+e2 e5 el+e2 0 el e4 el e Array e3 0 e3 e4+e5 e3 e5 e3 e4 e3 0 e2 e5 e2 e 0 e4+e5 e3 0 e3 0 Formula Coeff. 1 1 -1 -1 1 1 1 n-Coeff. 1 1 1 n-2 1 1 n n n(n-1) n(n-1) n n(n-1) n(n-1 1 1 - 1 - 1 n-2 1 1 v |~-C eff. | n n n(n-l) n(n-l) n n(n-l) n(n1 1 1 1 1 1 1 Separations 1 Coefficient 1 1,'R -Coefficient 1 1 - 1 - 1 1 1 (distinct units) n n n(n-1) n(n-1) 1 n-l n-l

With permutations of the elements of the second column, the first two arrays, the next two arrays, and the last two arrays constitute three distinct array types with the same A -coefficients. Then the condensed direct method using arrays applied to the four array types gives - ~ +20, (.)..-+1-l z'- - il- " I+ I J where the + in the subscript indicates the sum of the &'s with sums of permuted subscripts prior to the;. Thus With suitable notation it is not much more difficult to obtain a formula for 4, with this condensed direct method using arrays. We have L <~2,-<lJ Using the rule of proper parts, the only bracket products producing array types with non-vanishing coefficients are given by This can be written + 2 T 2,;, f2 ~ >I)> where T <i, *2 /' > symbolizes ( hil12) equivalent brackets. With this method, the algebraic coefficient for each array type is determined and then multiplied by the type coefficient. 17

The separations (amalgamations) coefficient need not be recorded since it is unity. We now absorb the sign and the factorials in the n-coefficient and have the general formula n-coefficient = ()! T! (e) (5.1) The algebraic coefficient of the array type is obtained by adding the n-coefficients of the array type and all its conditional amalgamations. Thus the algebraic coefficient of, I, with Z, 2 the only conditional amalgamation, is () + 1_ TABLE IV CONDENSED DIRECT METHOD FOR Ip ~" I,2,O 1 1 Array Type, O - O 0 z 1 +,z1 p1 1 0 2 _ _ _ -fPo 1 1 i- i o 21 g. Coeff. 1 n n(n-1) n-l n-l omb. Coeff. 1 1 1 (t2j ) & -Coeff. i 1 -l n -( 2 2 ) I n n(n-1) - - The result in terms of the I's associated with array types is then Z' _ 1Pp,- Y) on C,18,, -,

and the more explicit formula is 2- -A 42 + 2. Z2 Adlit - \ { + h + m p, > pr- 2 tn (-A l) p,+ 1) 1 fI i|7 vr CW)~rcp l~) % _ ( filt hi Values of A and -X can be substituted. Some collection of the resultant terms is commonly possible. Thus with H, = 4 and t2 = 2,,424= i + n it +2344 - + - & j 4- ) n-l No restriction has been placed on, or js (except, of course, that they are positive integers). The formula simplifies somewhat when one of them, say i, is 1, since 1 has no 2-part partitions and the last term vanishes. The formula is even applicable to the case with i = 0 if we drop the -2. from all terms containing;-! as a subscript, and drop all terms containing other functions of tz as subscripts. Thus 2 = 1, p,+2 n- ()9 19

6. SOME GENERAL THEORY Using bracket types we can write (2.6) with,:. >0 as { - >(-') T.,' Similarly, so, Array types based on (6.1) are used. The algebraic coefficient of each one of them must be multiplied by the product of the partition coefficients, ( i t - x)(}, IA'),1.. I,(J 6 ('... to obtain the k -coefficient of the array type. Formula (6.1) gives the product expansion in terms of every possible array type which results from the partitions of A and. Moreover the formula coefficient, aside from It-(&! ), is unity for every array type in the complete expansion. The values of () are absorbed in the n-coefficient in calculating the algebraic coefficient. Now consider any array type with A in the first column and,'' j'i in the second. Suppose there are rows in the array type. Then the n-coefficient for the array type, with the t(i afla) absorbed, is (see (5.1)) 21

n-coefficient =' (6.2) It is apparent at once that this modified n-coefficient is a function of the I's and /'Is and not of the individual +' s and V's. This means that different numerical values can be substituted for the various Ijp's and's without changing the n-coefficient as long as the pattern is' not changed. Some important rules follow. RULE I. RULE FOR ALGEBRAIC COEFFICIENT OF ARRAY TYPE The algebraic coefficient of the array type is obtained by adding the n-coefficient of the array type and those of all its conditional amalgamations. This rule results from the facts that (a) every conditional amalgamation of each array type appears in (6.1) with coefficient of 1, aside from { (ia) ( ), and (b) the expansion of each array type in terms of its separations has unit coefficients as illustrated by Table III using distinct units. RULE II. PATTERN RULE Array types with the same pattern have the same algebraic coefficient no matter what the values of the original I's and I's. Array types have the same pattern when the various groups of partition parts correspond in location. Thus the array types I,, 2 122-2 and i,, = $, a0 in the expansion of fe lX+z and the array type Ii 4 te e 3 in the expansion of cs 472 have the same pattern. The algebraic coefficient is l/n(n-2) in each case since the only conditional amalgamation results from adding the first two rows. Rule II follows immediately from Rule I. 22

RULE IIio RULE OF PROIPER'-:.K'S The algebraic coefficient is zero for every array type in which there is at least one row in which a proper part appears alone. By the pattern rule, the algebraic coefficient is the same no matter what the'values of ~.~, and, and the partition elements in the pattercnare. Consider the case in which,/; and X; are all greater than i and take the proper part appearing alone in a row to be unity, Then each of the ~... terms arising from the array type has a unit subscript. Since the product expansion with t. >I, 5 >I does not have any,4~oa term with unit subscript, the k -coefficiert must be zero,* Now the combinatorial coefficients are not zero, so it follows that the algebraic coefficient for the array type is zero, These rules provide the basis of the comb inatorial method for the products of two multiple #-statistics as developed in the sections below. The theory of this section is immediately extendable to multiple products of multiple i-statistics, and the rules stated above hold for general products. As suggested above, the rule of proper parts, as applied to arrays, gives Tukey's rule as a special case since any unit subscript over and above the unit subscripts of the original set must result from the appearance of a unit proper part as a single element of a row-, But the rule of proper parts is much more general, as it commonly eliminates many more array types. The theory and rules above are in a sense generalizations of some of the Wishart (modified Fisher) rules for arrays of in which partitions are replaced by Xis since only partitions of can occur in the first column, partitions of c in the second, etco, Thus all ~/ vanish except Yl and all A3 except., and the general rule for n-coefficient becomes n-coefficient = -- --------- 71711) n (n, ) (6-3) All conditional amalgamations become amalgamations and the rule of proper parts becomes "The coefficient is zero for every array in which an X is the only entry in the row but not the only one in the column. " This rule appears to be more general than the Wishart recommendation [1952a, po 4] which is somewhat vague but explicitly applies to patterns with single unit proper parts. *Since the algebraic coefficient is the same for a nmultiple infinity of values of and q, it follow s that the contribution of every array is in general unique so that the coefficient of every - with unit subscript must vanish, 23

I

7. THE STEPS OF THE GENERAL METHOD WITH ILLUSTRATION The general method can now be stated. 1. Write each multiple & -statistic of the product in terms of bracket types as indicated by (6o1). 2. List all possible arrangements of the products of bracket types in which the bracket type components of the first factor are placed in the first column, those of the second factor in the second column, etc., to form the array types. In so doing ignore any array type which has a proper part as a single non-zero element of a row. 3. Compute the combinatorial coefficient for the array type by forming the product of all combinatorial coefficients associated with every partition appearing in the array type. 4. Compute the algebraic coefficient for each array type as indicated in the previous section. 5. Multiply the algebraic coefficient by the combinatorial coefficient to obtain the A -coefficient for each array type. The listing of the coefficient in the column for the -term gives the result in combinatorial form, More explicitly, 6. Write the formula for the sums of the products of the k-coefficients and the -terms. If still more explicit form is desired, 7o Expand each of the A-terms to feature explicit A' So As an illustration we apply the method to A The first five steps are shown in Table Vo 25

TABLE V COMBINATORIAL METHOD FOR 1p p2 1PP2 = < plP2 > - ET < PllPl2P2 > - < PlP2 > + T <PP1P1P22 > + T Pl > + -.. (1) PiP2 3 = < 3 > - < 21 > + 2T < 111 > P1 3 P1 0 Pi 2 P11 2 Pi 0 P11 Pi 1 Pl 1 P11 P2 0 P2 0 P2 1 P12 1 P21 2 P12 1 P21 1 P12 1 P21 1 (2) Array Type 0 3 P2 0 P22 1 P2 1 P22 i P13 1 P22 1 P2 0 P23 1 0> (3) Comb. Coeff. 1 1 3 3(PllPl2) 3(P21P22) (PllPl2) (P21P22) (PllPl2Pl3) (P2Pm2P23) 1 -1 1 1 -1 -1 n fn (4) Alg. Coeff. n4) Alg. Coeff. n(n-1) n-1 n-1 (n-l)(n-2) (n-1)(n-2) (n-l)n-l)(n-2) (n)n2) f 1 31 1 -3 | 3(PIPlP2) 3(P21P22) -(PllPl2) -(P21P22) n(pllp2p3) n(P21Pn 22P23 $5n-Coeff. n(n-1) n-1 n-l (n-i) (n-2) (n-l)(n-2) (n-l)(n-2) (n-l)(n-2)

Step 6 gives us,ff_+ ) 4 -,)3-h: + 2- n2> (+ 210 n - and Step 7 gives +2 3 ri3 (I 3 - + r+ - ((: () 2- | 3 I 27

As a special case consider the value of Z2123 which is needed in the estimation of M (3 2<) )= EZ (- K3)(-_ K)2 I. We get at once A satisfactory combinatorial method needs rules which give the algebraic coefficient so that it need not be computed anew for each array type. The remainder of this paper is devoted, for the case of products of two factors, (a) to the determination of the algebraic coefficients for groups of array types, and (b) to the listing of general formulae resulting from the application of this combinatorial method. 28

8. ALGEBRAIC COEFFICIENTS A useful rule is the rule of extended array types. We define an extended array type to be one which consists of an initial array type plus additioo-al rows in which elements are.t~,' s (but not proper -arts of' I's) matched 7.-ith zeros, or I's matched with zeros. Then we have. RULJE IV. RULE OF EXTENDED ARRAY TYPES The algebraic coefficiellt of an extended array type is equal to that of the initial array type. This rule is very useful.le appropriate cases in simplifying the calculation of the algebraic coefficient since one may cross out any row which has a ~, term or a., term (which is not a proper part) in a row with a zero. For example, the algebraic coeffi-.:ient of iP't is that of -I: which is l/n(n-l) +l/n - 1/(-l. This rule should be applied after application of the rule of' proper parts which elimni~nates all array types having a single entry in a row which is a proper part. Suppose there are F, rows of the initial array type with both Ah and t entres,; with A entries only, and 1 with J entries only. If the contribution to the n-coefficient of the signs and factorials is indicated by, the value of the n-coefficient is Consider an extended array type which results from the addition of the row 0,j O. Then the contribution of the conditional amalgamations resulting from adding the new row to the initial ones in all possible ways, but not as yet involving any amalgamations of the initial rows, is which reduces to the value of the n-coefficient of the initial array type indicated above. Since this equality describes the relationship between every conditional amalgamation of the initial array type and the corresponding contribution of the augmented array type, it follows that the two algebraic coefficients are the same. A similar argument holds for the addition of the row 0, A;. The result is immediately extendable to the case of more than one row. 29

As a result of the application of the rule of proper parts which eliminates many array types having one or more zeros, and of the rule of extended array types which makes possible the elimination of all rows having zero entries from the remaining array types, we need concern ourselves only with array types having no zero entry which we call reduced array types. Thus the only array types needed in applying the combinatorial method to +y% k (see Table V) are 2t; 2 2w 2,' I' I vI I Il.IL i he A E t2 |2 1 3 I 43 1 (8.1) whose algebraic coefficients are easily computed. The one possible exception is the array type which has a zero in every row. The algebraic coefficient of this array type is 1 as may be seen by eliminating all rows except the first. The algebraic coefficient is then the n-coefficient which is(l/n)(n) = 1. The term Case I is used to identify array types with a single non-zero entry in each row. Additional notation is useful in expressing general formulae for the algebraic coefficients. We collect all the rows which cannot be added to any row, whether they contain proper parts of the'Is and O$'s or not, at the lower part of the reduced array type and indicate this collection of rows by AA (or A). Thus the reduced array type 17f:2 ~lQ (8.2) V'9 /23 can be written Gi't,, where A consists of a= 3 rows. lz tICz A A Now since no row of A can be amalgamated with any other row of the reduced array type, the signed factorial contribution to every conditional amalgamation (of the rows above A), and hence to the algebraic coefficient itself, 30

is the same. This is denoted by CA and is the product of the signed factorials in A excluding all parts of partitions which also have parts in the rows above Ao Thus in the illustration above, CA = -1 since the sign of 1 is related to the other parts above and since the last two elements in the first column are parts of a two part partition. The notation is general enough to include rm.= 0 in which case CA = 1. CA is also 1 when no partitions of new'>; or c[~ appear in A or when the partitions are two-part partitions and there is an even number of them. Case II is used to denote any reduced array type in which no conditional amalgamation is possible. All the rows are included in A. The algebraic coefficient is the n-coefficient. Thus the algebraic coefficient of f12 q2 is (Ai If A does not include any partitions of'; or j, or if only even numbers of two-part partitions appear, as in the illustration, the algebraic coefficient is l/rA In developing notation for more complex situations we let 3- be the number of parts of a partition of appearing above A and j; be the number of parts of - in the (reduced array type. Similarly a is the number of parts of %, appearing above A and S the number of parts of appearing in the reduced array type, Thus in the illustration (8.2), = 2, R, = 39, = 2, = 2, = 2,? =, = 1,, 1. Once the values of CA and ce are determined we need pay no more attention to the elements of A in determining the algebraic coefficient. Specification of these -'s and's enables us to identify extensive groups of reduced array types which are covered by a general formula for the algebraic coefficient. Thus {= R -=, A, = S, I.. and o = 0 identify the P row, two column patterns of Fisher [1929]. Further (o and (X can be used to indicate groups of rows within which amalgamations can be made. Thus 6- (. Z- 22, % > 0 indicate that there is a group of!p, rows which can be amalgamated with each other, a group of to rows which can be similarly amalgamated, and a group of cL rows which cannot be amalgamated. If also K! —, and 5] = fl then there are no parts of -,, nor parts of c,, in A. Of course if at = 0, then R, =, = I1-, and CA = i. General algebraic coefficients are given for the cases indicated below. The derivation features the adding of the combinatorial coefficients for partitions having the same number of parts and transforming to (advancing) dif31

ferences of zero. Thus (31)t C4O) - 4-3 =7 = L z(o~) Case III. = 2 Algebraic coefficient = CA 2 (R,- +!s-f(8.3) This formula is very general and special cases of it are useful in practice. For example it covers the last six of the nine reduced array types of Table V (see (8.1)). The three others are taken care of by the rules for Case I and Case II. Of frequent occurrence is the case in which _ =~ _, The more explicit formula is then Alg. Coeff. = CA (R,-2) i ('".ZQI F~',S,; —,, (8.4) This explicit formula covers four of the nine reduced array types of (8.1). If in addition we have R,:- S 2, then CA (Y —) Alg. Coeff. = (:2) (8.5) with obvious further simplification when CA = 1 and when t = 0. When (, — - = P 3, the more explicit formula is Alg. Coeff. = CA (R,-3! 3 (8.6) If in addition RI, -, we have Alg. Coeff. = CA (8.7) 32

with obvious further simplification when CA = 1 and cA = O. For general p with -,- RI and ~t 51, we have Alg. Coeff. ff = CA Z, (8.8) which, when Q = 0 simplifies to?as given by Fisher [1929, p. 226]. ] Case IV. = In this case the algebraic coefficient becomes PI Y.,-I+ +14 A,.- - U.,(+~,+u: (cf, a(.,) (8.9) More explicit formulae can be written for special cases. Thus when, we have Alg. Coeff. S= CA-?-) Ijin-n-)(t,-)-a)(75-afi~ (8.10) And if, in addition, RI = 51 R, S' 2, we have Alg. Coeff. = C-' ( )- (),) + 1j (8.11) which simplifies to n + 3+}_ when a = O. For general P1, f with A,= I- -RSI St Mlg. Coeff. = 2 (I) <j (8.12)

which simplifies further when c = O. Case V., Case V is in a sense a modification of Case IV if we consider,- _ %+I where 1/:, and j z. The terms in the conditional amalgamations correspond exactly except for the factorial involving ( and 2 which becomes ( R)- _, -, -I + g +! rather than ( R,- I+ a,)) (R,- - 1+ au,) I. Hence the formula is Alg. Coeff. = 2 ZL (F,'/ t, a), 4 (8.13) aI, i as Case VI. (Generalization of Case IV) Alg. Coeff. = 1T i )S — r)! Aia (8. 14) where It Z indicates 21 Case VII. (Generalization of Case V) 1-;:,''t +... i-;.4.. g. Coeff. C (R-,f; - i —~ ~+,, )! (S.-,.c- I+4.4A(.! Alg. Aoef ns__.: _.". f. __) n'R (____ ) ((8.15) "..;! These seven cases and adaptations of them take care of very general situations. Formulae for algebraic coefficients which are more specific but which are general enough for broad classes of reduced array types can be obtained as special cases. These are indicated by the values of, A, F,, S' and (a ~ Unless otherwise specified it is understood that R v, and 5.= XA for A 1 and that all other ~- O and. ~ 34

Case Specification Algebraic Coefficient I All rows cancel. I II The reduced array type is all A. A'7(p III I*)A52),r-2 2 2 A, - I * +, = 3,, -_ 3 _n_ * (.R I 3) 5 25 *~,-2~7 ~~~~(n I)(2)-n-3 *~ =5r ~ =5 m'(r+ r) ~r, =p, P, =13 e (,., —! t(o0) t-=2.,-2, R,- 3, 5,2: I I_ _ 2,- 2,, 2, Ri4 i,,-,,(,o._-2).V' s - 3.2 &3r+ -.43, n2 = _ _____s ___ -,", - Z,,,_ 3,?. =,3 4 +- +1.,.,, *Given essentially by Fisher [19291o 35

Case Spec ific at ion Algebraic Coefficient v t4,' 4X=2 ________ t, 3, -, 3,, — 2,.-,=i- /)(,n _-43~~ ~~, "~ ~~~~''J ~~~~~~ ( )1.'-,' x - - 1,. _4- 2 T~f,-r-~,~.1,~,-, j' 1jr Z~z56,Z

9. SOME GENERAL FORMULAE Some general formulae, obtained by the combinatorial method, are presented in this section. To condense the results, we use symbolic forms for the reduced array types. With I i representing the set -, y-,..., we indicate the group of array types in which any ct, say i,, may appear in a row with any element of f j byj,,j, the group of array types in which j, and p2 may appear by p}t etc. The notation t },is used for the extended array type in which c,, q, appear alone in additional rows. The notation { 9:}.2 symbolizes the array type with %, in a row with some element of { } with an additional row containing c,. Double subscripts indicate partitions. Thus If,,~,,lz indicates an array type in which the two part partitions of l, are added concurrently to two elements of j J and the row for z, is added. An adaptation makes possible the characterization of partitions of an element of j.e The appearance of double subscripts on some t, say'',, indicates that partitions of Si, and not /' itself, appear in the array type. Then we use ih,,4, 2+, 1 cJ,'j to indicate the array type in which the two part partitions of ~, appear with the two part partitions of c1, the other -'s appearing alone. Similarly we use 4 i,,,it. i,11.,2 tI2 to indicate an array type like the previous one with, in addition,.appearing in a row with some /, J- o And f-.i # + 11,,21~:j'-" indicates the extended array type with additional rows of's. The results of the combinatorial method, in this condensed notation, for several general formulae are given below. Some collections of coefficients of array types have been made. Thus the coefficient of +. in the expansion of 4,4 lX is l/n(n-2)+2/n(n-1) (n-2) =(n+l)/n(n-1 n-2) The first formula although well-known, is given for completeness. The results of Table IV are a special case of this. 37

{ 5 - ~ 3 - n ~~" /')( ff 77+ 07 3-) n rj (t (Y) - ) +1t~; l+1 + 1 ( ) ) The results of Table V are a special case of this with the fourth term vanishing. _, ~ _(_ - _ _) ____.. I. -4 (Y)( *This gives, as a very special case, This result has been stated by Barton, David, and Fix [1960, p. 56] for the case of f= even and odd using binomial coefficients. The need for two formulae is avoided by using the combinatorial coefficient C ( 17,). The subscripts of K, ~ in the formula for K4~ Kl, r even, should be +,1 -) L. 1 38

-~iir'... (,Qif f).4) (-'u)(:-> + —) ( l-) r, + U 0)( L)A C I { I1 +'4 -, (~,,,~,i,. )', { - i) I{ u + LA =

"~~~~~~~~~~~~~~~~~~~~~~~.-f-t~ d.." ~~ ~ ~ I?':? I-~~~~C:21)i..J' ) < iY \i r CI- I~~~~i - ~~~~~ fi(Z,... f.-, (.. 6-. A.,, rd cl,~~~~~~1 i CI~~~~ B..~,,::)c (~I? ~~ar r dC d 7~~~~~,-,-.... ~... I~~~~~~~~~~~(...'-,C:-'R (~-'->-~]. V 3-'~~~~~~~~~~~~~~~~~~~~ {Ii7 (k L'I,0' (% ____ - f( (w'.)u "' -~7K I~ I )I-U

"4 44 4 a-VA i -- AINS'- V VI ci -I- -' %~ ~ 1Q~ ~ t i N4~~~~~~~i s C sc h..' -7 t. rt 14; 4- - 4 -1 54 -% Sf39'%x} _ t t:3A f" -Q-'~~~`C~~ "-_t -5; +;~~~~~gi uDp ^ - p 1 > s t " c_2929,.a7~II, s_. %c v -A-, -f.t'0~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~d~l':~' -h~ Ki K c~i'5 -A- j-~EL~L — Y4 in'-4~ i ~r ~c3 *OO

N 4-1 ~~~~~~~~~~ r~~~~~~~~~~~~~~~~~~~~~~~~~~r r'e t% IN"~ ~~~~~I _~~o a t~ t6 M~~~~~~~~~~~~ ~~~~~~~~~~~~~I ~ ~ ~ ~~~~~~~~~~~~~~~~~~~-'.'A C~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~C Jc IN-N - r'~~~~~~'~O set _~ WXJ QP lr W 7+ L,, Le-..)C -- |- P -P.V'4 V~~~4j V\4 ~~~~~~'4 ftl C. I "N t~~~~~ (0 jC v CsA A F 1 Fr>i -i' 4L~L'I ~., +-1I 42 ~/~~~~~~~~~~~~~~, O~~~~~~~~~~~~~C~V;cS ~6~~

- 1- + 1 1 5 -~~~~5 ~~~~t,t M _ M~~~~-'-:4, (A\~d -tS +a $7 ~~~~~~~~~'-~~r +~~~~~~~~)

Ift = ~,we get Special cases are obtained by putting = 2,3,...: 3 n 3 n ln-) n-l 2 as indicated by Barton, David, and Fix [1960]. --' _ {'+ -tr'ol" (' *esg subscr i of p i-n,t f u i n(-,)(,-,.) a:~+, ( -l)(n —2) f- t t

"4 44 4 a-VA i -- AINS'- V VI ci -I- -' %~ ~ 1Q~ ~ t i N4~~~~~~~i s C sc h..' -7 t. rt 14; 4- - 4 -1 54 -% Sf39'%x} _ t t:3A f" -Q-'~~~`C~~ "-_t -5; +;~~~~~gi uDp ^ - p 1 > s t " c_2929,.a7~II, s_. %c v -A-, -f.t'0~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~d~l':~' -h~ Ki K c~i'5 -A- j-~EL~L — Y4 in'-4~ i ~r ~c3 *OO

1+4 f + W e4 j c (HJ.) lr{d',~-', +' 1 +,' "'( ( y, l(%, ~L) X' _-U~-CI Y ecQZ~lld~ I (r-~-~zl Ztt 0+ I,_____ "(+9 ______-o 7 T IL(Z-*)(-.;~5

)LL-hd ~ ~k'ji~tC~ r ~_,,( kV d 4 -1 6 ( -u?'6 ~-~~~~~~Z+, fi *d i't~~~tv~!~ ~ i-~f4G~, ~!d df~1 C(1' r4 r- C4~t a 4- 7 IJ) (Z~ —9z c~)(l- L4) (i 6- LC9@Q - ct) CL ~~~~~~~C1~~~~~~~~~~C rti-(~~~'~~v~~i' -'~i'hrfrllc~ ~~r~ (iI)'< I-" Vv I p~~~~(+ C~# (4/ f " +~ rj~ ~ ~~k~'i,_ i(+') I' I-~~ ----- C' ~ ~ ~ ~~ -' ~ -J~ O ~ 44C

+ 4.'-4 - * T~~~rl -4:-4.4+ -'a -- N + -I~~~~~ 4 — ~ J, 4 N — C4 4~ T -- N - -t.1cl4P )P Il~ 4 41 crl~~~~~ +da 4J -( 4-' r( F.~~~~~S~~; 4 -r *- ~+ T~~ c ~ - - -a-... 4e -s AfAE NJ i,aC ~i~~~~~~~~~i + A~ N ~ ~ -r T5 lf t'N~e'4 t Ar~LIc

~ -t -~ -4C',_,- + 4- ~p~4 -,P-! +'4:.-? - JIc 2 9~~L r-L ~'>'I C / 4 C-4 1A11 — 7se b I; + I~+ C'~~~~ -' -'-I-I + ty) 14- -~~~~~4F- N + + W) A- C\4 -' +- 1 r\ $- +. -~0~ -1 -a ~~~~~~~ ~~~~ +~~~~ +' ~ QI'-;* - **1- C (b t t- Q~~~L- ~ \ ~~~~1 F~~~~~~~~~ *-~- I I ~ IP I I I I'~~b ~ 11~Qe`9t

AtC i11$1 { n, },+}),1'~'n-#9 f "r ( j ), n 4(vt- )(f-;L p~ 3, +Y —4 4t &) 4~I- T Ct -,, r - 1.25YiiVZ)rl4') 3{ 4~~~~~~~~~ + ) fe+' )-I 4- I (+ n(n-l) Y~-) (n -2) (Y -3) +}t)' +1 v-I''; If p = 1, all the partition terms vanish, so, 4.A = --'f I+ -2.+ n(n1 2 n )(2j 21 +II 2 4 2 2 Similarly, compact expressions are easily obtained for 1t -kh and 4 1 f The general formula for (4 ( i' ) is'~ t~ A 4' 1A 4 f1+ - 2 + )4, 2_ 1P 4, -4 -+ (Xt-UL2)A&-(4-2) 4-i +-4 <~(-tI). (Y-vt92~ 3 Y t) (t);r~~, <i al~5, 0 n p') i~i ~(-PXP:)l~-~ a~~~r p:i5;

This section provides formulae for ~X for < finite and 1, Additional formuae for products of two multiple +-statistics can be found by the combinatorial method developed above, While this paper is primarily concerned with products of two multiple -statistics, some of the results (such as the rule of proper parts) hold for multiple products. The establishment of rules for algebraic coefficients for array types with more than two columns, the specification of the resultant combinatorial method, and the presentation of general and specific formulae for multiple products are objectives of our continuing study, 51

REFERENCES Abdel-Aty, S. H. (1954). Tables of generalized -k-statisticso Biometrika, 41, 253-60. Barton, D. E,, and David, Fo N. (1961). The central sampling moments of the mean in samples from a finite population. Biometrika, 48, 199-201. Barton, D. E., David, Fo N., and Fix, E. (1960). The polykays of the natural numbers. Biometrika, 47, 53-59. David, F. No, and Kendall, M. G. (1949) o Tables of symmetric functionsPart I. Biometrika, 36, 431-49, Dressel, P. Lo (1940) Statistical seminvariants and their estimates with particular emphasis on their relation to algebraic invariants. Ann. Math, Statist., 1 33-57. Dwyer, P. S. (1938). On combined expansions of products of symmetric power sums and of sums of symmetric power products with applications to sampling —Part II. Ann, Math. Statist., 9, 97-132. Fisher, R. A. (1929). Moments and product-moments of sampling distributions. Proco London Math. Soc. (2), 30, 199-238o Reprinted in Fisher, R, A. (1950). Contributions to Mathematical Statistics, Wiley, New York. Irwin, J. O., and Kendall, M. G. (1944). Sampling moments of moments for a finite population. Ann, Eugenics, 12, 138-42o Kendall, M. Go. (1940a) Some properties of $-statisticso Ann. Eugenics, 10, 106-11. Kendall, M. Go (1940b), Proof of Fisher's rules for ascertaining the sampling semi-invariants of A-statistics, Ann. Eugenics, 10, 215-22. Kendall, M. G. (194Cc). The derivation of multivariate sampling formulae from univariate formulae by symbolic operation, Ann. Eugenics, 10, 392-402. Kendall, M. G. (1952). Moment-statistics in samples from a finite population. Biometrika, 39, 14-16. Kendall, M. G., and Stuart, A. (1958) The Advanced Theory of Statistics, 1 (three-volume edition). Charles Griffin and Co~, London, 53

REFERENCES (Concluded) Tukey, J. W. (1950). Some sampling simplified. J. Amer. Statist. Assoc., 45, 501-19. Tukey, J. W. (1956). Keeping moment-like sampling computations simple. Ann. Math. Statist., 27, 37-54. Wishart, J. (1952a). Moment coefficients of the {-statistics in samples from a finite population. Biometrika, 39, 1-13. Wishart, J. (1952b). The combinatorial development of the cumulants of the' -statistics. Trabajos Estadist., 3, 13-26. 54

UNIVERSITY OF MICHIGAN 3 9015 02841 3196