# 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.

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'`