A finite word poset (Q5942562)

The posets \(P^{(n)}\) denote the collections of all sequences of length \(n\) on a finite alphabet \(\Gamma= \{1,2,\dots, k\}\) ordered by subsequence containment with \(P^{(n)}_i\) comprising all \(k^i\) \(I\)-sequences as rank \(i\) elements. Investigated in the light of the poset of all finite sequences on \(\Gamma\), whose combinatorial properties are interesting, important and well-studied, similarly interesting results are obtained as well for the (poset) ideals \(B_{k,n}\) of \(P^{(n)}\) generated by \((w_1\cdots w_k)\cdots(w_1\cdots w_k) w_1\cdots w_\ell\), where \(\ell\equiv n\pmod k\) and \(w_1\cdots w_k\) is a fixed permutation of \(\Gamma\) (or the reverse of such a sequence) equipped with the derived (induced) order. Thus, e.g., if \(\pi\) is a permutation of \(\Gamma\), \(\sigma_\pi(w_1\cdots w_\ell)= \pi(w_1)\cdots \pi(w_\ell)\), \(\sigma_\pi\in \text{Sym}_k\cong S_k\), and \(\rho\) reverses words, then, for \(n> 2\), \(\alpha\in \Aut(P^{(n)})\) implies \(\alpha= \pi\rho\) or \(\alpha= \pi\), \(\Aut(P^{(n)})= \text{Sym}_k\otimes Z_2\), or, if \(n= 2\), \(\Aut(P^{(n)})= \text{Sym}_k\otimes Z^{{k\choose 2}}\). If \(\overline N(j,\xi;k)\) denotes the number of \(j\)-sequences not containing \(\xi\), then \(\overline N(j,\xi,k)= \sum^{|\xi|- 1}_{i=0} {j\choose i}(k- 1)^{(j- i)}\), \(|\xi|\) is the length of \(\xi\). The cardinality of a maximum antichain is \(k^n\). Further combinatorial properties of interest are obtained and the theorem of Burosch, Franke and Röhl is provided with an alternative proof, while the BLYM inequality is also verified via the normalized matching property established for the \(P^{(n)}\).