Circular digraph walks, \(k\)-balanced strings, lattice paths and Chebychev polynomials (Q1010838)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5541013
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Circular digraph walks, \(k\)-balanced strings, lattice paths and Chebychev polynomials |
scientific article; zbMATH DE number 5541013 |
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
0.85888547
0 references
0 references
0.85579664
0 references
0 references
0.85472363
0 references
0.8546174
0 references
0.85181475
0 references
0 references
