A049312 -id:A049312 - cp's OEIS frontend

A221492 Number of tangled bicolored graphs on n unlabeled vertices.

0, 0, 0, 0, 1, 2, 10, 34, 158, 804, 4876, 35516, 319719, 3636064, 53349918, 1025758444, 26132964903, 888605372756, 40526634099476, 2487361532245964, 205991405080129554, 23065538883807036798, 3498567662956243132910

Offset: 0

Mathieu Guay-Paquet, Jan 18 2013

nonn

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.

			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.

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

Cf. A221493, A079146.

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 *)

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

A361952 Array read by antidiagonals: T(n,k) is the number of unlabeled posets with n elements together with a function rk mapping each element to a rank between 1 and k such that whenever v covers w in the poset then rk(v) = rk(w) + 1.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 8, 8, 1, 0, 1, 5, 13, 21, 17, 1, 0, 1, 6, 19, 40, 58, 38, 1, 0, 1, 7, 26, 66, 126, 172, 94, 1, 0, 1, 8, 34, 100, 228, 420, 569, 258, 1, 0, 1, 9, 43, 143, 373, 816, 1537, 2148, 815, 1, 0, 1, 10, 53, 196, 571, 1412, 3140, 6342, 9538, 3038, 1, 0

Offset: 0

Andrew Howroyd, Mar 31 2023

A poset is counted once for each admissible ranking function. This is an intermediate step in the computation of A361953 where each graded poset is counted exactly once.

			Array begins:
============================================
n/k| 0 1   2    3    4     5     6     7 ...
---+----------------------------------------
0  | 1 1   1    1    1     1     1     1 ...
1  | 0 1   2    3    4     5     6     7 ...
2  | 0 1   4    8   13    19    26    34 ...
3  | 0 1   8   21   40    66   100   143 ...
4  | 0 1  17   58  126   228   373   571 ...
5  | 0 1  38  172  420   816  1412  2272 ...
6  | 0 1  94  569 1537  3140  5631  9351 ...
7  | 0 1 258 2148 6342 13383 24410 41097 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..860 (first 41 antidiagonals).

Columns k=0..2 are A000007, A000012, A049312.
Rows n=0..4 are A000012, A000027, A034856, A137742.
The labeled version is A361950.
Cf. A361953.

\\ See Links in A361953 for program.
{ my(A=A361952tabl(7)); for(i=1, #A, print(A[i,])) }

A132043 Number of bitransversal (transversal and dual transversal) matroids on n unlabeled elements.

Original entry on oeis.org

2, 4, 8, 17, 38, 95, 268, 917, 4086

Offset: 1

Gordon F. Royle, Oct 30 2007

nonn

A transversal matroid is a matroid whose independent sets are the partial transversals of a family of subsets of [1..n], while a bitransversal matroid is a transversal matroid whose dual is transversal. The principal (or fundamental) transversal matroids enumerated by A049312 form an important subset of bitransversal matroids.

Jensen, P. M., Binary fundamental matroids. Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 281-296, Colloq. Math. Soc. Janos Bolyai, 25, North-Holland, Amsterdam-New York, 1981

Cf. A049312.

cp's OEIS Frontend

A221492 Number of tangled bicolored graphs on n unlabeled vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A361952 Array read by antidiagonals: T(n,k) is the number of unlabeled posets with n elements together with a function rk mapping each element to a rank between 1 and k such that whenever v covers w in the poset then rk(v) = rk(w) + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A132043 Number of bitransversal (transversal and dual transversal) matroids on n unlabeled elements.

Views

Author

Keywords

Comments

References

Crossrefs