Pattern avoidance in extensions of comb-like posets (Q2345778)

A linear extension of a partially ordered set (poset) is a permutation of the poset's elements that respects the poset's relations. A permutation \(v\) is said to be \(w\)-avoiding if no subsequence of \(v\) has the same relative order as \(w\). Special posets, called combs are considered. A comb consists of a spine (a fully ordered set) and several teeth (fully ordered sets too), where the first element of each tooth coincides with a corresponding element of the spine. Enumerations of linear extensions for two special type of integer posets (namely type-\(\alpha\) and type-\(\beta\)) that avoid some length-3 patterns are considered. If \(A_w(P)\) denotes the number of linear extensions of the poset \(P\) avoiding \(w\), and \(K_{s,t}^\alpha\) (resp. \(K_{s,t}^\beta\)) denotes the number of combs with spine of length \(s\) and teeth of length \(t\) of type-\(\alpha\) (resp. type-\(\beta\)), then the main results of the paper can be written as: \(\displaystyle A_{312}\big(K_{s,t}^\beta\big) = \frac{1}{ts+1}{ s(t+1) \choose s}\) for \(t>1\) (the number of \((t+1)\)-ary trees) and \(\displaystyle A_{213}\big(K_{s,t}^\alpha\big) = \frac{1}{s+1}{ 2s \choose s}\) for \(t > 1\) (the number of binary trees).