cp's OEIS Frontend

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

%I A361901 #14 Aug 02 2024 12:04:04
%S A361901 1,6,9072,163459296,15205637551104,4847253138540933120,
%T A361901 4144575934565485291192320,8072771848739175726302071357440,
%U A361901 31871690751871005247875440218598277120,233637150127891005003834299796206474735124480,2970126289229822074571543766217262582458754059468800
%N A361901 The number of linear extensions of n fork-join DAGs of width 3.
%C A361901 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 A361901 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):
%C A361901  n |    1    |      2        |          3
%C A361901 ---------------------------------------------------
%C A361901    |    o    |    o     o    |    o     o     o
%C A361901    |   /|\   |   /|\   /|\   |   /|\   /|\   /|\
%C A361901    |  o o o  |  o o o o o o  |  o o o o o o o o o
%C A361901    |   \|/   |   \|/   \|/   |   \|/   \|/   \|/
%C A361901    |    o    |    o     o    |    o     o     o
%H A361901 Winston de Greef, <a href="/A361901/b361901.txt">Table of n, a(n) for n = 0..99</a>
%H A361901 Wikipedia, <a href="https://en.wikipedia.org/wiki/Fork-join_model">Fork-join model</a>
%F A361901 a(n) = (5n)!/20^n.
%e A361901 a(1) = 6 is the number of linear extensions of one fork-join DAG of width 3. Let the DAG be labeled as follows:
%e A361901      1
%e A361901    / | \
%e A361901   2  3  4
%e A361901    \ | /
%e A361901      5
%e A361901 Then the six linear extensions are:
%e A361901   1 2 3 4 5
%e A361901   1 2 4 3 5
%e A361901   1 3 2 4 5
%e A361901   1 3 4 1 5
%e A361901   1 4 2 3 5
%e A361901   1 4 3 2 5
%t A361901 a[n_] := (5n)!/20^n
%t A361901 Table[a[n], {n, 0, 8}]
%o A361901 (PARI) a(n)=(5*n)!/20^n \\ _Winston de Greef_, Apr 16 2023
%Y A361901 Row m=3 of A357297.
%K A361901 nonn
%O A361901 0,2
%A A361901 _José E. Solsona_, Mar 28 2023