A380336 Triangular array read by rows. T(n,k) is the number of ways to choose a size k subset S of [n] and form a labeled acyclic digraph on S. Then form another labeled acyclic digraph on [n]-S. For each pair u in S and v in [n]-S add the directed edge u->v or not, n>=0, 0<=k<=n.
1, 1, 1, 3, 4, 3, 25, 36, 36, 25, 543, 800, 864, 800, 543, 29281, 43440, 48000, 48000, 43440, 29281, 3781503, 5621952, 6255360, 6400000, 6255360, 5621952, 3781503, 1138779265, 1694113344, 1888975872, 1946112000, 1946112000, 1888975872, 1694113344, 1138779265
Offset: 0
Examples
Triangle T(n,k) begins:
1;
1, 1;
3, 4, 3;
25, 36, 36, 25;
543, 800, 864, 800, 543;
29281, 43440, 48000, 48000, 43440, 29281;
...
Links
- E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
- R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.
Programs
-
Mathematica
nn = 6; B[n_] := n! 2^Binomial[n, 2]; e[z_] := Sum[z^n/B[n], {n, 0, nn}]; Map[Select[#, # > 0 &] &,Table[B[n], {n, 0, nn}] CoefficientList[Series[1/e[-u z]*1/e[-z], {z, 0, nn}], {z, u}]] // Grid
Formula
Sum_{n>=0} T(n,k)*y^k*x^n/(2^binomial(n,2)*n!) = 1/E(-y*x)*1/E(-x) where E(x) = Sum_{n>=0} x^n/(2^binomial(n,2)*n!).