login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A221492 Number of tangled bicolored graphs on n unlabeled vertices. 3
0, 0, 0, 0, 1, 2, 10, 34, 158, 804, 4876, 35516, 319719, 3636064, 53349918, 1025758444, 26132964903, 888605372756, 40526634099476, 2487361532245964, 205991405080129554, 23065538883807036798, 3498567662956243132910 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

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

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

M. Guay-Paquet, A. H. Morales, E. Rowland, Structure and enumeration of (3+1)-free posets (extended abstract), arXiv:1212.5356 [math.CO], 2012.

FORMULA

G.f.: T(x) = 1 - 2*x - 1/(1+B(x)), where B(x) is the g.f. for A049312.

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.

MATHEMATICA

terms = 23;

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}]]];

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]}];

A[n_, k_] := g[Min[n, k], Abs[n - k]];

A[d_] := Sum[A[n, d - n], {n, 0, d}];

B[x_] = Sum[A[d] x^d, {d, 0, terms}];

T[x_] = 1 - 2x - 1/B[x];

CoefficientList[T[x] + O[x]^terms, x] (* Jean-Fran├žois Alcover, Jan 30 2019, after Alois P. Heinz in A049312 *)

CROSSREFS

Cf. A221493, A079146.

Sequence in context: A052965 A108924 A281097 * A318696 A116898 A033261

Adjacent sequences:  A221489 A221490 A221491 * A221493 A221494 A221495

KEYWORD

nonn

AUTHOR

Mathieu Guay-Paquet, Jan 18 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 4 11:25 EDT 2020. Contains 334825 sequences. (Running on oeis4.)