Bell numbers, again. FINDER axiomatizations.

[Antti Karttunen]

Dear SeqFans,

I have been recently playing with John Slaney's
FINDER (Finite Domain Enumerator),
(see http://arp.anu.edu.au/~jks/finder.html for details)
to concoct various axiomatizations for many of our belowed
combinatorial objects. Using it is fun, almost
like coding some kind of "inverted Prolog",
and when I grow cardinality one by one
and jot down the number of solutions for each,
I get sequences which I can check against
OEIS, to see whether I'm on the right track
at all.
However, it is easy to make mistakes, and thus
generate solutions to wholly different problem
that what I originally had in mind.

For example, today I was looking for an axiomatization
for "non-crossing handshakes" (enumerated by Catalans
as we all know), but created "accidentally" this kind
of thing:

%=======================================================================
%
%       
%       Handshaking across a table (everybody shaking), with
%       an extra condition. Failed attempt of A000108A.fnd
%       SEEMS (Check it!) to be enumerated by EIS A000110 (Bell numbers),
%       but aerated (0,1,0,2,0,5,0,15,0,52,0,203,0,877,0,4140,0,21147,...)
%       because we get no solutions when there are odd number of shakers.
%
% See also:
%
% http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000110
% http://www.iki.fi/~kartturi/matikka/ModFin/A000108A.fnd
% http://www.research.att.com/~njas/sequences/a002694.gif
% http://mathforum.org/advanced/robertd/bell.html
%
%==========================================================================

sort {
        ELEM
        cardinality = 16
}


function {
        f:      ELEM -> ELEM { bijective }
}


clause {
        f(x) = x -> FALSE.                      % No fixed points.
        f(x) = y -> f(y) = x.                   % Just transpositions, no larger cycles.
        FALSE = (f(x) = y); FALSE = (y > x); f(y-1) > x.
        FALSE = (f(x) = y); FALSE = (y > x); FALSE = (f(y-1) > y).
}

setting {
        verbosity stats: full
        stack: maximal
}


end

The last two axioms say that if x and y shake hands, then
the person one position left from y shakes hand with a person who is
in the interval ]x,y], i.e. is situated between x and y,
or, unless x and y are situated next to each other, y-1 is actually x
(and thus shaking with y).
Can anybody give a proof that this structure actually is enumerated
by Bell numbers?

So, only after finding the erroneous extra solution
for the case cardinality=8 and thinking about it a bit,
I realized that that kind of a "local" condition is not
enough to forbid crossing handshakes.
Here is the correct solution:

%=======================================================================
%
%       
%       Handshaking across a table (everybody shaking), with
%       no crossing handshakes allowed.
%       Is enumerated by 0,1,0,2,0,5,0,14,0,42,0,132,0,429,0,1430,0,4862,0,16796,0,...
%       whose bisection is the famous A000108, Catalan numbers.
%
% Actually, it's more natural to think here Stanley's interpretation (o),
% ways of connecting 2n points in the plane lying on a horizontal line
% by n nonintersecting arcs, each arc connecting two of the points
% and lying above the points, or
% (kk) fixed-point free involutions w of [2n] such that if i < j < k < l
% and w(i) = k, then w(j) != l (in other words, 3412-avoiding fixed-point
% free involutions), which are essentially the same thing.
%
% See http://www-math.mit.edu/~rstan/ec/catalan.ps.gz
% Exercise 19 for the interpretations.
%
% The last axiom says, that
% if((x<y) && (y != f(x)) && (x < f(x)) && (y < f(y)))
% then should hold either that (f(x) < y) or f(y) < f(x).
%
% I.e. the relative orders   x   < f(x)  <   y   < f(y)
%                      and   x   <   y   < f(y)  < f(x)
% are possible,
%               but not:     x   <   y   < f(x)  < f(y)
%
% The semicolon (;) in clauses stands for disjuction, "or".
%
%==========================================================================

sort {
        int
        cardinality = 20
}


function {
        f:      int -> int { bijective }
}


clause {
        f(x) = x -> FALSE.                      % No fixed points.
        f(x) = y -> f(y) = x.                   % Just transpositions, no larger cycles.
        x=y; x>y; y=f(x); x>f(x); y>f(y); f(x)<y; f(y)<f(x).
}

setting {
        verbosity stats: full
        stack: maximal
}


end


--------------------------

Another question:
If I add to the axioms of partial orders
an axiom forcing each "sub-poset" to be
eventually connected to a "root" (which is
"less than" every other node)
I get the sequence which begins like A006059
"Connected labeled topologies with n points."
Is it question of the same thing?
One may think this class as some kind of trees
where "trunks that part and then connect again"
are allowed. Indeed, sometimes one sees this phenomenon
in forests, at least in its milder form.


%=======================================================================
%
%       Connected labeled topologies with n points.
%       I.e. (???) partially ordered sets ("posets") with n labeled elements,
%       with all elements except one having at least one "less than element".
%
%       Is enumerated by EIS A006059 (1,2,9,76,1095,25386,910161,...) ???
%
% See also:
%
% http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006059
% http://mathworld.wolfram.com/PartialOrder.html
% http://www.iki.fi/~kartturi/matikka/ModFin/A00169.fnd
% http://www.iki.fi/~kartturi/matikka/ModFin/A001035R.fnd
%
% http://arp.anu.edu.au/~jks/finder.html
%
%=======================================================================

sort {
        ELEM
        cardinality = 7
}


function {
        e:      ELEM,ELEM -> bool.      % e(x,y) means x < y.
        f:      ELEM -> ELEM { cut }    % "Skolem-function". Prune off its extra solutions with cut.
}


clause {
        e(x,x) -> FALSE.                        % Irreflexive.
        e(x,y) -> FALSE = e(y,x).               % Asymmetric.
        FALSE = e(x,y); FALSE = e(y,z); e(x,z). % Transitive.
        x=y; e(f(x),x); e(f(y),y).              % If x and y are distinct, then at least other has a predecessor.
}

setting {
        verbosity stats: full
        stack: maximal
}


end



-----------------


Terveisin,

Antti