We consider a generalization of the problem of counting ternary words of a given length which was recently investigated by Koshy and Grimaldi . 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.
In this note, we provide bijective proofs of some recent identities involving Stirling numbers of the second kind, as previously requested. Our arguments also yield generalizations in terms of a well known q-Stirling number.