A361901 The number of linear extensions of n fork-join DAGs of width 3.

1, 6, 9072, 163459296, 15205637551104, 4847253138540933120, 4144575934565485291192320, 8072771848739175726302071357440, 31871690751871005247875440218598277120, 233637150127891005003834299796206474735124480, 2970126289229822074571543766217262582458754059468800

Offset: 0

Author

José E. Solsona, Mar 28 2023

Keywords

• nonn

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.

When the width is 3 (i.e. m=3), these fork-join DAGs can be depicted as follows (we omit the first column for n=0 because the graph is empty in this case):

n | 1 | 2 | 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

| \|/ | \|/ \|/ | \|/ \|/ \|/

| o | o o | o o o

Examples

			a(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

• Winston de Greef, Table of n, a(n) for n = 0..99
• Wikipedia, Fork-join model

Crossrefs

Row m=3 of A357297.

Programs

Mathematica

a[n_] := (5n)!/20^n
Table[a[n], {n, 0, 8}]

PARI

a(n)=(5*n)!/20^n \\ Winston de Greef, Apr 16 2023

Formula

a(n) = (5n)!/20^n.