Assembly of nothing

[Christian G. Bower]

This is about a problem with sequence transforms I've been thinking
about for a couple of years now. I call it the "assembly of nothing"
problem.

Assembly refers to creating a set of combinatorial structures
classified by number of nodes of the form A(B) where B is a
preexisting set of structures and A is a rule for how to place
the B-structures into the new structure.

One type of assembly is combinatorial substitution (or composition).
In this instance the "A" rule is itself a collection of structures.
The assembly is to take copies of "B" structures and use them as
the points of the "A" structure.

A variant of this assembly is one where certain pairs of points in
the "A" structure are set aside to be filled with the same "B"
structure (i.e. 2 copies of the same structure) or different
"B" structures.

What's particularly notable about these assemblies is that they
can be described by index series which are formal polynomial
series of the indexed variables x_1, x_2, x_3, ....

The "nothing" part of the title refers to "B" structures that have
a size (or number of points) of zero. The formulas detailing the
counting of these structures frequently forbid the "B" structure
from containing any zero sized members. In many cases this seems
like a necessary restriction, but in others, it can get in the
way of some useful combinatorial questions.

Let's consider 2 types of assemblies.

Sets of structures, allowing the same structure multiple times
(as implemented by the Euler transform for unlabeled structures
and the Exponential transform for labeled structures.)

Sets of structures, requiring all structures to be different
(as implemented by the Weigh transform for unlabeled structures.)

http://www.research.att.com/~njas/sequences/A000041
The partition sequence A000041 counts unlabeled sets of nonempty sets
hence it has g.f. EULER(x/(1-x)) if we consider EULER as a g.f.
transformation.

http://www.research.att.com/~njas/sequences/A000009
A000009 counts sets of nonempty sets all different from one another
with g.f. WEIGH(x/(1-x)).

in the first case, it makes sense that the "B" structure (the
nonempty sets) are not allowed to have 0 sized elements (i.e.
be empty). If we tried to count partitions of n and allowed n
to be partitioned into 0s, we would have infinitely many
possibilities. 1, 1+0, 1+0+0, ....

In the second case, we can allow empty "B" structures, since
each structure can only be used once giving us 4 partitions
of 3 into distinct parts: 3, 3+0, 1+2, 1+2+0, or in general
2*A000009(n) partitions of n into distinct parts allowing 0
as a part. Hence we would like to say that
WEIGH(1/(1-x)) = 2*WEIGH(x/(1-x)).

The commonly used formulas appear to support these observations.

The Euler transform as applied to a sequence is often rendered:

(1-x)^(-a1)*(1-x^2)^(-a2)*(1-x^3)^(-a3)*(1-x^4)^(-a4)*...

with the Weigh transform as

(1+x)^a1*(1+x^2)^a2*(1+x^3)^a3*(1+x^4)^a4*...

both of these formulas ignore the a0 term, but if we were to extend
these one term backward we would have Euler start

(1-1)^(-a0)*...

and Weigh

(1+1)^a0*...

and we can see that in Euler's case given any positive a0 we begin
with 0 raised to a negative power giving an infinite value and for
Weigh's case we start the product with 2^a0.

A similar effect is seen from the index series.

An index series is applied to a g.f. as follows:

If s(x_1, x_2, x_3, ...) is the index series, then it maps the
g.f. A(x) to s(A(x), A(x^2), A(x^3), ...) thus x_2^2 + x_3*x_4
maps as A(x^2)^2+A(x^3)*A(x^4).

Euler's i.s. is exp(x_1/1 + x_2/2 + x_3/3 + ...)

Weigh's i.s. is exp(x_1/1 - x_2/2 + x_3/3 - ...)

We can see that if A(x) has a positive constant term, then
that term will be multiplied by the divergent harmonic series
1+1/2+1/3+... and blow up. With Weigh we have the alternating
harmonic series 1-1/2+1/3-...=ln 2 giving it the 2^a0 character.

So in these 2 examples, the problem seems manageable, but if one
is looking for a general theory to cover all such assemblies or
all transforms defined by i.s., things are not so easy.

Consider 2 other assembly rules:

Ordered lists of structures, allowing the same structure multiple times
(as implemented by the Invert transform for unlabeled structures.)

Ordered lists of structures, requiring a structure not have a copy
of itself as a neighbor
(I call the unlabeled version of this the Carlitz transform. It's
not in the EIS canon yet.)

Invert's i.s. is 1/(1-x_1)
Carlitz's i.s. is 1/(1-x_1+x_2-x_3+...)

Invert creates compositions (or ordered partitions) the way Euler
creates partitions.

Hence we have INVERT(x/(1-x)) = (1-x)/(1-2x) = 1,1,2,4,8,16,...

Just as in the unordered partitions, we would not allow one to
compose n into 0s, there would be infinitely many choices.
Note that unlike the Euler transform which blows up for a0>0,
The Invert transform can be calculated for any a0 != 1, although
it's difficult to give a combinatorial interpretation to any
nonzero value.

http://www.research.att.com/~njas/sequences/A003242
Carlitz(x/(1-x)) gives us A003242 Carlitz compositions, those
where no two adjacent parts are equal. We can allow Carlitz
compositions to contain 0s since the separation of the 0s by other
numbers keeps it finite: Carlitz(1/(1-x)) = A114900.
http://www.research.att.com/~njas/sequences/A114900
However, the i.s. does not tell us how to do it. If A(x)=1 what
does one make of Carlitz(A(x)) = 1/(1-1+1-1+...)

I recently had an idea about how to deal with issues like this:
use an analytic interpretation of the g.f. of a sequence.

If a sequence represents structures contains only finitely many
structures, then the number of structures is A(1) where A(x) is
the g.f. My idea is to take the case where A(x) has a radius of
convergence (ROC) >0 and <=1 so that it cannot be evaluated by
adding the terms, and associating its size with A(1) of the
analytic extension of the g.f. Here in the Carlitz case we have
1-x+x^2-x^3+... = 1/(1+x) hence A(1) = 1/2 and 1/(1/2)=2, the
expected value for Carlitz compositions of 0 allowing 0 as a part.
(The 2 are the empty composition and zero.)

In this way I can evaluate a transform of a sequence whose only
nonzero term is a_0 as T(a_0*x)(1) and for more general sequences
I can apply the transform to a 2 dimensional sequence as follows.

If sequence has g.f. A(x) then let C(x,y) = y*A(x).

Apply T to C(x,y) getting D(x,y) as output:

Let d_n = [x^n] D(x,1)

I suspect this will be an adequate solution to many problems of
this sort, but I'm not sure how far this method can be trusted.
Part of the problem is I don't know my analytic function theory
as well as I should. (If anyone out there does, please chime in.)
More importantly, I've run across some examples that challenge
the method.

My first example involves the Euler transform. It's basically only
a problem because I would expect that if f(1)=g(1) then
(Tf)(1) = (Tg)(1) for any transform with both f and g in its
domain. It seems reasonable as 1^n=1 for all n so that i.s.'s
behave like g.f.'s when evaluated at 1. More importantly, the
choice to use the linear term in "C(x,y) = y*A(x)" as opposed
to "C(x,y) = y^2*A(x)" was arnitrary and it seemingly should
not matter which term I chose, so I would like some assurance
that I'll get the same answer following any such path.

Consider

EULER(0) = 1
EULER(x-x^2) = 1+x
EULER(x-x^3) = 1+x+x^2

For all of these, the inputs have f(1)=0, but the outputs have
g(x)=1,2 or 3

I think the reason for this anamoly may be in the instability
Euler has at 0. Just as Weigh behaves like 2^x, Euler behaves
like 0^(-x) giving 0 for negative values of x, infinity for
positive values and doing what we see here at x=0. 0^0 is
generally defined as 1, but analytically it can be anything and
that may be the limitation I'm running into.

My other example concerns me, because I'm interested in formulas
that can be applied to arbitrary sequences, not just integer
sequences. Most of our familiar transform formulas work fine for
arbitrary sequences, and it would be nice if all of them did,
however...


Ordered lists of structures, requiring all structures to be different
(as implemented by the AGK transform for unlabeled structures
found on
http://www.research.att.com/~njas/sequences/transforms2.html )

Obviously, this assembly makes sense for empty structures since
each structure can appear at most once. If I allow there to be
n types of empty structures in the input then I have
A003149(n) empty structures in the output.
http://www.research.att.com/~njas/sequences/A003149

While it seems quite plausible that this sequence can be
interpolated into a nice analytic function, the method I illustrated
above offers no help as for n anything other that a
nonnegative integer gives me a sequence with ROC of zero.

So the idea in posting this is to present some new ideas to the
sequence community, get some opinions from people who know some
things that I don't know and get some ideas about how to handle
difficult cases.

Christian