Counting occurrences of a pattern of length three with at most two distinct letters in a k-ary word

Toufik Mansour, Armend Shabani

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

Define τ(π) to be the number of subsequences of π that are order-isomorphic to τ. Let τ be a pattern of length three with at most two distinct letters, namely,
τ ∈ {111, 112, 121, 122, 211, 212, 221}.
In this paper, we give an algorithm for finding the generating function
wτ;r(n; y) =X
k≥1
X
π∈[k]n,τ(π)=r
y
k
for the number of k-ary words of length n that contain exactly r occurrences of the pattern τ, for given r ≥ 0. In particular, we obtain explicit formulas for the generating functions wτ;r(n; y), where r = 0, 1.
שפה מקוריתאנגלית
עמודים (מ-עד)183–201
כתב עתJournal of Automata, Languages and Combinatorics
כרך21
מספר גיליון3
סטטוס פרסוםפורסם - 31 דצמ׳ 2016

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Counting occurrences of a pattern of length three with at most two distinct letters in a k-ary word'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי