A362565 -id:A362565 - cp's OEIS frontend

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

José E. Solsona, Feb 22 2023

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

			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

Wikipedia, Fork-join model

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

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

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula