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,11

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.

References

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

Links

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

Formula

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

Example

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;
  ...

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

Crossrefs

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

Sequence in context: A236679 A364871 A096392 * A105825 A238570 A145425

Adjacent sequences: A332961 A332962 A332963 * A332965 A332966 A332967

Keyword

nonn,tabl

Author

Geoffrey Critzer, Mar 04 2020

Status

approved