A357297 -id:A357297 - cp's OEIS frontend

A361901 The number of linear extensions of n fork-join DAGs of width 3.

1, 6, 9072, 163459296, 15205637551104, 4847253138540933120, 4144575934565485291192320, 8072771848739175726302071357440, 31871690751871005247875440218598277120, 233637150127891005003834299796206474735124480, 2970126289229822074571543766217262582458754059468800

Offset: 0

José E. Solsona, Mar 28 2023

nonn

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.
When the width is 3 (i.e. m=3), these fork-join DAGs can be depicted as follows (we omit the first column for n=0 because the graph is empty in this case):
 n |    1    |      2        |          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
   |   \|/   |   \|/   \|/   |   \|/   \|/   \|/
   |    o    |    o     o    |    o     o     o

			a(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

Winston de Greef, Table of n, a(n) for n = 0..99
Wikipedia, Fork-join model

Row m=3 of A357297.

a[n_] := (5n)!/20^n
Table[a[n], {n, 0, 8}]

a(n)=(5*n)!/20^n \\ Winston de Greef, Apr 16 2023

a(n) = (5n)!/20^n.

A362565 The number of linear extensions of n fork-join DAGs of width 4.

Original entry on oeis.org

1, 24, 532224, 237124952064, 765985681152147456, 10915755547826792536473600, 510278911920303453316871670988800, 64243535333922263307871175411271676723200, 18920767554543625469992819764324607588052867481600

Offset: 0

José E. Solsona, Apr 24 2023

nonn

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.
When the width is 4 (i.e., m=4), these fork-join DAGs can be depicted as follows (we omit the first column for n=0 because the graph is empty in this case):
 n |     1     |         2        |             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 o o o o o o
   |   \| |/   |   \| |/   \| |/  |   \| |/   \| |/   \| |/
   |     o     |     o       o    |     o       o       o

			a(1) = 24 is the number of linear extensions of one fork-join DAG of width 4.

Wikipedia, Fork-join model.

Row m=4 of A357297.

a[n_] := (6n)!/30^n
Table[a[n], {n, 0, 8}]

a(n) = (6n)!/30^n.

cp's OEIS Frontend

A361901 The number of linear extensions of n fork-join DAGs of width 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula