Pattern occurrences in \(k\)-ary words revisited: a few new and old observations (Q2077272): Difference between revisions

The paper works with patterns interpreted as words over an ordered alphabet and their occurrences interpreted as scattered occurrences of words order-isomorphic to a given one. For example, the word \(22463\) contains two occurrences of the pattern \(21\), namely, \(43\) and \(63\). If a word does not contain any occurrences of a pattern \(p\), we say that it avoids \(p\). The paper contains, first, a new upper bound on the number of \(k\)-ary words avoiding a given pattern, and second, a corollary meaning that if the number of words of length \(n\) over an alphabet of size \(k\) which avoid any of two patterns is the same for all \(k\) and \(n\), then the same is true for the number of permutations of size \(n\), for every \(n\), avoiding them.