Manda Riehl - cp's OEIS frontend

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

1, 2, 106, 5976, 387564, 27247446, 2020632046, 155622020610, 12327937844924, 998103225615208

Offset: 0

Manda Riehl, Jul 29 2015

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.

Additional terms were provided by David Bevan.

			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.

M. Paukner, L. Pepin, M. Riehl, and J. Wieser, Pattern Avoidance in Task-Precedence Posets, arXiv:1511.00080 [math.CO], 2015.
Manda Riehl, A 321-avoiding diamond with associated permutation 1234.

Cf. A260331, A260332.

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.

Original entry on oeis.org

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

Offset: 0

Manda Riehl, Jul 29 2015

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

			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.

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.

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.
Jun Yan, Lattice paths enumerations weighted by ascent lengths, arXiv:2501.01152 [math.CO], 2025. See p. 11.
Lin Yang, Yu-Yuan Zhang, and Sheng-Liang Yang, The halves of Delannoy matrix and Chung-Feller properties of the m-Schröder paths, Linear Alg. Appl. (2024).
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)

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

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..n} binomial(n,k)*binomial(4*n,k-1)*2^k/n for n > 0. - Michael D. Weiner, Jul 23 2019
From Peter Bala, Jun 16 2023: (Start)
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.
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 ).
3) a(n) = 2 * hypergeom([1 - n, -4*n], [2], 2) for n >= 1 (equivalent to Weiner's conjecture above).
4) [x^n] A(x)^n =  (2*n) * hypergeom([1 - n, 1 - 5*n], [2], 2) for n >= 1. (End)

A260331 Labelings of n diamond-shaped posets with 4 vertices per diamond where the labels follow the poset relations.

Original entry on oeis.org

1, 2, 280, 277200, 1009008000, 9777287520000, 207786914375040000, 8508874143657888000000, 611958228411875304960000000, 72094798889203029677337600000000, 13177487340968529764423766528000000000, 3577714168047637768100581459885056000000000, 1392303245637418713834022280928868392960000000000

Offset: 0

Manda Riehl, Jul 29 2015

nonn

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.

			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.

M. Paukner, L. Pepin, M. Riehl, and J. Wieser, Pattern Avoidance in Task-Precedence Posets, arXiv:1511.00080 [math.CO], 2015.
Manda Riehl, A labelling of a diamond with 4 vertices so that the labels follow the poset relations.

Cf. A260332, A260579.

Table[(4 n)!/12^n, {n, 0, 12}] (* Michael De Vlieger, Apr 06 2016 *)

a(n) = (4n)!/12^n.

More terms from Michael De Vlieger, Apr 06 2016

a(4) corrected by Georg Fischer, May 08 2021

A257995 Forests of binary shrubs on 3n vertices avoiding 321.

Original entry on oeis.org

1, 2, 37, 866, 23285, 679606, 20931998, 669688835, 22040134327, 741386199872, 25376258521393, 880977739374392, 30946637156662975, 1097929752363923490, 39284677690031136567, 1415992852373003788459

Offset: 0

Manda Riehl, May 15 2015

nonn

We define a shrub as a rooted, ordered tree with the only vertices being the root and leaves. We then label our shrubs' vertices with integers such that each child has a larger label than its parent. We associate a permutation to a tree by reading the labels from left to right by levels, starting with the root. A forest is an ordered collection of trees where all vertices in the forest have distinct labels. We associate a permutation to a forest by reading the permutation associated to each tree and then concatenating. We then enumerate labeled forests of binary shrubs whose associated permutation avoids 321.

David Bevan, Table of n, a(n) for n = 0..993
D Bevan, D Levin, P Nugent, J Pantone, L Pudwell, Pattern avoidance in forests of binary shrubs, arXiv preprint arXiv:1510:08036, 2015
M. Riehl, Forests of binary shrubs avoiding patterns of length 3

A001764, A002293, A060941 and A144097 enumerate binary shrubs avoiding other patterns of length 3.

gf := RootOf(_Z^10*z^10+18*_Z^9*z^9+123*_Z^8*z^8+(-3*z^8+420*z^7+54*z^6)*_Z^7+(-36*z^7+751*z^6+486*z^5)*_Z^6+(-138*z^6+354*z^5+1053*z^4)*_Z^5+(3*z^6-228*z^5-213*z^4+162*z^3+729*z^2)*_Z^4+(18*z^5-215*z^4+2*z^3-360*z^2)*_Z^3+(15*z^4+24*z^3-71*z^2-54*z)*_Z^2+(-z^4+24*z^3-8*z^2+54*z-1)*_Z+4*z^2+4*z+1)^(1/2):
seq(coeff(series(gf,z,21),z,i),i=0..20);

b[k_]:=k(k+1)/2;n[k_]:=n[k]=Join[{b[k+1],b[k+1]-1},Table[b[i],{i,k,1,-1}],{1}];v[1]={1,0,1};v[k_]:=v[k]=Module[{s=MapIndexed[#1n[First@#2]&,v[k-1]]},Table[Total[If[i>Length@#,0,#[[i]]]&/@s],{i,Length@Last@s}]];a[k_]:=a[k]=Total@v[k];Array[a,20] (* David Bevan, Oct 27 2015 *)

A246747 The number of binary heaps on n elements whose breadth-first search reading word avoids 231.

Original entry on oeis.org

1, 1, 1, 2, 3, 7, 14, 37, 80, 222, 544, 1601, 4095, 12416, 33785, 105769, 293747, 935184, 2717376, 8848014, 26134254, 86210716, 262068267, 877833206, 2695238060, 9109101156, 28619396967, 97879220771, 310021153392, 1067906857449, 3440140082033, 11957123227292

Offset: 0

Manda Riehl, Sep 04 2014

nonn

Also, the number of binary heaps on n elements whose breadth-first search reading word avoids 312.
Note that a breadth-first search reading word is equivalent to reading the tree labels left to right by levels, starting with the root.
For more information on heaps, see A056971.

			A heap on 4 elements is pictured in the 2nd link, and has breadth first reading word abcd. Then for n = 4 the a(4) = 3 heaps have reading words 1234, 1243, and 1324.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
D. Levin, L. Pudwell, M. Riehl, A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.
Manda Riehl (joint work with Derek Levin, Lara Pudwell, and Adam Sandberg), Page 92 of the Permutation Patterns 2014 Abstract Book .
Manda Riehl, A heap on 4 elements

May be equal to A245899.

Cf. A000108, A056971, A246829.

a(n) = Sum_{i=0..floor((n-1)/2)} A000108(i)*a(n-i-1) for n > 0.

A245894 Number of labeled increasing binary trees on 2n-1 nodes whose breadth-first reading word avoids 231.

Original entry on oeis.org

1, 2, 14, 163, 2558

Offset: 1

Manda Riehl, Aug 22 2014

The number of labeled increasing binary trees with an associated permutation avoiding 231 in the classical sense. The tree’s permutation is found by recording the labels in the order they appear in a breadth-first search. (Note that a breadth-first search reading word is equivalent to reading the tree labels left to right by levels, starting with the root).

In some cases, the same breadth-first search reading permutation can be found on differently shaped trees. This sequence gives the number of trees, not the number of permutations.

			When n=3, a(n)=14.  In the Links above we show the fourteen labeled increasing binary trees on five nodes whose permutation avoids 231.

Manda Riehl, For n = 3: the 14 labeled trees on 5 nodes whose associated permutation avoids 231.

A245888 gives the number of unary-binary trees instead of binary trees.

A245901 gives the number of permutations which avoid 231 that are breadth-first reading words on labeled increasing binary trees.

A246829 The number of binary heaps on n elements whose breadth-first search reading word avoids 321.

Original entry on oeis.org

1, 1, 2, 3, 7, 16, 45, 111, 318, 881, 2686, 8033, 25470, 80480, 263977, 862865, 2891344, 9706757, 33178076, 113784968, 395303480, 1379160685, 4859274472, 17195407935, 61310096228, 219520467207, 790749207801, 2859542098634, 10391610220375, 37897965144166

Offset: 1

Manda Riehl, Sep 04 2014

nonn

Note that a breadth-first search reading word is equivalent to reading the tree labels left to right by levels, starting with the root.

For more information on heaps, see A056971.

			A heap on 4 elements is pictured in the 2nd link, and has breadth first reading word abcd. Then for n = 4 the a(4) = 3 heaps have reading words 1234, 1243, and 1324.

D. Levin, L. Pudwell, M. Riehl, A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014. [broken link]
Manda Riehl (joint work with Derek Levin, Lara Pudwell, and Adam Sandberg), Page 92 of the Permutation Patterns 2014 Abstract Book
Eric Weisstein's World of Mathematics, Heap

Cf. A056971, A246747.

A245903 Number of permutations of length 2n-1 avoiding 321 that can be realized on increasing binary trees.

Original entry on oeis.org

1, 2, 10, 79, 753

Offset: 1

Manda Riehl, Aug 22 2014

The number of permutations of length 2n-1 avoiding 321 in the classical sense which can be realized as labels on an increasing binary tree read in the order they appear in a breadth-first search. (Note that breadth-first search reading word is equivalent to reading the tree left to right by levels, starting with the root.)

In some cases, more than one tree results in the same breadth-first search reading word, but here we count the permutations, not the trees.

			For n=3, the a(3)= 10 permutations can be read from the sample trees given in the Links section above.

Manda Riehl, When n=3, the 10 permutations of length 5 that avoid 321 and can be realized on increasing binary trees.
Manda Riehl, Maple file used to calculate the terms.

A245903 appears to be the terms of A245900 with odd indices. A245896 is the number of increasing unary-binary trees whose breadth-first reading word avoids 321.

A245902 Number of permutations of length 2n-1 avoiding 312 that can be realized on increasing binary trees.

Original entry on oeis.org

1, 2, 7, 37, 222

Offset: 1

Manda Riehl, Aug 22 2014

The number of permutations of length 2n-1 avoiding 312 in the classical sense which can be realized as labels on an increasing binary tree read in the order they appear in a breadth-first search. (Note that breadth-first search reading word is equivalent to reading the tree left to right by levels, starting with the root.)

In some cases, more than one tree results in the same breadth-first search reading word, but here we count the permutations, not the trees.

			For n=3, the a(3)= 7 permutations can be read from the sample trees given in the Links section above.

Manda Riehl, When n=3, the 7 permutations of length 5 that avoid 312 and can be realized on increasing binary trees.

A245902 appears to be the terms of A245899 with odd indices. A245895 is the number of increasing unary-binary trees whose breadth-first reading word avoids 312.

A245901 Number of permutations of length 2n-1 avoiding 231 that can be realized on increasing binary trees.

Original entry on oeis.org

1, 2, 10, 74, 667

Offset: 1

Manda Riehl, Aug 22 2014

The number of permutations of length 2n-1 avoiding 231 in the classical sense which can be realized as labels on an increasing binary tree read in the order they appear in a breadth-first search. (Note that breadth-first search reading word is equivalent to reading the tree left to right by levels, starting with the root.)

In some cases, more than one tree results in the same breadth-first search reading word, but here we count the permutations, not the trees.

			For n=3, the a(3)= 10 permutations can be read from the sample trees given in the Links section above.

Manda Riehl, When n=3, the 10 permutations of length 5 that avoid 231 and can be realizeed on increasing binary trees.

A245901 appears to be the terms of A245898 with odd indices. A245894 is the number of increasing unary-binary trees whose breadth-first reading word avoids 231.

cp's OEIS Frontend

User: Manda Riehl

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A260331 Labelings of n diamond-shaped posets with 4 vertices per diamond where the labels follow the poset relations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A257995 Forests of binary shrubs on 3n vertices avoiding 321.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A246747 The number of binary heaps on n elements whose breadth-first search reading word avoids 231.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A245894 Number of labeled increasing binary trees on 2n-1 nodes whose breadth-first reading word avoids 231.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A246829 The number of binary heaps on n elements whose breadth-first search reading word avoids 321.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A245903 Number of permutations of length 2n-1 avoiding 321 that can be realized on increasing binary trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A245902 Number of permutations of length 2n-1 avoiding 312 that can be realized on increasing binary trees.

Views

Author

Keywords

Comments