On an Extension of Arbogast's Method of Derivations

II. On an Extension of Arbogast's Method of Derivations. By Arthur Cayley, Esq., F.R.S. Received October 18,—Read December 13, 1860. Arbogast's Method of Derivations was devised by him with a view to the development of a function $\phi(a + bx + cx^2 + \ldots)$, but it is at least as useful for the formation of only the literal parts of the coefficients, or, what is the same thing, the combinations of a given degree and weight in the letters $(a, b, c, d, \ldots)$, the weights of the successive letters being $0, 1, 2, 3, \&c.$ Thus instead of applying the method to finding the coefficients $$a^4, 4a^3b, 4a^3c + 6a^2b^2, \&c.$$, we may apply it merely to finding the sets of terms $$a^4, a^3b, a^3c, \&c.$$. $$a^2b^2$$ To derive any column from the one which immediately precedes it, we operate on a letter by changing it into its immediate successor in the alphabet, and we must in each term operate on the last letter, and also, when the last but one letter in the term is the immediate antecessor in the alphabet of the last letter (but in this case only), operate on the last but one letter. Thus $a^3c$ gives $a^3d$, but $a^2b^2$ gives $a^2bc$ and $ab^3$, and the next succeeding column is therefore $$a^3d$$ $$a^2bc$$ $$ab^3$$. If the series of letters is finite, and the last letter of the term is also the last letter of the series, then it is impossible to operate on the last letter of the term, but the last but one letter (when the foregoing rule applies to it) is still to be operated on; and if the rule does not apply, then the term does not give rise to a term in the succeeding column; the operations will at length terminate, and a complete series of columns be obtained. Thus, if the letters are $(a, b, c, d)$, and the operations are (as before) performed upon $a^4$, the entire series of columns is | $a^4$ | $a^3b$ | $a^3c$ | $a^2b^2$ | $a^2bd$ | $a^2cd$ | $a^2d^2$ | $abd^2$ | $acd^2$ | $ad^3$ | $bd^3$ | $cd^3$ | $c^4$ | |-------|--------|--------|----------|---------|---------|---------|---------|---------|--------|--------|--------|------| | | | | | | | | | | | | | | MDCCCLXI. Nothing can be more convenient than the process when the entire series of columns is required; but it is very desirable to have a process for the formation of any column apart from the others; and the object of the present memoir is to investigate a rule for the purpose. But as Arbogast's rule, applied as above, depends upon very similar principles, I will commence by showing how this rule is to be demonstrated. If we take any combination $b^3d$ and operate backwards on the last letter (viz. by changing it into its immediate antecessor in the alphabet), we obtain $b^3c$, which is a term in the next preceding column; $b^3d$ is therefore obtainable from a term in the next preceding column, viz. $b^2c$, and the process is to operate on the last letter. If, instead of $b^3d$, the term is $abc^2$ (the last letter here entering as a power), the operation backwards on the last letter gives $ab^2c$, which is also a term of the preceding column; and it is to be noticed that the last but one letter $b$ is here the immediate antecessor of the last letter $c$ (and would have been so even if $b$ had not entered into the given term $abc^2$, thus $ac^2$ operated on backwards would have given $abc$). Hence $abc^2$ is obtained by operating on a term in the next preceding column, viz. the term $ab^2c$, but in this case the operation is performed on the last but one letter. Every term is thus obtained from the next preceding column, viz. the terms are obtained by operating on the last letter, and (when the last but one letter is the immediate antecessor in the alphabet of the last letter) then also on the last but one letter, of each term of the next preceding column, and the correctness of the rule is thus demonstrated. It is to be observed that the terms are operated upon in order, the operation on the last but one letter (when it is operated on) being made immediately after that upon the last letter of the same term, and that the terms of a column are thus obtained in the proper alphabetical order. I pass now to the above mentioned question of the formation of a single column by itself; it will be convenient, by way of illustration, to write down the columns \[ \begin{align*} a^3e^3 & \quad ade^3 \\ abde^2 & \quad bce^3 \\ ac^2e^2 & \quad bd^2e^2 \\ acd^2e & \quad c^2de^2 \\ ad^4 & \quad cd^3e \\ b^3ce^2 & \quad d^5 \\ b^2d^2e & \quad \\ bc^2de & \quad \\ bcd^3 & \quad \\ c^4e & \quad \\ c^5d^2 & \quad \\ \end{align*} \] which belong to the set $(a, b, c, d, e)$, and are of the degree 5 and the weights 12 and 15 respectively. Some definitions and explanations are required. I speak of the first and last letters of the set, simply as the first and the last letter: there is frequent occasion to speak of the last letter; and to avoid confusion, the last letter of a term will be spoken of as the ultimate letter; it is necessary also to consider the penultimate, antepenultimate, and pro-antepenultimate letters of the term. It will be convenient to distinguish between the ultimate letter and the ultimate, which may be either the ultimate letter or a power of such letter; and similarly for the penultimate, &c. Thus in the term $bcd^3$, the ultimate letter is $d$ and the ultimate is $d^3$, the penultimate and the penultimate letter are each of them $e$; of course the ultimate, penultimate, &c. letters are always distinct from each other. We have also to consider the pairs of letters contained in a term; $cd^3e$ contains the pairs $(c, d), (c, e), (d, d), (d, e)$, and so in other cases; the letters of a pair are taken in the natural order. A pair not containing either the first letter or the last letter is expansible; thus the set being as before $(a, b, c, d, e)$, the pairs $(b, c), (d, d)$ are expansible: they are expanded by retreating the prior and advancing the posterior letter each one step; thus the just mentioned pairs $(b, c), (d, d)$, are expanded into $(a, d)$ and $(c, e)$ respectively. A pair composed of two distinct non-contiguous letters is contractible; it is contracted by advancing the prior and retreating the posterior letter each one step: thus $(a, d), (c, e)$ are contractible pairs, and they give by contraction the pairs $(b, c), (d, d)$ respectively: the processes of expansion and contraction are obviously converse to each other. The expression the last expansible pair of a term hardly requires explanation; $(d, d)$ is the last expansible pair of the term $bcd^3$, or of the term $b^2d^2e^2$, $(c, d)$ the last expansible pair of the term $c^2de$ (the set being always $(a, b, c, d, e)$), and so in all other cases. The expression the last expansion, in regard to any term, means the expansion of the last expansible pair of such term. The expansion or contraction of any pair of a term leaves unaltered as well the weight as the degree, the resulting term belongs therefore to the same column as the original one. But the effect of an expansion is to diminish, and that of a contraction to increase the alphabetical rank, or rank in the column, the ranks being reckoned as the first or lowest, second, third, and so on, up to the last or highest rank. In particular, by performing upon any term the last expansion, we diminish the rank in the column, and by a succession of last expansions we bring the term up to the head of the column. Such term is not susceptible of any further expansion; it may therefore contain the first and last letters or either of them, and it may also contain a single intermediate letter in the first power only; thus the first and last letters being $a, e$, the head term of a column is of the form $a^m e^n$ or $a^m c e^n$, $c$ being some intermediate letter, and the powers $a^m, e^n$ being both or either of them omittable. In like manner, by a succession of contractions of any term we obtain the term at the foot of the column; such term is not susceptible of any further contraction, and it must therefore be composed either of a single letter or of two contiguous letters, that is it must be of the form $c^m$, or of the form $c^md^n$, where $c, d$ are any two contiguous letters, not excluding the case where the single letter or each or either of the contiguous letters is a first or a last letter. It is to be observed that the passage up from any term to the term at the head of the column (or top term) by means of a succession of last expansions, is a perfectly unique one; but as no selection has been made of a like unique process of contraction, this is not the case with respect to the passage down from any term to the term at the foot of the column (or bottom term) by a succession of contractions. Every term gives by the last expansion a term above it; it can therefore be obtained from such term above it by means of a contraction. But the contraction of the upper term is by hypothesis such that, performing upon the contracted term the last expansion, we obtain the upper term; a contraction, which, performed on any term, gives a lower term, which by performing upon it the last expansion reproduces the first mentioned or upper term, may be called a reversible contraction. And it is clear that if we perform on the top term all the reversible contractions, and on each of the resulting terms all the reversible contractions, and so on as long as the process is possible, we obtain without repetition all the terms of the column. The column is in fact similar to a genealogical tree in the male line, each lower term issuing from a single upper term, while each upper term generates a lower term or terms, or does not generate any such term, and the top term being the common origin of the entire series. It may be added that when the order of the reversible contractions of the same term is duly fixed, the alphabetical arrangement of the terms in the column agrees with the order as of primogeniture (an elder son and his issue male preceding all the younger sons and their respective issue male) in the genealogical tree. It only remains then to inquire under what conditions a contraction is reversible. Now as regards any term, in order that a contraction performed on it may be reversible, it is necessary and sufficient that the pair produced by the contraction should be the last expansible pair of the contracted term. There are several cases to be considered. First, if the contraction affects the ultimate and penultimate letters of the term: this implies that the ultimate and penultimate letters are not contiguous. Let the term terminate in $e^mh$, the contracted term will terminate in $e^{m-1}fg$, and $(f, g)$, the pair produced by the contraction, is the last expansible pair of the contracted term; the contraction is in this case reversible. If, however, the term terminate in $e^mh^p$ ($p > 1$), the contracted term will terminate in $e^{m-1}fgh^{p-1}$, and the last expansible pair is not as before $(f, g)$, but it is (according as $p = 2$ or $p > 2$) $(g, h)$ or $(h, h)$: unless indeed $h$ is the last letter, in which case $(f, g)$ remains the last expansible pair of the contracted term. In the example $e^m$ has been written, but the case $m = 1$ is not excluded; moreover, the penultimate letter $e$ is removed three steps from the ultimate letter $h$, but the result would have been the same if instead of $e$ we had had any preceding letter, or had had the letter $f$; by hypothesis it is not $g$, the letter contiguous to the ultimate letter $h$. The conclusion is that a contraction on the ultimate and penultimate letters (these being non-contiguous) is reversible if the ultimate is a simple letter, or if, being a power, it is a power of the last letter. Next let the contraction affect the ultimate and antepenultimate letters. The two letters are here separated by the penultimate letter, and are therefore not contiguous. Suppose that the termination is $f'g^m k$ ($f'$ and $g$ contiguous), the contracted term terminates in $f'^{-1} g^m j$, and $(g,j)$ the pair arising from the contraction is the last expansible pair of the contracted term; the contraction is therefore reversible. In the example $f'$ has been written, but the case $l=1$ is not excluded; moreover the ultimate letter $k$ is taken non-contiguous to the penultimate letter $g$; but if the ultimate letter had been the contiguous letter $h$, the only difference is that the pair would be $(g,g)$, and the conclusion is not altered. But suppose the termination of the term is $e'g^m k$ ($e', g$, non-contiguous), then the contracted term terminates in $e'^{-1} f'g^m j$, where the pair arising from the contraction is $(f',j)$, but the last expansible pair is $(g,j)$; the contraction therefore is not reversible. The case $l=1$ is not excluded; nor is it necessary that the ultimate letter should be non-contiguous to the penultimate; if the ultimate letter had been $h$, the pair arising from the contraction would have been $(f',g)$, but the last expansible pair $(g,g)$, and the contraction is still not reversible. In each of the cases considered the ultimate has been a simple letter: if in the first case the ultimate had been $k^p (p > 1)$, then the contracted pair would terminate in $j k^{p-1}$, and (according as $p=2$ or $p < 2$) the last expansible pair would be $(j,k)$ or $(k,k)$, which is not the pair $(g,j)$ produced by the contraction; the contraction is therefore not reversible, unless indeed $k$ is the last letter, in which case it continues reversible. In the second case the contraction, which is not reversible when the ultimate is the simple letter $k$, remains not reversible when the ultimate is a power of such letter. The conclusion is that a contraction on the ultimate and antepenultimate letters is reversible, if the penultimate and antepenultimate letters are contiguous, and the ultimate is a simple letter, or if, being a power, it is a power of the last letter. A contraction on the ultimate and pro-antepenultimate letters, or on the ultimate letter and any letter preceding the pro-antepenultimate letter, is never reversible. To show this, it will be sufficient to consider the case where the term terminates in $efgh$, the contracted term terminates in $ffgg$, the pair arising from the contraction being $(f,g)$, and the last expansible pair being $(g,g)$; and \textit{a fortiori}, if the letters or any of them occur as powers, or are non-contiguous. Consider, next, a contraction on the penultimate and antepenultimate letters; this assumes that these letters are non-contiguous. Such a contraction may be reversible if only the ultimate is the last letter or a power thereof; and the condition is then similar to that in the case of the ultimate and penultimate letters; only as the penultimate cannot be a power of the last letter, it must be a simple letter. And the conditions in order that the contraction may be reversible then are that the ultimate is the last letter or a power thereof, and the penultimate a simple letter. The next case is that of a contraction on the penultimate and pro-antepenultimate letters. Such contraction may be reversible if the ultimate is the last letter or a power thereof; and the condition is then similar to that for the case of the ultimate and antepenultimate letters; only as the penultimate cannot be a power of the last letter, it must be a simple letter. The conditions, in order that the contraction may be reversible, are that the ultimate may be the last letter or a power thereof, the penultimate a simple letter, and the antepenultimate and pro-antepenultimate letters contiguous. A contraction on the penultimate letter and on any letter preceding the pro-antepenultimate letter, or upon any two letters preceding the penultimate letter, is never reversible. If the ultimate, penultimate, antepenultimate and pro-antepenultimate letters are denoted by U, P, A, P' respectively, then by what precedes, the following contractions, viz. UP, UA, PA, PP', may be reversible, and they will be so under the conditions shown in the annexed Table. It is to be noticed that the conditions for UA, PA are mutually exclusive, and consequently that the number of reversible contractions to be performed upon any term is at most 3. The Table is | P | A | P' | |---|---|---| | U | U, P, non-contiguous letters. The ultimate a simple letter, or a power of the last letter. | P, A, contiguous letters. The ultimate a simple letter, or a power of the last letter. | | P | P, A, non-contiguous letters. Penultimate a simple letter. Ultimate the last letter, or a power thereof. | A, P', contiguous letters. Penultimate a simple letter. Ultimate the last letter, or a power thereof. | The contractions are to be applied in the order UP, UA, PA, PP', but all the contracted terms originating in a prior contraction of a given term are to be exhausted before proceeding to a posterior contraction of the same term. As an example of the process, the set being \((a, b, c, d, e)\), I will take the column \[ \begin{align*} abe^3 \\ acde^2 \\ ad^2e \\ b^2de^2 \\ bc^2e^2 \\ bd^2e \\ bd^4 \\ c^3de \\ c^2d^3 \end{align*} \] The top term \(abe^3\) is given. The contractions applicable to it are UP, UA. And UP gives \(acde^2\). The only contraction applicable to this is UA, giving \(ad^2e\). And there is not any contraction applicable to $ad^3e$. We revert therefore to UA on $abe^3$, this gives $b^2de^2$. The only applicable contraction is PA, giving $bc^2e^2$. The contractions applicable to this are UP, UA. And UP gives $bcd^2e$. The only contraction applicable to this is UA, giving $bd^4$, and there is not any contraction applicable to $bd^4$. We revert therefore to UA on $bc^2e$, this gives $c^3de$, and the only contraction applicable to this is UA, giving $c^2d^3$. There is not any contraction applicable to this, and the process is therefore complete. It may be remarked that the example presents no instance of the contraction PP'; in fact the only terms having a pro-antepenultimate are $acde^3$, in which A, P' are not contiguous letters, and $bcd^2e$, in which the penultimate is not a simple letter, so that the contraction PP' is in each case excluded. It must be confessed that a considerable amount of practice would be required before the process could be readily made use of.