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 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
LINKS
Winston de Greef, Table of n, a(n) for n = 0..99
Wikipedia, Fork-join model
FORMULA
a(n) = (5n)!/20^n.
EXAMPLE
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
MATHEMATICA
a[n_] := (5n)!/20^n
Table[a[n], {n, 0, 8}]
PROG
(PARI) a(n)=(5*n)!/20^n \\ Winston de Greef, Apr 16 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
José E. Solsona, Mar 28 2023
STATUS
approved