|
|
A221493
|
|
Number of tangled bicolored graphs on n labeled vertices.
|
|
3
|
|
|
0, 0, 0, 0, 12, 120, 2460, 64680, 2323692, 111920760, 7272700860, 639739653960, 76764606923532, 12645557866982040, 2878366780307114460, 909775941009828296040, 401039212596034472197932, 247339947733328456032703160, 214013123181627427780427544060
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
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
[ A | J ]
[---+---]
[ 0 | B ]
where the top right block J consists of all 1's, and the bottom left block 0 consists of all 0's.
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: T(x) = 2*e^(-x) - 1 - 1/B(x), where B(x) is the e.g.f. for A047863.
|
|
EXAMPLE
|
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. Given 4 labels, there are 12 distinct ways of labeling the vertices, so a(4) = 1.
|
|
MATHEMATICA
|
nmax = 19;
B[x_] = Sum[Exp[2^n x] x^n/n!, {n, 0, nmax}] + O[x]^nmax;
T[x_] = 2 Exp[-x] - 1 - 1/B[x] + O[x]^nmax;
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|