Catalan numbers, axiomatized, noncrossing Murasaki-diagrams.

[Antti Karttunen]

First, note for everybody who might have tried to send
personal e-mail to my address Antti.Karttunen at iki.fi on
this week:
For some stupid reason our company's SMTP-server now rejects
any mail forwarded from that address, so I changed Antti.Karttunen at iki.fi
to point back to the old, working mail-server to which
I have an access. The last SeqFan-message I have seen is 
Subject: Re: generatingfunctions
   Date: Mon, 5 May 2003 19:25:46 +0200 (CEST)
   From: Karol PENSON <penson at lptl.jussieu.fr>
so it might be that anything sent after that
to Antti.Karttunen at iki.fi has bounced back.
Please re-send if important or interesting.
(The missing SeqFan-postings I can ask from Wouter
or from the archives. ;-)


But back to the topic!

wouter meeussen wrote:
> 
> ----- Original Message -----
> From: "wouter meeussen" <wouter.meeussen at pandora.be>
> To: "Antti Karttunen" <Antti.Karttunen at iki.fi>
> Sent: Thursday, May 08, 2003 10:58 PM
> Subject: Re: Bell numbers, again. FINDER axiomatizations.
> 
> > Aha,
> >
> > got an "Observational Math Bug" eh?
> > watch out! its worse than SARS.

I know, I know. It's waste of many great men...
So here follows another fruit of insomnia, a yet another axiomatization
resulting Catalan numbers. Incidentally, it has a property that
connects this thread back to the "Tale of Genji".
(I leave it as an easy puzzle how to construct the exact bijection...)

%=======================================================================
%
%       Functions on domain {0..n-1} for which f(0)=0
%       and f(x+1) is never greater than f(x)+1.
%       Is enumerated by EIS A000108 (1,1,2,5,14,42,132,429,...)
%       a.k.a. Catalan numbers.
%       Probably the simplest axiomatization that results
%       a structure enumerated by Catalans.
%       Direct correspondence with Stanley's interpretations
%       (pp), (qq) and (rr), where the last is
%       "noncrossing Murasaki diagrams with n vertical lines".
%
% See http://www-math.mit.edu/~rstan/ec/catalan.ps.gz
% Exercise 19 for those interpretations.
%
% See also:
%
% http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000108
% http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A071157
% http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A071159
% C. Banderier, A. Denise, P. Flajolet, M. Bousquet-Milou et al.,
% Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
% Available at: http://pauillac.inria.fr/algo/banderier/Papers/DiscMath99.ps
% http://www.maths.usyd.edu.au:8000/u/kooc/catalan.html
% http://www.iki.fi/~kartturi/matikka/ModFin/A000108.fnd
% http://www.iki.fi/~kartturi/matikka/ModFin/A000108A.fnd
%
% http://arp.anu.edu.au/~jks/finder.html
%
%==========================================================================

sort {
        int
        cardinality = 1
}


function {
        f:      int -> int.
}


clause {
        f(0) = 0.
        x > 0 -> FALSE=(f(x-1)+1 < f(x)).  % No larger than one-step leaps upward.
}

setting {
        verbosity stats: full
        stack: maximal
}


end



Groetjes,

Antti