On computing the total displacement number via weighted Motzkin paths

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.

motzkin_topdown.cpp

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

Theorem 2 Counting from left to right.

motzkin_leftright.cpp
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.

markovmotzkin.cpp

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'