New progress on an old problem

[Christian G.Bower]

I last wrote about this problem in 1/2004:

--------------
It occured to me that it is a type of sequence exponentiation.

The operation which I called EOP at the time, I'll represent using
the exponential symbol ^ here.

b^a = EULER(a *d invEULER(b))

Here *d represents Dirichet convolution or multiplication of the
Dirichet generation functions.

It satisfies the exponential property b^(g+h) = b^g * b^h
if * is multiplication of the ordinary g.f.'s (ordinary convolution.)

It's analogous to the scalar equation:

y^x = exp(x*log(y))

Furthermore since EULER and WEIGH are both exponential transforms,
we can replace EULER with WEIGH in the equation.

b^a = EULER(a *d invEULER(b)) = WEIGH(a *d invWEIGH(b))
--------------

One thing I tried (back in 2000 when I first started looking at this
problem) was replacing the EULER transform with the INVERT transform
to do the same with ordered lists of structures. Thus the sequence
operation I'll call LINEOP

b LINEOP a = INVERT(a *d invINVERT(b))

I had thought I had written about this one before in seqfan, but I can't
find it. In the EULER/WEIGH transform case, the base sequence b described
how many copies of the same structure could be used.  In this case the
base describes how many copies of the same structure can be next to each
other.  For example:

[1 0 0 0 ...] LINEOP [1 1 1 1 1 ...] = A003242

ID Number: A003242
URL:       http://www.research.att.com/projects/OEIS?Anum=A003242
Sequence:  1,1,1,3,4,7,14,23,39,71,124,214,378,661,1152,2024,3542,6189,
           10843,18978,33202,58130,101742,178045,311648,545470,954658,
           1670919,2924536,5118559,8958772,15680073,27443763,48033284,
           84069952,147142465,257534928,450748483,788918212
Name:      Number of compositions of n such that no two adjacent parts are
equal.

Incidentally, I would like to propose naming the transform
T(a) = [1 0 0 0 ...] LINEOP a
as the Carlitz transform.  A003242 is called the sequence of Carlitz
compositions, because of a paper he wrote about them.

At the time, I had no good idea as to why such a simple trick should work,
but I think I have an idea now.

One thing about the exponentiation defined earlier is that it defines
transforms that are exponential relative to ordinary generating functions.

T(a+b) = a*b where * is multiplication of o.g.f's.

with the following statement about exponential transforms:

--------------
and more generally, if T and U are exponential transforms then:
T(a) = U(L(a)) for some linear transform L. By linear I mean
L(a+b) = L(a)+L(b).
--------------

it's easy to see how the method generates the only possible exponential
transform satisfying initial conditions.

But INVERT is not exponential.

But if I defined multiplication of sequences as the following o.g.f.
operation

a ** b = (a*b)/(1-(a-1)*(b-1))

it would be.

In fact, any one-to-one function creates such an operation on its range
according to a**b = f(f^-1(a) + f^-1(b))

But that's not the whole story.  I tried this trick on several other
transforms and none of them worked.  One particular transform I was
working with, I call the CYCLE transform, the one I called CIK in

http://www.research.att.com/~njas/sequences/transforms2.html

doesn't work, but I've finally found enough tweaks to get an equivalent
transform out of it.

The operation I call a CYOP b, arranges objects of type b in a circle
where a governs how many b objects can be layed right next to each other.

a CYOP b = invMOEBIUS(invEULER(a LINEOP b) - (a *d invEULER(b))) + (a *d b)

This formula is a bit complicated, but I can calculate with it quickly.
I'm hoping to unravel it a bit and find something that can be simplified.

As to why the simpler trick works with EULER and INVERT and not with
CYCLE, consider this.  If I want to create a Carlitz string of X's and Y's,
I start with either X or Y and I alternate as long as I wish.

X
Y
XY
YX
XYX
XYXYXYXYXYXY
YXYXYXYXY
...

If I want a Carlitz string of X's, Y's and Z's, I can alternate Z's with
Carlitz strings of X's and Y's.

Z XYX Z YX Z XYXYXY Z

But I cannot create a cycle of X, Y, Z by alternating Z with cycles of 
X and Y, I have to alternate Z with strings of X and Y.  Hence the basic
operation for pairing up two structures does not work for adding a third.

One of those old magic formulas from combinatorics was very useful in
finding the formula for CYOP

MOEBIUS(CYCLE) = invEULER(INVERT)

Anyway, since I've made these new toys creating sequences, I suppose I'll
create some sequences.

2-colored necklaces where a bead cannot be next to a bead of the same color
are kind of boring:
2,1,0,1,0,1,0,1,0,1,...

so I won't bother to submit it, but the 3 color version
3,3,2,6,6,14,18,36,58,108,...

looks interesting enough to submit (A106365) as do the 4-6 color versions
(6,7 and 8)

By creating an eigensequence with these transforms, I can do mobiles
(cycling rooted trees) where a branch is never the same as its next door
neighbor
1,1,1,2,3,6,14,30,68,159,381,914,... (going in as A106364)

and the equivalent breed of rooted planar trees and planar trees
1,1,1,2,4,10,28,77,221,650,1951,... (A106362)
1,1,0,1,0,1,3,7,14,43,115,326,931,... (A106363)

Now if I can only find such transforms for reversible lines and cycles.

Christian