[Previous] [Next] [Contents]

combinat::decomposableObjects -- decomposable combinatorial objects

Introduction

The library combinat::decomposableObjects(specification) provides functions for counting, generating, and drawing at random the decomposable combinatorial objects defined recursively by specification.

Domain


combinat::decomposableObjects(specification <, Options>)

Parameters

specification- A combinatorial specification

Options

Labelled = b- Selects between labeled or unlabeled combinatorial objects. b must be TRUE or FALSE. The default value is FALSE.
Products = Type- Choose the counting algorithm. Type is one of Naive, Holonomic. The default value is Holonomic for context free grammars, and Naive otherwise. See "count" for details.
MainNonTerminal = A- Specifies the main non terminal of the specification. A must be a non terminal appearing in the specification. By default, the first one (as returned by op(specification,[1,1]) is used). This option used to be incorrectly named MainTerminal.
Boustrophedonic = b- Specifies the order in which elements of products are generated; see ``background'' section for more details. b must be TRUE or FALSE. The default value is TRUE.

Details

Categories

Cat::CombinatorialClass

Method count: number of decomposable objects

Method generator: generator for decomposable objects

Method list: list of decomposable objects

Method unrank: unranking of decomposable object

Method random: random object

Method standardSpecification: specification in standard form

Method standardSpecificationCount: specification in standard form

Method recurrenceRelation: recurrence relation for the coefficients of the generating series

Method generateCode: automatic C code generation

Example 1

We create a domain for complete binary trees:

>> BinaryNaive:=combinat::decomposableObjects({B=Union(Z,Prod(B,B))}):
     
        

Standard form of specification

>> BinaryNaive::standardSpecification()
     
                       table(
                         Z = Atom(Z),
                         B = Union(Z, NonTerminal1),
                         NonTerminal1 = Prod(B, B)
                       )
        

The number of binary tree of size 0 to 10

>> BinaryNaive::count(i) $i=0..10
     
                0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862
        

A random tree of size 1 and size 2

>> BinaryNaive::random(i)$ i=1..2
     
                               Z, Prod(Z, Z)
        

List of all objects of size 4 satisfying the specification

>> BinaryNaive::list(4)
     
      [Prod(Z, Prod(Z, Prod(Z, Z))), Prod(Z, Prod(Prod(Z, Z), Z)),
      
         Prod(Prod(Z, Prod(Z, Z)), Z), Prod(Prod(Prod(Z, Z), Z), Z),
      
         Prod(Prod(Z, Z), Prod(Z, Z))]
        

Example 2

This specification is the Schroeder tree with Naive product:

>> SchroederNaive:=combinat::decomposableObjects(
   {B=Union(Z,Prod(Z,B),Prod(Z,B,B))}):
     
        

Standard form of specification

>> SchroederNaive::standardSpecification()
     
                table(
                  Z = Atom(Z),
                  B = Union(Z, NonTerminal1, NonTerminal4),
                  NonTerminal4 = Prod(Z, NonTerminal3),
                  NonTerminal3 = Alias(NonTerminal2, op),
                  NonTerminal2 = Prod(B, B),
                  NonTerminal1 = Prod(Z, B)
                )
        

The number of Schroeder tree of size 0 to 10

>> SchroederNaive::count(i) $i=0..10
     
                  0, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835
        

A random tree of size 1 and size 2

>> SchroederNaive::random(i)$ i=1..2
     
                               Z, Prod(Z, Z)
        

Example 3

This specification defines the Schroeder trees with Naive and Holonomic product:

>> SchroederHolonomic:=combinat::decomposableObjects(
   {B=Union(Z,Prod(Z,B),Prod(Z,B,B))},Products=Holonomic):
   SchroederNaive:=combinat::decomposableObjects(
   {B=Union(Z,Prod(Z,B),Prod(Z,B,B))}):
     
        

Time necessary to count the number of Schroeder tree of size 500 according to whether you use the holonomic products or not

>> time(SchroederNaive::count(500));time(SchroederHolonomic::count(500));
     
                                    11340
         
                                    30
        

