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

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

Offset

0,2

Comments

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

Links

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

Wikipedia, Fork-join model.

Formula

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

Example

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

Mathematica

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

Crossrefs

Row m=4 of A357297.

Sequence in context: A289746 A289640 A319977 * A268505 A172734 A159191

Adjacent sequences: A362562 A362563 A362564 * A362566 A362567 A362568

Keyword

nonn

Author

José E. Solsona, Apr 24 2023

Status

approved