Counting permutations by their rigid patterns (Q696917): Difference between revisions

A rigid pattern is a sequence \(\tau= \tau_1\tau_2\cdots\tau_k\) of \(k\) distinct positive integers. An occurrence of \(\tau\) in an \(n\)-permutation \(\sigma= \sigma_1\sigma_2\cdots\sigma_n\) is a subword \(\sigma_{i+1} \sigma_{i+2}\cdots\sigma_{i+k}\) of \(\sigma\) such that for some integer \(c\), \(\sigma_{i+j}= \tau_j\) for \(1\leq j\leq k\). This article finds the number of \(n\)-permutations containing exactly \(m\) occurrences of a given rigid pattern \(\tau\) as a function of \(n\), \(m\) and certain properties of \(\tau\). This result generalizes a solution given in the beginning of the article to a problem posed by Herbert Wilf. The analogous problem for a pattern, where the subword of \(\sigma\) need not consist of numbers in consecutive positions and its \(i\)th number need only be greater than its \(j\)th one iff \(\tau_i> \tau_j\) rather than being related by the same additive constant, is still unsolved in general. The article refers to some special case solutions in the literature.