Algorithm Projects (Mitch Harris by way of Olivier Gerard)

[Olivier Gerard]

On Mon, 28 Jul 2003, wouter meeussen wrote:

>hi all,
>
>I came across A052889 by counting the blocks of size one over all set
>partitions of set {1..n}.
>Am I the only one *not* understanding the
>"INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 865" ?
>
>spec:= [S,{B=Set(C),C=Set(Z,1 <=
>              card),S=Prod(Z,B)},labelled]:
>              seq(combstruct[count](spec,size=n), n=0..20);
>
>All praise to INRIA, but the "vulgarisation level" seems pretty low (to a
>Mathematica user).
>Maybe my own Mma formulae are equally "hungarian" to them?
>
>Is there a 'translation service' anywhere?

  http://algo.inria.fr/encyclopedia/help.html

yes it is an implicit notation in that it is a way of defining a whole set 
of combinatorial objects (as trees) at once. Or you could just see it as 
generating function operators:

      Z = an atom  (each atom used is labeled)
  gf: Z(x) = x

      C = Set(Z, card <= 1) is the set of positive integers 
  gf: C(x) =  e^(Z(x)) -  1 = e^x - 1 (the -1 removes the empty set)
          [x^n]C = 1 means there is exactly one set with n atoms 
          since each atom is labeled

      B = Set(C) the set of (ordered) sets of integers 
        = ordered set partitions
  gf: B(x) = 1/(1-C(x)) = 1/(2-e^x)

      S = Prod(Z, B) pairs of an atom (Z) and an ordered set partition
        = an ordered set partition with an adjoining single atom.
          the adjoining atom turns out to define a "root" in the 
          partition
  gf: S(x) = x * 1/(2-e^x) = x/(2-e^x)


-- 
Mitch Harris
Lehrstuhl fuer Automatentheorie, Fakultaet Informatik
Technische Universitaet Dresden, Deutschland
http://tcs.inf.tu-dresden.de/~harris