Comments on A1111160, A055113 and A006013 Date: Tue, 11 Oct 2005 22:02:14 -1000 (HST) From: Douglas Rogers There seems to be more that might usefully be said about A055113 and A006013, in particular how they are linked through A111160: 0 1 1 4 9 31 91 309 ... The problem being considered can be set up in terms of generating functions as follows. Given the g.f. C for the sequence of Catalan numbers (A000108), satisfying the functional equation C = 1 + xCC, to investigate the partition C = Z + W, where Z = 1 + ZW, (*) W = x(ZZ + ZW + WW). (**) So Z is the g.f. for A055113, while W is that for A111160. Now, the link to A006013 is through W, since W(x) = xC(x)U(xxC(x)), where U is the generating function for A006013. This type of function of a function relationship is familiar in the theory of branching processes. What it means here is that the coefficients of W, and so also therefore the terms of A055113, are linear combinations of ballot numbers. But, since the terms of A006013 are themselves ``higher'' or ``generalized'' ballot numbers, in fact, we have explicit expressions for the terms in this particular decomposition of the sequences of Catalan numbers. Moreover, amusingly enough, a problem about binary operations is found to have this partticular form of resolution in terms of ternary operations. The algebraic proof of this identity is simplicity itself, given (*) and (**). On the one hand, Z = 1/(1 - xW), while on the other W(1 - xW) = x(ZZ + ZW) = xCZ. Hence, W = xCZZ = XC/(1 - xw)(1 - xW). Thus, if U(x) satifies the functional equation U = 1/(1 - xU)(1 - xU), which is, indeed, one way to obtain A006013, then, by comparison, W(x) = xC(x)U(xxC(x)), as claimed. Of course, if we write V = 1 + xVU, so that V = 1/(1 - xU), then U = VV, while V = 1 + xVVV. Here V is the generating function of sequence A001764, one of a comparatively well-known family generalizing the Catalan numbers. In particular, V is associated with ternary bracketings in much the same way as C is with binary bracketings. Naturally, one expects this family to yield a full generalization of these observations, with ternary bracketings turning on results for quaternary bracketings, and so on.