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

1, 1, 1, 6, 1, 1, 90, 20, 2, 1, 2520, 1680, 280, 6, 1, 113400, 369600, 277200, 9072, 24, 1, 7484400, 168168000, 1009008000, 163459296, 532224, 120, 1, 681080400, 137225088000, 9777287520000, 15205637551104, 237124952064, 49420800, 720, 1, 81729648000, 182509367040000, 207786914375040000, 4847253138540933120, 765985681152147456, 689598074880000, 6671808000, 5040, 1

Offset: 0

Author

José E. Solsona, Feb 22 2023

Keywords

• nonn
• tabl

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 ...

with columns: A000012 (n=0) and A000142 (n=1).

Examples

			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
		

Links

• Wikipedia, Fork-join model

Crossrefs

Rows m = 0..4 give A000680, A014606, A260331, A361901, A362565.

Columns n = 0..1 give A000012, A000142.

Programs

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}]]

Formula

T(m,n) = (n*(m+2))!/((m+1)^n*(m+2)^n).