On computing the total displacement number via weighted Motzkin paths

Andreas Bärtschi, Barbara Geissmann, Daniel Graf, Tomas Hruz, Paolo Penna, Thomas Tschager
ETH Zürich, Department of Computer Science
Contact: grafdan@ethz.ch

E.g.: all Motzkin paths of area=9 width=7 height=2
      _       |        _     |       __     |      __   
     /X\/\    |     /\/X\    |     _/XX\    |     /XX\_ 
    /XXXXX\   |    /XXXXX\   |    /XXXXX\   |    /XXXXX\

Dynamic Programs for Counting and Sampling

Theorem 7 Counting and sampling from top to bottom.


Compile and run with: g++ motzkin_topdown.cpp -o m -std=c++11; ./m

Theorem 2 Counting from left to right.

motzkin_leftright_bignum.cpp O(n^4) mem
motzkin_leftright_bignum_memory.cpp O(n^3) mem
output100.txt with M(n,A) and D(n,d) up to 100 (10MB)

Compile and run with: g++ motzkin_leftright.cpp -o m -std=c++11; ./m
For the bigint-versions with arbitrary precision, the CGAL library is required. Then follow these compilation steps:

  • Run: cgal_create_cmake_script
  • To the file CMakeLists.txt add this line:
    set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
  • Run: cmake .
  • Run: make
  • Execute: ./motzkin_leftright_bignum

Markov Chain for Building Block Sampling

Theorem 6 Implementation of the Monte Carlo Markov Chain MBlocks.


Compile and run with: g++ markovmotzkin.cpp -o m -std=c++11; ./m
The program takes as inputs:

  • height: h
  • max height: h_max
  • number of repetitions: stepnumber
  • seed for random generator: seed
  • building block sequence: f_0 p_1 f_1 ... p_h f_h
The program gives as output:
  • building block sequence (after stepnumber many steps, length of sequence might be different): f'_0 p'_1 f'_1 ... p'_h' f'_h'