Generating Functions and Wilf Equivalence on [Theta][subscript]k-Embeddings

Abstract

Let a word w be comprised of letters w[subscript]1, w[subscript]2,..., w[subscript]n [is an element of] P where P is a poset. For the purpose of this study, let P=the set of positive integers, so that any word is a string of positive integers, where each integer of the word is called a letter. A word u is said to be an embedding into w if there is a string v of consecutive letters in w. In this study, a generalization of factors and embeddings, called [Theta][subscript]k embeddings is investigated. A goal of this study was to determine which words u have the same weight generating function in order to improve methods of solving problems that require the use of factors or embeddings.