login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #10 May 15 2023 08:43:16

%S 1,24,532224,237124952064,765985681152147456,

%T 10915755547826792536473600,510278911920303453316871670988800,

%U 64243535333922263307871175411271676723200,18920767554543625469992819764324607588052867481600

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

%C 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.

%C 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):

%C n | 1 | 2 | 3

%C ------------------------------------------------------------

%C | o | o o | o o o

%C | /| |\ | /| |\ /| |\ | /| |\ /| |\ /| |\

%C | o o o o | o o o o o o o o | o o o o o o o o o o o o

%C | \| |/ | \| |/ \| |/ | \| |/ \| |/ \| |/

%C | o | o o | o o o

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Fork-join_model">Fork-join model</a>.

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

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

%t a[n_] := (6n)!/30^n

%t Table[a[n], {n, 0, 8}]

%Y Row m=4 of A357297.

%K nonn

%O 0,2

%A _José E. Solsona_, Apr 24 2023