Catalan numbers, axiomatized, noncrossing Murasaki-diagrams.

Antti Karttunen Antti.Karttunen at
Fri May 9 12:40:51 CEST 2003

First, note for everybody who might have tried to send
personal e-mail to my address Antti.Karttunen at 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
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>
so it might be that anything sent after that
to Antti.Karttunen at 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>
> To: "Antti Karttunen" <Antti.Karttunen at>
> 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
% Exercise 19 for those interpretations.
% See also:
% 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:

sort {
        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




More information about the SeqFan mailing list