Writings of Charles S. Peirce: A Chronological Edition, Volume 8: 1890–1892

35. On the Number of Dichotomous Divisions: A Problem in Permutations

222 35 On the Number of Dichotomous Divisions: A Problem in Permutations Spring 1891 Houghton Library In the calculus of logic, a proposition is separated by its copula, R, into two parts, as A R B. But these parts may again be separated in like manner, as (A R B) R C and A R (B R C), and so on indefinitely. It becomes pertinent to inquire how many such propositional forms with a given number of copulas there are. The same problem presents itself in general algebra, where R is replaced by any non-associative sign of operation; and, indeed, the question not unfrequently arises; but I do not know that the solution has been given. We may consider a row of letters, A, B, C, etc., which we may call the ABC, separated into two parts by a punctuation mark, and each part (not consisting of a single letter) into two parts by a subordinate punctuation mark, and so on until all the letters are separated. I shall call the resulting form an ABC-separation. The following are examples A : B . C ; D , E : F A . B ; C : D ; E , F Let n be the number of punctuations; then, the number of letters will be n  1. Let Fn be the number of ABC-separations with n punctuations , or say of n-point separations. Then, if i be the number of letters to the left of the highest punctuation, so that n  1  i is the number to the right, the number of ABC-separations of the row to the left is F(i  1) and the number of ABC-separations of the row to the right is F(n  i), and the number of those ABC-separations of the total row in which the first punctuation has i letters to the left of it is F(i  1) F(n  i). And the total number of n-point separations is 35. Dichotomous Divisions, 1891 223 Fn  F(i  1) F(n  i)  F0 F(n  1)  F1 F(n  2)  . . .  F(n  2) F1  F(n  1)F0. And it is evident that F0  1; so that this formula gives F1  F0 F0  1 1  1 F2  F0 F1  F1 F0  1 1  1 1  2 F3  F0 F2  F1 F1  F2 F0  1 2  1 1  2 1  5 F4  F0 F3  F1 F2  F2 F1  F3 F0  1 5  1 2  2 1  5 1  14 And so we should find F5  42, F6  132, F7  429, etc. Taking the ratio of successive Fs, we find  1,  2,  ,  ,  3,  . Now, noticing that the last of these has its denominator equal to 7 and that next but one before it its denominator 5, we are naturally led to express the intermediate one as a fraction with 6 for its denominator. The three numerators are then 14, 18, 22, which are in arithmetical progression . If this holds good we should have  ,  ,  , and all these values are verified. We next predict that  , and finding it to be so, we entertain a high degree of confidence that this is the general rule. For unless the true formula is of a degree of complexity which the simple nature of the problem prevents us from expecting, it can hardly agree with that we have found for the first seven ratios of the series without according completely. We have, then, as we may be morally sure, Fn   2 n  i 1 n  F1 F0 ----- F2 F1 ----- F3 F2 ----- 5 2 -- F4 F3 ----- 14 5 ----- F5 F4 ----- F6 F5 ----- 22 7 ----- F3 F2 ----- 10 4 ----- F2 F1 ----- 6 3 -- F1 F0 ----- 2 2 -- F7 F6 ----- 26 8 ----- 4n 2  ( ) 4n 6  ( ) 4n 10  ( ) . . . 2 n 1  ( ) n n 1  ( ) . . . 2 ------------------------------------------------------------------------------------- 2n 1  ( ) 2n 3  ( ) 2n 5  ( ) . . . 1 n 1  ( ) n n ( 1 ) . . . 1  ---------------------------------------------------------------------------------2n n 1  ( )n n 1  ( ) . . .1 ------------------------------------------------------ 2n 2n 1  ( ) 2n 2  ( ) 2n 3  ( ) . . .1 2n 2n 2  ( ) . . . 2 --------------------------------------------------------------------------------------- - Writings of C. S. Peirce 1890–1892 224   It remains to demonstrate this mathematically. Suppose that in writing the ABC-separation, before we insert any letters we set down all those punctuations that are superordinate to the first letter, that is, all which help to separate the place of A, and no others . Thus, in the first example above, or A : B . C ; D , E : F we should set down : . and in the second, or A...