%I #27 May 23 2023 05:38:07
%S 1,1,1,6,1,1,90,20,2,1,2520,1680,280,6,1,113400,369600,277200,9072,24,
%T 1,7484400,168168000,1009008000,163459296,532224,120,1,681080400,
%U 137225088000,9777287520000,15205637551104,237124952064,49420800,720,1,81729648000,182509367040000,207786914375040000,4847253138540933120,765985681152147456,689598074880000,6671808000,5040,1
%N T(m,n) is the number of linear extensions of n fork-join DAGs of width m, read by downward antidiagonals.
%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 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):
%C m\n| 1 | 2 | 3
%C ---------------------------------------------------
%C 0 | o | o o | o o o
%C | | | | | | | | |
%C | o | o o | o o o
%C ---------------------------------------------------
%C | o | o o | o o o
%C | | | | | | | | |
%C 1 | o | o o | o o o
%C | | | | | | | | |
%C | o | o o | o o o
%C ---------------------------------------------------
%C | o | o o | o o o
%C | / \ | / \ / \ | / \ / \ / \
%C 2 | o o | o o o o | o o o o o o
%C | \ / | \ / \ / | \ / \ / \ /
%C | o | o o | o o o
%C ---------------------------------------------------
%C | o | o o | o o o
%C | /|\ | /|\ /|\ | /|\ /|\ /|\
%C 3 | 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
%C The array begins like this:
%C m\n|0 1 2 3 4
%C -----------------------------------------------------------
%C 0 |1 1 6 90 2520 ... A000680
%C 1 |1 1 20 1680 369600 ... A014606
%C 2 |1 2 280 277200 1009008000 ... A260331
%C 3 |1 6 9072 163459296 15205637551104 ... A361901
%C 4 |1 24 532224 237124952064 765985681152147456 ... A362565
%C 5 |1 120 49420800 689598074880000 97981404549709824000000 ...
%C with columns: A000012 (n=0) and A000142 (n=1).
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Fork-join_model">Fork-join model</a>
%F T(m,n) = (n*(m+2))!/((m+1)^n*(m+2)^n).
%e 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:
%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 (* Formula *)
%t T[m_, n_] := (n*(m+2))!/((m+1)^n*(m+2)^n)
%t (* 5 X 5 Table *)
%t Table[T[m, n], {m, 0, 5}, {n, 0, 5}]
%t (* Eight rows of the triangle *)
%t Table[Table[T[m, n - m], {m, 0, n}], {n, 0, 8}]
%t (* As a sequence *)
%t Flatten[Table[Table[T[m, n - m], {m, 0, n}], {n, 0, 8}]]
%Y Rows m = 0..4 give A000680, A014606, A260331, A361901, A362565.
%Y Columns n = 0..1 give A000012, A000142.
%K nonn,tabl
%O 0,4
%A _José E. Solsona_, Feb 22 2023