Automated Counting of Restricted Motzkin Paths
By AJ Bu
PDF
Published: February 19, 2021 in Volume 1 (2021), Number 2 of the journal Enumerative Combinatorics and Applications
Motzkin paths are simple yet important combinatorial objects. In this paper, we consider families of Motzkin paths with restrictions on
peak heights, valley heights, upwardrun lengths, downwardrun lengths, and flatrun lengths. This paper presents two fully automated methods for
enumerating the paths of such families. The first method uses numeric dynamic programming. While this method often times works, it can be slow and
may not work for larger problems. The second method uses symbolic dynamic programming to solve such problems.
These methods are implemented in the maple packages accompanying this article.
Maple packages
Sample Input and Output Files for Motzkin.txt
Here, a(n) is the number of Motzkin paths of length n avoiding peak heights in A
and valley heights in B. This provides sample outputs of
the first 101 terms of the sequence and the algebraic equation satisfied by the generating function for various
sets finite sets A and B of nonnegative integers.
The input gives you
the output.
Here, a(n) is the number of Motzkin paths of length n avoiding upwardruns of lengths in C, downwardruns with lengths in D,
and flatruns with lengths in E.
This provides sample outputs of
the first 101 terms of the sequence and the algebraic equation satisfied by the generating function for various
sets finite sets C,D, and E of nonnegative integers..
The input gives you
the output.
Here, a(n) is the number of Motzkin paths of length n avoiding avoiding peak heights in A
and valley heights in B, upwardruns of lengths in C, downwardruns with lengths in D,
and flatruns with lengths in E. This provides sample outputs of
the first 101 terms of the sequence and the algebraic equation satisfied by the generating function for various
sets finite sets A,B,C,D, and E of nonnegative integers.
The input gives you
the output.
Here, a(n) is the number of Motzkin paths of length n avoiding peak heights in A
and valley heights in B. This provides sample outputs of
the first 101 terms of the sequence and the algebraic equation satisfied by the generating function for various sets
A and B containing linear expressions of the form c1*r+c2 where c1 and c2 are
nonnegative integers and r is a variable defined over the nonnegative integers.
The input gives you
the output.
Here, a(n) is the number of Motzkin paths of length n avoiding upwardruns of lengths in C, downwardruns with lengths in D,
and flatruns with lengths in E.
This provides sample outputs of
the first 101 terms of the sequence and the algebraic equation satisfied by the generating function for various sets
C, D, and E containing linear expressions of the form c1*r+c2 where c1 and c2 are
nonnegative integers and r is a variable defined over the nonnegative integers.
The input gives you
the output.
Here, a(n) is the number of Motzkin paths of length n avoiding avoiding peak heights in A
and valley heights in B, upwardruns of lengths in C, downwardruns with lengths in D,
and flatruns with lengths in E. This provides sample outputs of
the first 101 terms of the sequence and the algebraic equation satisfied by the generating function for various sets
A, B, C, D, and E containing linear expressions of the form c1*r+c2 where c1 and c2 are
nonnegative integers and r is a variable defined over the nonnegative integers.
The input gives you
the output.
Sample Input and Output Files for MotzkinClever.txt

This provides the algebraic equation satisfied by the ordinary generating function for the sequence enumerating Motzkin paths
that avoid peak heights in A and valley heights in B for various finite sets A and B of nonnegative integers.
The input gives you
the output.

This provides the algebraic equation satisfied by the ordinary generating function for the sequence enumerating Motzkin paths
that avoid upwardruns of lengths in C, downwardruns with lengths in D,
and flatruns with lengths in E for various finite sets C,D, and E of nonnegative integers.
The input gives you
the output.

This provides the algebraic equation satisfied by the ordinary generating function for the sequence enumerating Motzkin paths
that avoid peak heights in A and valley heights in B for various sets A and B containing linear expressions of the form c1*r+c2 where
c1 and c2 are nonnegative
integers and r is a variable defined over the nonnegative integers.
The input gives you
the output.

This provides the algebraic equation satisfied by the ordinary generating function for the sequence enumerating Motzkin paths
that avoid upwardruns of lengths in C, downwardruns with lengths in D,
and flatruns with lengths in E for various sets C,D, and E containing linear expressions of the form c1*r+c2 where c1 and c2 are nonnegative
integers and r is a variable defined over the nonnegative integers.
The input gives you
the output.
AJ Bu's Papers
AJ Bu's Home Page