|
%I #10 Apr 16 2023 13:38:36
%S 1,6,9072,163459296,15205637551104,4847253138540933120,
%T 4144575934565485291192320,8072771848739175726302071357440,
%U 31871690751871005247875440218598277120,233637150127891005003834299796206474735124480,2970126289229822074571543766217262582458754059468800
%N The number of linear extensions of n fork-join DAGs of width 3.
%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 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):
%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
%C | \|/ | \|/ \|/ | \|/ \|/ \|/
%C | o | o o | o o o
%H Winston de Greef, <a href="/A361901/b361901.txt">Table of n, a(n) for n = 0..99</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Fork-join_model">Fork-join model</a>
%F a(n) = (5n)!/20^n.
%e a(1) = 6 is the number of linear extensions of one fork-join DAG of width 3. Let the DAG be labeled as follows:
%e 1
%e / | \
%e 2 3 4
%e \ | /
%e 5
%e Then the six linear extensions are:
%e 1 2 3 4 5
%e 1 2 4 3 5
%e 1 3 2 4 5
%e 1 3 4 1 5
%e 1 4 2 3 5
%e 1 4 3 2 5
%t a[n_] := (5n)!/20^n
%t Table[a[n], {n, 0, 8}]
%o (PARI) a(n)=(5n)!/20^n \\ _Winston de Greef_, Apr 16 2023
%Y Row m=3 of A357297.
%K nonn
%O 0,2
%A _José E. Solsona_, Mar 28 2023
| 