Some combinatorial interpretations of \(q\)-analogs of Schröder numbers (Q1306593): Difference between revisions

Recall that the Schröder numbers \(R_n\) are defined by the recurrence relation \(R_0=1\), \(R_{n+1}= R_n+ \sum^n_{k=0} R_kR_{n-k}\). The paper studies two \(q\)-analogues of the Schröder numbers, \(S_n(q)\) and \(\overline S_n(x,q)\), where these \(q\)-analogues are defined by the recurrences \[ S_0(q)= 1,\quad S_{n+1}(q)= S_n(q)+ \sum^n_{k=0} S_k(q) S_{n-k}(q) q^{n- k+1}, \] and \[ \overline S_1(x,q)= 2xq,\quad \overline S_{n+1}(x,q)= 2xq\overline S_n(x,q)+\overline S_n(xq,q)+ \sum^{n-1}_{k= 0}\overline S_k(xq,q)\overline S_{n-k}(x, q). \] Recall that Schröder paths are paths from \((0,0)\) to \((n,n)\) using steps \((0,1)\), \((1,0)\) and \((1,1)\), and Schröder paths are enumerated by the Schröder numbers. It turns out that the generating function \(S_n(q)\) counts Schröder paths by area. The number of permutations of \(1,2,\dots, n\) avoiding the patterns 4231 and 4132 is \(R_{n-1}\), and the generating function \(S_{n-1}(q)\) counts permutations of \(1,2,\dots, n\) avoiding the patterns 4231 and 4132 by the number of inversions. The generating function of 1-colored parallelogram polyominoes having parameter \(2n\) according to their width and area is equal to \(\overline S_{n-1}(x,q)\).