cp's OEIS Frontend

A372153 Irregular triangular array read by rows. T(n,k) is the number of simple labeled graphs on [n] with circuit rank equal to k, n >= 1, 0 <= k <= binomial(n-1,2).

%I A372153 #26 Jun 09 2025 20:24:29
%S A372153 1,2,7,1,38,19,6,1,291,317,235,125,45,10,1,2932,5582,7120,6915,5215,
%T A372153 3057,1371,455,105,15,1,36961,108244,207130,306775,368046,364539,
%U A372153 300342,205940,116910,54362,20356,5985,1330,210,21,1,561948,2331108,6176387,12709760
%N A372153 Irregular triangular array read by rows.  T(n,k) is the number of simple labeled graphs on [n] with circuit rank equal to k, n >= 1, 0 <= k <= binomial(n-1,2).
%C A372153 The circuit rank r(G) of a simple graph G is the minimum number of edges that must be removed to break all of its cycles.  r(G) = m - n + c where m,n,c are the number of edges, vertices, and connected components respectively of G.
%C A372153 Equivalently, T(n,k) is the number of simple labeled graphs on [n] such that the incidence matrix has nullity equal to k where the incidence matrix is viewed as a matrix with entries in the field GF(2).
%D A372153 R. Diestel, Graph Theory, Springer, 2017, pp. 23-27.
%H A372153 Andrew Howroyd, <a href="/A372153/b372153.txt">Table of n, a(n) for n = 1..1160</a> (rows 1..20)
%H A372153 Wikipedia, <a href="http://en.wikipedia.org/wiki/Circuit_rank">Circuit rank</a>.
%H A372153 Wikipedia, <a href="http://en.wikipedia.org/wiki/Incidence_matrix">Incidence matrix</a>.
%F A372153 T(n,0) = A001858(n).
%F A372153 E.g.f. for T(n,1): f(x)*g(x) where f(x) is the e.g.f. for A001858 and g(x) is the e.g.f. for A057500.
%F A372153 E.g.f.: exp(y*log(Sum_{k>=0} (1+y)^binomial(k,2)*(x/y)^k/k!)). - _Andrew Howroyd_, Jun 09 2025
%e A372153 Triangle T(n,k) begins:
%e A372153      1;
%e A372153      2;
%e A372153      7,    1;
%e A372153     38,   19,    6,    1;
%e A372153    291,  317,  235,  125,   45,   10,   1;
%e A372153   2932, 5582, 7120, 6915, 5215, 3057, 1371, 455, 105, 15, 1;
%e A372153   ...
%t A372153 Needs["Combinatorica`"]; Map[Select[#, # > 0 &] &, Transpose[ Table[ Table[ Total[ Map[#[[1]] &,Select[Table[{n!/GraphData[{n, i}, "AutomorphismCount"], GraphData[{n, i}, "CyclomaticNumber"]}, {i, 1, NumberOfGraphs[n]}], #[[2]] == k &]]], {n, 1, 7}], {k, 0, 15}]]] // Grid
%o A372153 (PARI) T(n)={[Vecrev(p)| p<-Vec(-1+serlaplace(exp(y*log(sum(k=0, n, (1+y)^binomial(k,2)*x^k/k!/y^k, O(x*x^n))))))]}
%o A372153 { foreach(T(7), row, print(row)) } \\ _Andrew Howroyd_, Jun 09 2025
%Y A372153 Cf. A001858, A057500.
%K A372153 nonn,tabf
%O A372153 1,2
%A A372153 _Geoffrey Critzer_, Apr 20 2024
%E A372153 More terms from _Andrew Howroyd_, Jun 09 2025