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.