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, upward-run lengths, downward-run lengths, and flat-run 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 non-negative integers.
The input gives you
the output.
Here, a(n) is the number of Motzkin paths of length n avoiding upward-runs of lengths in C, downward-runs with lengths in D,
and flat-runs 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 non-negative 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, upward-runs of lengths in C, downward-runs with lengths in D,
and flat-runs 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 non-negative 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
non-negative integers and r is a variable defined over the non-negative integers.
The input gives you
the output.
Here, a(n) is the number of Motzkin paths of length n avoiding upward-runs of lengths in C, downward-runs with lengths in D,
and flat-runs 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
non-negative integers and r is a variable defined over the non-negative 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, upward-runs of lengths in C, downward-runs with lengths in D,
and flat-runs 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
non-negative integers and r is a variable defined over the non-negative 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 non-negative 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 upward-runs of lengths in C, downward-runs with lengths in D,
and flat-runs with lengths in E for various finite sets C,D, and E of non-negative 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 non-negative
integers and r is a variable defined over the non-negative 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 upward-runs of lengths in C, downward-runs with lengths in D,
and flat-runs 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 non-negative
integers and r is a variable defined over the non-negative integers.
The input gives you
the output.
AJ Bu's Papers
AJ Bu's Home Page