login
Labelings of n diamond-shaped posets with 4 vertices per diamond where the labels follow the poset relations whose associated reading permutation avoids 231 in the classical sense.
19

%I #62 Jan 09 2024 11:03:28

%S 1,2,18,226,3298,52450,881970

%N Labelings of n diamond-shaped posets with 4 vertices per diamond where the labels follow the poset relations whose associated reading permutation avoids 231 in the classical sense.

%C According to Yang-Jiang (2021) these are the 5-Schroeder numbers. If confirmed, this will prove Michael Weiner's conjectures and enable us to extend the sequence. Yang & Jiang (2021) give an explicit formula for the m-Schroeder numbers in Theorem 2.4. - _N. J. A. Sloane_, Mar 28 2021

%C By diamond-shaped poset with 4 vertices, we mean a poset on four elements with e_1 < e_2, e_1 < e_3, e_2 < e_4, e_3 < e_4, and no order relations between e_2 and e_3. In the Hasse diagram for such a poset, we have a least element, two elements in the level above, and one element in the top level, so the diagram resembles a diamond. The associated permutation is the permutation obtained by reading the labels of each poset by levels left to right, starting with the least element.

%C Also the number of labelings of n diamond-shaped posets with 4 vertices per diamond where the labels follow the poset relations whose associated reading permutation avoids 312 in the classical sense via reverse complement Wilf equivalence.

%C Conjecture: Also the number of lattice paths (Schroeder paths) from (0,0) to (n,4n) with unit steps N=(0,1), E=(1,0) and D=(1,1) staying weakly above the line y = 4x. - _Michael D. Weiner_, Jul 24 2019

%D Sheng-Liang Yang and Mei-yang Jiang, The m-Schröder paths and m-Schröder numbers, Disc. Math. (2021) Vol. 344, Issue 2, 112209. doi:10.1016/j.disc.2020.112209. See Table 1.

%H M. Paukner, L. Pepin, M. Riehl, and J. Wieser, <a href="http://arxiv.org/abs/1511.00080">Pattern Avoidance in Task-Precedence Posets</a>, arXiv:1511.00080 [math.CO], 2015.

%H Manda Riehl, <a href="/A260332/a260332.png">A 231-avoiding diamond whose associated permutation is 1234.</a>

%H Lin Yang, Yu-Yuan Zhang, and Sheng-Liang Yang, <a href="https://doi.org/10.1016/j.laa.2023.12.021">The halves of Delannoy matrix and Chung-Feller properties of the m-Schröder paths</a>, Linear Alg. Appl. (2024).

%H Sheng-liang Yang and Mei-yang Jiang, <a href="https://journal.lut.edu.cn/EN/abstract/abstract528.shtml">Pattern avoiding problems on the hybrid d-trees</a>, J. Lanzhou Univ. Tech., (China, 2023) Vol. 49, No. 2, 144-150. (in Mandarin)

%F There is a complicated recursive formula available in Paukner et al.

%F Yang & Jiang (2021) give an explicit formula for the 5-Schroeder numbers in Theorem 2.4. - _N. J. A. Sloane_, Mar 28 2021

%F Conjecture: a(n) = Sum_{k=1..n} binomial(n,k)*binomial(4*n,k-1)*2^k/n for n > 0. - _Michael D. Weiner_, Jul 23 2019

%F From _Peter Bala_, Jun 16 2023: (Start)

%F Conjectures: 1) the g.f. A(x) = 1 + 2*x + 18*x^2 + 226*x^3 + ... satisfies A(x)^4 = (1/x) * the series reversion of ((1 - x)/(1 + x))^4.

%F 2) Define b(n) = (1/4) * [x^n] ((1 + x)/(1 - x))^(4*n). Then A(x) = exp( Sum_{n >= 1} b(n)*x^n/n ).

%F 3) a(n) = 2 * hypergeom([1 - n, -4*n], [2], 2) for n >= 1 (equivalent to Weiner's conjecture above).

%F 4) [x^n] A(x)^n = (2*n) * hypergeom([1 - n, 1 - 5*n], [2], 2) for n >= 1. (End)

%e For a single diamond (n=1) poset with 4 vertices, we must label the least element 1 and the greatest element 4, and the two central elements can be labeled either 2, 3 or 3, 2 respectively. Thus the associated permutations are 1234 and 1324.

%Y Cf. A260331, A260579.

%Y The sequences listed in Yang-Jiang's Table 1 appear to be A006318, A001003, A027307, A034015, A144097, A243675, A260332, A243676. - _N. J. A. Sloane_, Mar 28 2021

%K nonn,more

%O 0,2

%A _Manda Riehl_, Jul 29 2015