A381192 Irregular triangle read by rows. Properly color the vertices of a simple labeled graph on [n] using exactly n colors c_1<c_2<...<c_n (in other words, use each color exactly once). Orient the edges according to the strict order on the colors. T(n,k) is the number of such graphs with exactly k descents, n>=0, 0<=k<=binomial(n,2).

1, 1, 3, 1, 21, 19, 7, 1, 315, 516, 419, 208, 65, 12, 1, 9765, 24186, 31445, 27488, 17538, 8420, 3050, 816, 153, 18, 1, 615195, 2080323, 3769767, 4754751, 4592847, 3555479, 2257723, 1188595, 519745, 187705, 55237, 12941, 2325, 301, 25, 1

Offset

0,3

Comments

A descent in a labeled directed graph is an edge s->t such that s>t.

T(n,0) = A005329(n).

Sum_{k>=0} T(n,k)*k = A005329(n)*n(n-1)/8.

Links

Table of n, a(n) for n=0..41.

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020.

Example

     1;
     1;
     3,     1;
    21,    19,     7,     1;
   315,   516,   419,   208,    65,   12,   1;
  9765, 24186, 31445, 27488, 17538, 8420, 3050, 816, 153, 18, 1;
  ...

Mathematica

nn = 6; B[n_] :=FunctionExpand[QFactorial[n, (1 + u y)/(1 + y)]] (1 + y)^Binomial[n, 2]; e[z_] := Sum[z^n/B[n], {n, 0, nn}]; Map[CoefficientList[#, u] &, Table[B[n], {n, 0, nn}] CoefficientList[Series[1/(1 - z), {z, 0, nn}], z] /. y -> 1] // Grid

Crossrefs

CF. A005329, A381058, A011266 (row sums), A381102.

Sequence in context: A136236 A113090 A223549 * A138354 A193632 A346412

Adjacent sequences: A381189 A381190 A381191 * A381193 A381194 A381195

Keyword

nonn,tabf

Author

Geoffrey Critzer, Feb 16 2025

Status

approved