A260332 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.

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

Offset

0,2

Comments

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

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.

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.

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

References

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.

Links

Table of n, a(n) for n=0..6.

M. Paukner, L. Pepin, M. Riehl, and J. Wieser, Pattern Avoidance in Task-Precedence Posets, arXiv:1511.00080 [math.CO], 2015.

Manda Riehl, A 231-avoiding diamond whose associated permutation is 1234.

Sheng-liang Yang and Mei-yang Jiang, Pattern avoiding problems on the hybrid d-trees, J. Lanzhou Univ. Tech., (China, 2023) Vol. 49, No. 2, 144-150. (in Mandarin)

Formula

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

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

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

Example

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.

Crossrefs

Cf. A260331, A260579.

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

Sequence in context: A227934 A349652 A245112 * A254999 A357603 A024486

Adjacent sequences: A260329 A260330 A260331 * A260333 A260334 A260335

Keyword

nonn,more

Author

Manda Riehl, Jul 29 2015

Status

approved