login
T(m,n) is the number of linear extensions of n fork-join DAGs of width m, read by downward antidiagonals.
2

%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