A332964 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs on n nodes with exactly k bipartite connected components, n >= 0, 0 <= k <= n.

1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 3, 4, 2, 1, 1, 16, 9, 5, 2, 1, 1, 96, 37, 13, 6, 2, 1, 1, 812, 162, 46, 14, 6, 2, 1, 1, 10957, 1120, 194, 50, 15, 6, 2, 1, 1, 260494, 12675, 1219, 204, 51, 15, 6, 2, 1, 1, 11713772, 276758, 13099, 1254, 208, 52, 15, 6, 2, 1, 1

Offset: 0

Author

Geoffrey Critzer, Mar 04 2020

Keywords

• nonn
• tabl

Comments

T(n,k) is the number of graphs on n nodes with incidence matrix of rank n-k, where the incidence matrix is defined as in Godsil-Royle reference below.

Examples

			Triangle T(n,k) begins:
    1;
    0,   1;
    0,   1,   1;
    1,   1,   1,  1;
    3,   4,   2,  1,  1;
   16,   9,   5,  2,  1, 1;
   96,  37,  13,  6,  2, 1, 1;
  812, 162,  46, 14,  6, 2, 1, 1;
  ...
		

References

• C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001, page 166.

Crossrefs

Cf. A157051 (column k=0 for n>0), A000088 (row sums), A157015, A005142.

Programs

Mathematica

Needs["Combinatorica`"];
Table[Table[Count[Prepend[Flatten[Table[g = {n, k};b = GraphData[g,"IncidenceMatrix"]; {n - MatrixRank[b]}, {k,2, NumberOfGraphs[n]}]], n], i], {i, 0, n}], {n, 0,7}] // Grid

Formula

G.f.: Product_{i>=1} (1/(1-x^i))^A157051(i)*(1/(1-y*x^i))^A005142(i).