A240955 Triangular array read by rows. T(n,k) is the number of k-colored labeled digraphs with n vertices, n>=1, 1<=k<=n.

1, 1, 8, 1, 96, 384, 1, 2048, 36864, 98304, 1, 84480, 6881280, 62914560, 125829120, 1, 7221248, 3043491840, 80530636800, 483183820800, 773094113280, 1, 1218502656, 3326443782144, 260661565194240, 3752083429785600, 16624615811973120, 22166154415964160, 1, 421846581248, 9253226255745024, 2290594981959696384, 75808248102597427200, 726340547902313594880, 2542191917658097582080, 2905362191609254379520

Offset

1,3

Comments

Here, a k-colored digraph is a digraph whose labels are colored with exactly k colors so that no two adjacent vertices have the same color.

Links

Table of n, a(n) for n=1..36.

Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.

Formula

T(n,k)= n!*2^(n^2)*[x^n] (A(x) - 1)^k where A(x)=Sum{n>=0}x^n/(n!*2^(n^2)).

T(n,n)= n!*2^(n^2-n).

Example

1,
1, 8,
1, 96,      384,
1, 2048,    36864,      98304,
1, 84480,   6881280,    62914560,    125829120,
1, 7221248, 3043491840, 80530636800, 483183820800, 773094113280
T(2,2)=8 because there are 4 directed graphs on 4 labeled nodes and each is counted two times.  4*2=8.

Mathematica

nn=10; f[x_]:=Sum[x^n/(n!*2^(2*Binomial[n, 2])), {n, 0, nn}]; Map[Select[#, #>0&]&, Drop[Transpose[Table[Table[n!*2^(2*Binomial[n, 2]), {n, 0, nn}]CoefficientList[Series[(f[x]-1)^k, {x, 0, nn}], x], {k, 1, nn}]], 1]]//Grid

Crossrefs

Sequence in context: A254933 A174503 A048786 * A132056 A051187 A284865

Adjacent sequences: A240952 A240953 A240954 * A240956 A240957 A240958

Keyword

nonn,tabl

Author

Geoffrey Critzer, Aug 04 2014

Status

approved