Circular digraph walks, \(k\)-balanced strings, lattice paths and Chebychev polynomials (Q1010838)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Circular digraph walks, \(k\)-balanced strings, lattice paths and Chebychev polynomials |
scientific article |
Statements
Circular digraph walks, \(k\)-balanced strings, lattice paths and Chebychev polynomials (English)
0 references
7 April 2009
0 references
Summary: We count the number of walks of length \(n\) on a \(k\)-node circular digraph that cover all \(k\) nodes in two ways. The first way illustrates the transfer-matrix method. The second involves counting various classes of height-restricted lattice paths. We observe that the results also count so-called \(k\)-balanced strings of length \(n\), generalizing a 1996 Putnam problem.
0 references
\(k\)-node circular digraph
0 references
counting walks of given length
0 references
transfer matrix method
0 references
generating function
0 references
Cramer's rule
0 references
Chebyshev polynomial
0 references
bad walks
0 references
height restricted lattice paths
0 references
\(k\)-balanced strings
0 references
