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,2

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

Links

Winston de Greef, Table of n, a(n) for n = 0..99

Wikipedia, Fork-join model

Formula

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

Example

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

Mathematica

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

Prog

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

Crossrefs

Row m=3 of A357297.

Sequence in context: A137040 A357805 A172733 * A329911 A088021 A102979

Adjacent sequences: A361898 A361899 A361900 * A361902 A361903 A361904

Keyword

nonn

Author

José E. Solsona, Mar 28 2023

Status

approved