A260331 -id:A260331 - cp's OEIS frontend

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

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)

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.

Original entry on oeis.org

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.

A357297 T(m,n) is the number of linear extensions of n fork-join DAGs of width m, read by downward antidiagonals.

Original entry on oeis.org

1, 1, 1, 6, 1, 1, 90, 20, 2, 1, 2520, 1680, 280, 6, 1, 113400, 369600, 277200, 9072, 24, 1, 7484400, 168168000, 1009008000, 163459296, 532224, 120, 1, 681080400, 137225088000, 9777287520000, 15205637551104, 237124952064, 49420800, 720, 1, 81729648000, 182509367040000, 207786914375040000, 4847253138540933120, 765985681152147456, 689598074880000, 6671808000, 5040, 1

Offset: 0

José E. Solsona, Feb 22 2023

The fork-join structure is a modeling structure, commonly seen for example in parallel computing, usually represented as a DAG (or poset). It has an initial "fork" vertex that spawns a number of m independent children vertices (the width) whose output edges are connected to a final "join" vertex. More generally, we can have a number n of these DAGs, each one with m+2 vertices.
The family of fork-join DAGs we are considering here can be depicted as follows (we omit the first column for n=0 because the graph is empty in this case):
m\n|    1    |      2        |          3
---------------------------------------------------
 0 |    o    |     o  o      |       o  o  o
   |    |    |     |  |      |       |  |  |
   |    o    |     o  o      |       o  o  o
---------------------------------------------------
   |    o    |     o  o      |       o  o  o
   |    |    |     |  |      |       |  |  |
 1 |    o    |     o  o      |       o  o  o
   |    |    |     |  |      |       |  |  |
   |    o    |     o  o      |       o  o  o
---------------------------------------------------
   |    o    |    o     o    |    o     o     o
   |   / \   |   / \   / \   |   / \   / \   / \
 2 |  o   o  |  o   o o   o  |  o   o o   o o   o
   |   \ /   |   \ /   \ /   |   \ /   \ /   \ /
   |    o    |    o     o    |    o     o     o
---------------------------------------------------
   |    o    |    o     o    |    o     o     o
   |   /|\   |   /|\   /|\   |   /|\   /|\   /|\
 3 |  o o o  |  o o o o o o  |  o o o o o o o o o
   |   \|/   |   \|/   \|/   |   \|/   \|/   \|/
   |    o    |    o     o    |    o     o     o
The array begins like this:
m\n|0   1         2               3                       4
-----------------------------------------------------------
 0 |1   1         6              90                    2520 ... A000680
 1 |1   1        20            1680                  369600 ... A014606
 2 |1   2       280          277200              1009008000 ... A260331
 3 |1   6      9072       163459296          15205637551104 ... A361901
 4 |1  24    532224    237124952064      765985681152147456 ... A362565
 5 |1 120  49420800 689598074880000 97981404549709824000000 ...
with columns: A000012 (n=0) and A000142 (n=1).

			T(3,1) = 6 is the number of linear extensions of one fork-join DAG of width 3. Let the DAG be labeled as follows:
     1
   / | \
  2  3  4
   \ | /
     5
Then the six linear extensions are:
  1 2 3 4 5
  1 2 4 3 5
  1 3 2 4 5
  1 3 4 1 5
  1 4 2 3 5
  1 4 3 2 5

Wikipedia, Fork-join model

Rows m = 0..4 give A000680, A014606, A260331, A361901, A362565.

Columns n = 0..1 give A000012, A000142.

(* Formula *)
T[m_, n_] := (n*(m+2))!/((m+1)^n*(m+2)^n)
(* 5 X 5 Table *)
Table[T[m, n], {m, 0, 5}, {n, 0, 5}]
(* Eight rows of the triangle *)
Table[Table[T[m, n - m], {m, 0, n}], {n, 0, 8}]
(* As a sequence *)
Flatten[Table[Table[T[m, n - m], {m, 0, n}], {n, 0, 8}]]

T(m,n) = (n*(m+2))!/((m+1)^n*(m+2)^n).

cp's OEIS Frontend

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

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

A357297 T(m,n) is the number of linear extensions of n fork-join DAGs of width m, read by downward antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula