|
%I #17 Apr 06 2020 20:08:36
%S 0,0,0,0,1,2,10,34,158,804,4876,35516,319719,3636064,53349918,
%T 1025758444,26132964903,888605372756,40526634099476,2487361532245964,
%U 205991405080129554,23065538883807036798,3498567662956243132910
%N Number of tangled bicolored graphs on n unlabeled vertices.
%C A bicolored graph on n labeled vertices, k of which are black, and (n-k) of which are white, can be represented as a k X (n-k) matrix, where the (i,j) entry is 1 if the i-th black vertex is adjacent to the j-th white vertex, and 0 otherwise. Then, the graph is tangled if (1) the matrix does not have any rows or columns of all 0's or all 1's; and (2) it is not possible to permute the rows of the matrix and the columns of the matrix to obtain a matrix of the form
%C [ A | J ]
%C [---+---]
%C [ 0 | B ]
%C where the top right block J consists of all 1's, and the bottom left block 0 consists of all 0's.
%H M. Guay-Paquet, A. H. Morales, E. Rowland, <a href="http://arxiv.org/abs/1212.5356">Structure and enumeration of (3+1)-free posets (extended abstract)</a>, arXiv:1212.5356 [math.CO], 2012.
%F G.f.: T(x) = 1 - 2*x - 1/(1+B(x)), where B(x) is the g.f. for A049312.
%e The only tangled bicolored graph on 4 vertices (up to isomorphism) consists of 2 black vertices, 2 white vertices, and 2 edges, with each black vertex joined to a different white vertex.
%t terms = 23;
%t b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Flatten @ Table[Map[ Function[{p}, p + j*x^i], b[n - i*j, i - 1]], {j, 0, n/i}]]];
%t g[n_, k_] := g[n, k] = Sum[Sum[2^Sum[Sum[GCD[i, j]*Coefficient[s, x, i]* Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/ Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n + k, n + k]}], {s, b[n, n]}];
%t A[n_, k_] := g[Min[n, k], Abs[n - k]];
%t A[d_] := Sum[A[n, d - n], {n, 0, d}];
%t B[x_] = Sum[A[d] x^d, {d, 0, terms}];
%t T[x_] = 1 - 2x - 1/B[x];
%t CoefficientList[T[x] + O[x]^terms, x] (* _Jean-François Alcover_, Jan 30 2019, after _Alois P. Heinz_ in A049312 *)
%Y Cf. A221493, A079146.
%K nonn
%O 0,6
%A _Mathieu Guay-Paquet_, Jan 18 2013
|
