## How many signs? (Part II)
We may illustrate the method of calculation by considering the case n=6. The whole sign may be contained in one circle, or several. In the first case we call the sign 'prime'; otherwise, it is 'composite', and is the 'product' of several primes. Assuming n=6, if the sign is prime, then it consists of a sign made of 5 circles enclosed in one big circle, giving us 20 possibilities. In case the sign has two factors, the number of circles in the factors may be 5+1, 4+2 or 3+3. In the first case, the first factor consists of a sign made of 4 circles, enclosed in an outer circle; the second component is just an empty circle; giving us 9 possibilities. The second case gives us 4 possibilities. In the third case, each component consists of a sign made of 2 circles, enclosed in an outer circle. There are 2 signs made of 2 circles, so that looks at first like 4 possibilities. But we don't care which factor is which, so that 4 is reduced to 3. So that's another 16 signs with 2 factors. If the sign splits into 3 factors, the circles can split up as 4+1+1, 3+2+1, or 2+2+2. The number of signs here is 4+2+1 = 7. 4 factors: 3+1+1+1 (2 signs), 2+2+1+1 (1 sign). 5 factors: 2+1+1+1+1 (1 sign). 6 factors: 1+1+1+1+1+1 (1 sign, consisting of 6 empty circles). The total number of signs made out of 6 circles is 20+16+7+3+1+1 = 48; agreeing with the number given in the table. Even with just 6 circles, the 'bare hands' approach to calculating the number of signs is becoming pretty difficult; for higher n, we will definitely need to be more cunning. As with numbers, but in a more obvious way, each sign may be expressed as a product of 'primes'; for example: Here the whole sign is a product of three factors, each of which is prime in that it cannot be further divided. In the case of the natural numbers, we may write (formally) 1 + 2 + 3 + 4 + 5 + 6 + 7 + ... With the signs, we may write (formally) something similar: _ + O + OO + (O) + OOO + O(O) + ((O)) + ... On the left we have a formal sum of x Because the number of circles in a composite sign is the sum of the numbers of circles in the prime factors, the powers of x behave in such a way that the formula remains valid (assuming the powers of x multiply independently of the signs). We now let the signs fade away. On the left, we are left with a formal power series in x, where the coefficient of x (1 + x one such factor for each prime sign, k being the number of circles in that prime sign. Note that usually there will be many prime signs belonging to the same k. If there are n (1 - x But note that n 1 + a This constitutes a beautiful 'implicit equation' for the coefficients a Moving on to a (1 - x) is 2, giving us the correct value for a ln(f(x)) = -a Differentiating, f'(x)/f(x) = a Here b b and in general b Returning to our equation, we may multiply each side by f(x), obtaining f '(x) = f(x) g(x), that is, a From this (together with the formulae for the b b and so on. The calculations are best arranged in a tabular form: The shaded cells are the ones that have to be added up and divided by 6 to obtain a One might ask, how many of the signs with n circles have the value m (mark) and how many have the value n (not a mark)? The following table gives the answer, for the first few n. c Exercise for the reader: work out a method of calulating these numbers. (Clue: each sign that evaluates to no mark must be the product of primes, each of which evaluates to no mark.) Exercise: on the whole, it seems that more signs evaluate to m than to n. Calculate (using a computer) the limit, if any, of the ratio d ## References[1] Cayley, 'On the Theory of the Analytical Forms called Trees', See also: Cayley, 'On the Analytical Forms called Trees' |