OFFSET
0,4
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.
The family of fork-join DAGs we are considering here can be depicted as follows (we omit the first column for n=0 because the graph is empty in this case):
m\n| 1 | 2 | 3
---------------------------------------------------
0 | o | o o | o o o
| | | | | | | | |
| o | o o | o o o
---------------------------------------------------
| o | o o | o o o
| | | | | | | | |
1 | o | o o | o o o
| | | | | | | | |
| o | o o | o o o
---------------------------------------------------
| o | o o | o o o
| / \ | / \ / \ | / \ / \ / \
2 | o o | o o o o | o o o o o o
| \ / | \ / \ / | \ / \ / \ /
| o | o o | o o o
---------------------------------------------------
| o | o o | o o o
| /|\ | /|\ /|\ | /|\ /|\ /|\
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
The array begins like this:
m\n|0 1 2 3 4
-----------------------------------------------------------
0 |1 1 6 90 2520 ... A000680
1 |1 1 20 1680 369600 ... A014606
2 |1 2 280 277200 1009008000 ... A260331
3 |1 6 9072 163459296 15205637551104 ... A361901
4 |1 24 532224 237124952064 765985681152147456 ... A362565
5 |1 120 49420800 689598074880000 97981404549709824000000 ...
LINKS
Wikipedia, Fork-join model
FORMULA
T(m,n) = (n*(m+2))!/((m+1)^n*(m+2)^n).
EXAMPLE
T(3,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
(* Formula *)
T[m_, n_] := (n*(m+2))!/((m+1)^n*(m+2)^n)
(* 5 X 5 Table *)
Table[T[m, n], {m, 0, 5}, {n, 0, 5}]
(* Eight rows of the triangle *)
Table[Table[T[m, n - m], {m, 0, n}], {n, 0, 8}]
(* As a sequence *)
Flatten[Table[Table[T[m, n - m], {m, 0, n}], {n, 0, 8}]]
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
José E. Solsona, Feb 22 2023
STATUS
approved