cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A357297 #27 May 23 2023 05:38:07
%S A357297 1,1,1,6,1,1,90,20,2,1,2520,1680,280,6,1,113400,369600,277200,9072,24,
%T A357297 1,7484400,168168000,1009008000,163459296,532224,120,1,681080400,
%U A357297 137225088000,9777287520000,15205637551104,237124952064,49420800,720,1,81729648000,182509367040000,207786914375040000,4847253138540933120,765985681152147456,689598074880000,6671808000,5040,1
%N A357297 T(m,n) is the number of linear extensions of n fork-join DAGs of width m, read by downward antidiagonals.
%C A357297 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 A357297 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):
%C A357297 m\n|    1    |      2        |          3
%C A357297 ---------------------------------------------------
%C A357297  0 |    o    |     o  o      |       o  o  o
%C A357297    |    |    |     |  |      |       |  |  |
%C A357297    |    o    |     o  o      |       o  o  o
%C A357297 ---------------------------------------------------
%C A357297    |    o    |     o  o      |       o  o  o
%C A357297    |    |    |     |  |      |       |  |  |
%C A357297  1 |    o    |     o  o      |       o  o  o
%C A357297    |    |    |     |  |      |       |  |  |
%C A357297    |    o    |     o  o      |       o  o  o
%C A357297 ---------------------------------------------------
%C A357297    |    o    |    o     o    |    o     o     o
%C A357297    |   / \   |   / \   / \   |   / \   / \   / \
%C A357297  2 |  o   o  |  o   o o   o  |  o   o o   o o   o
%C A357297    |   \ /   |   \ /   \ /   |   \ /   \ /   \ /
%C A357297    |    o    |    o     o    |    o     o     o
%C A357297 ---------------------------------------------------
%C A357297    |    o    |    o     o    |    o     o     o
%C A357297    |   /|\   |   /|\   /|\   |   /|\   /|\   /|\
%C A357297  3 |  o o o  |  o o o o o o  |  o o o o o o o o o
%C A357297    |   \|/   |   \|/   \|/   |   \|/   \|/   \|/
%C A357297    |    o    |    o     o    |    o     o     o
%C A357297 The array begins like this:
%C A357297 m\n|0   1         2               3                       4
%C A357297 -----------------------------------------------------------
%C A357297  0 |1   1         6              90                    2520 ... A000680
%C A357297  1 |1   1        20            1680                  369600 ... A014606
%C A357297  2 |1   2       280          277200              1009008000 ... A260331
%C A357297  3 |1   6      9072       163459296          15205637551104 ... A361901
%C A357297  4 |1  24    532224    237124952064      765985681152147456 ... A362565
%C A357297  5 |1 120  49420800 689598074880000 97981404549709824000000 ...
%C A357297 with columns: A000012 (n=0) and A000142 (n=1).
%H A357297 Wikipedia, <a href="https://en.wikipedia.org/wiki/Fork-join_model">Fork-join model</a>
%F A357297 T(m,n) = (n*(m+2))!/((m+1)^n*(m+2)^n).
%e A357297 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:
%e A357297      1
%e A357297    / | \
%e A357297   2  3  4
%e A357297    \ | /
%e A357297      5
%e A357297 Then the six linear extensions are:
%e A357297   1 2 3 4 5
%e A357297   1 2 4 3 5
%e A357297   1 3 2 4 5
%e A357297   1 3 4 1 5
%e A357297   1 4 2 3 5
%e A357297   1 4 3 2 5
%t A357297 (* Formula *)
%t A357297 T[m_, n_] := (n*(m+2))!/((m+1)^n*(m+2)^n)
%t A357297 (* 5 X 5 Table *)
%t A357297 Table[T[m, n], {m, 0, 5}, {n, 0, 5}]
%t A357297 (* Eight rows of the triangle *)
%t A357297 Table[Table[T[m, n - m], {m, 0, n}], {n, 0, 8}]
%t A357297 (* As a sequence *)
%t A357297 Flatten[Table[Table[T[m, n - m], {m, 0, n}], {n, 0, 8}]]
%Y A357297 Rows m = 0..4 give A000680, A014606, A260331, A361901, A362565.
%Y A357297 Columns n = 0..1 give A000012, A000142.
%K A357297 nonn,tabl
%O A357297 0,4
%A A357297 _José E. Solsona_, Feb 22 2023