Time necessary to generate a random Schroeder tree of size 500 according to whether you use holonomic products or not

>> time(SchroederNaive::random(500));
   time(SchroederHolonomic::random(500));
     
                                    820
       
                                    490
        

Example 4

We demonstrate how to use the functions generator and list.

>> Shroeder:=combinat::decomposableObjects(
   {B=Union(Z,Prod(Z,B),Prod(Z,B,B))}):
     
        
>> Shroeder::count(5)
     
                                     9
        

All objects of size 5 satisfying the specification

>> Shroeder::list(5)
     
      [Prod(Z, Prod(Z, Prod(Z, Prod(Z, Z)))),
      
         Prod(Z, Prod(Z, Prod(Z, Z, Z))),
      
         Prod(Z, Prod(Z, Z, Prod(Z, Z))),
      
         Prod(Z, Prod(Z, Prod(Z, Z), Z)),
      
         Prod(Z, Z, Prod(Z, Prod(Z, Z))), Prod(Z, Z, Prod(Z, Z, Z)),
      
         Prod(Z, Prod(Z, Prod(Z, Z)), Z), Prod(Z, Prod(Z, Z, Z), Z),
      
         Prod(Z, Prod(Z, Z), Prod(Z, Z))]
        

We build and use a generator for those objects:

>> f:=Shroeder::generator(5):
     
        
>> f() $ i =0..9
     
      Prod(Z, Prod(Z, Prod(Z, Prod(Z, Z)))),
      
         Prod(Z, Prod(Z, Prod(Z, Z, Z))),
      
         Prod(Z, Prod(Z, Z, Prod(Z, Z))),
      
         Prod(Z, Prod(Z, Prod(Z, Z), Z)),
      
         Prod(Z, Z, Prod(Z, Prod(Z, Z))), Prod(Z, Z, Prod(Z, Z, Z)),
      
         Prod(Z, Prod(Z, Prod(Z, Z)), Z), Prod(Z, Prod(Z, Z, Z), Z),
      
         Prod(Z, Prod(Z, Z), Prod(Z, Z)), FAIL
        

Example 5

We create a domain for labeled and unlabeled complete binary trees:

>> BinaryUnlabeled:=combinat::decomposableObjects(
   {B=Union(Z,Prod(B,B))},Labelled=FALSE):
   BinaryLabeled:=combinat::decomposableObjects(
   {B=Union(Z,Prod(B,B))},Labelled=TRUE):
     
        

Number of objects of size 0 to 10 satisfying the specification

>> BinaryUnlabeled::count(i)$i=0..10;
   BinaryLabeled::count(i)$i=0..10;
     
                0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862
      
      0, 1, 2, 12, 120, 1680, 30240, 665280, 17297280, 518918400,
       
         17643225600
        

Example 6

We use the mechanics of combinat::decomposableObjects to present the classical and striking ``balls and bars'' model for integer compositions. A composition like [2,1,3] can be represented as a string of balls and bars by using sequences of balls, separated by bars, here: öoIoIooo". Such strings can be described by the grammar BB = Union(o, oBB, oIBB).

>> ballsAndBars :=
   combinat::decomposableObjects(
      [
       Ball         = Atom("o"),
       Bar          = Epsilon("I"),
       BB           = Union(Ball,
                            Alias(Prod(Ball, BB),op),
                            Alias(Prod(Ball, Bar, BB),op)
                           ),
       BallsAndBars = Alias(BB, _concat)
      ], MainNonTerminal = BallsAndBars):
     

There are 2n-1 balls and bars strings with n balls:

>> ballsAndBars::count(i) $ i = 1..10
     
                   1, 2, 4, 8, 16, 32, 64, 128, 256, 512
        

This can be seen directly from the recurrence relation:

>> ballsAndBars::recurrenceRelation()
     
                             2 u(n - 1) - u(n)
        

Here are all the compositions of 3:

>> ballsAndBars::list(3)
     
                     ["ooo", "ooIo", "oIoo", "oIoIo"]
        

Background

Super-Domain

Dom::BaseDomain

Axioms

Ax::systemRep

Changes

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package