<abstract xmlns="http://www.w3.org/1999/xhtml"><p>We consider a generalization of the problem of counting ternary words of a given length which was recently investigated by Koshy and Grimaldi [10]. In particular, we use finite automata and ordinary generating functions in deriving a <italic>k</italic>-ary generalization. This approach allows us to obtain a general setting in which to study this problem over a <italic>k</italic>-ary language. The corresponding class of <italic>n</italic>-letter <italic>k</italic>-ary words is seen to be equinumerous with the closed walks of length <italic>n</italic> − 1 on the complete graph for <italic>k</italic> vertices as well as a restricted subset of colored square-and-domino tilings of the same length. A further polynomial extension of the <italic>k</italic>-ary case is introduced and its basic properties deduced. As a consequence, one obtains some apparently new binomial-type identities via a combinatorial argument.</p></abstract>

We consider a generalization of the problem of counting ternary words of a given length which was recently investigated by Koshy and Grimaldi [10]. In particular, we use finite automata and ordinary generating functions in deriving a k-ary generalization. This approach allows us to obtain a general setting in which to study this problem over a k-ary language. The corresponding class of n-letter k-ary words is seen to be equinumerous with the closed walks of length n − 1 on the complete graph for k vertices as well as a restricted subset of colored square-and-domino tilings of the same length. A further polynomial extension of the k-ary case is introduced and its basic properties deduced. As a consequence, one obtains some apparently new binomial-type identities via a combinatorial argument.

Generalized Jacobsthal numbers and restricted <italic>k</italic>-ary words

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Generalized Jacobsthal numbers and restricted -ary words

We consider a generalization of the problem of counting ternary words of a given length which was recently investigated by Koshy and Grimaldi [10]. In...

Generalized Jacobsthal numbers and restricted k-ary words

Published Online: Nov 01, 2019

Page range: 91 - 108

Received: Oct 14, 2018

Accepted: Jan 04, 2019

DOI: https://doi.org/10.1515/puma-2015-0034

Keywords
-ary word, Jacobsthal number, finite automata, polynomial generalization

© 2019 José L. Ramirez et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Generalized Jacobsthal numbers and restricted k-ary words

Published Online: Nov 01, 2019

Page range: 91 - 108

Received: Oct 14, 2018

Accepted: Jan 04, 2019

DOI: https://doi.org/10.1515/puma-2015-0034

Keywords-ary word, Jacobsthal number, finite automata, polynomial generalization

© 2019 José L. Ramirez et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Keywords
-ary word, Jacobsthal number, finite automata, polynomial generalization