login
Triangle read by rows: T(n,k) is the number of graphs with n vertices and maximum vertex degree k, (0 <= k < n).
8

%I #58 Mar 10 2020 19:29:06

%S 1,1,1,1,1,2,1,2,4,4,1,2,8,12,11,1,3,15,43,60,34,1,3,25,121,360,378,

%T 156,1,4,41,378,2166,4869,3843,1044,1,4,65,1095,14306,68774,113622,

%U 64455,12346,1,5,100,3441,104829,1141597,3953162,4605833,1921532,274668

%N Triangle read by rows: T(n,k) is the number of graphs with n vertices and maximum vertex degree k, (0 <= k < n).

%C Terms may be computed without generating each graph by enumerating the number of graphs by degree sequence. A PARI program showing this technique for graphs with labeled vertices is given in A327366. Burnside's lemma can be used to extend this method to the unlabeled case. - _Andrew Howroyd_, Mar 10 2020

%H Andrew Howroyd, <a href="/A263293/b263293.txt">Table of n, a(n) for n = 1..210</a> (first 20 rows)

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000171">The degree of a graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumVertexDegree.html">Maximum Vertex Degree</a>

%F From _Geoffrey Critzer_, Sep 10 2016: (Start)

%F G.f. for column k=0: A(x)=1/(1-x).

%F G.f. for column k=1: B(x)=x^2/((1-x^2)(1-x)).

%F G.f. for column k=2: 1/((1-x)(1-x^2))*Product_{i>=3} 1/(1-x^i)^2 - B(x) - A(x).

%F (End)

%F T(n, 0) = 1.

%F T(n, n - 1) = A000088(n - 1).

%F T(n, k) = A294217(n, n - 1 - k). - _Andrew Howroyd_, Sep 03 2019

%e Triangle begins:

%e 1,

%e 1, 1,

%e 1, 1, 2,

%e 1, 2, 4, 4,

%e 1, 2, 8, 12, 11,

%e 1, 3, 15, 43, 60, 34,

%e 1, 3, 25, 121, 360, 378, 156,

%e 1, 4, 41, 378, 2166, 4869, 3843, 1044,

%e ...

%Y Row sums are A000088 (simple graphs on n nodes).

%Y Column k=2 is A324740.

%Y Diagonals include A000088(n-1), A324693, A324670.

%Y Cf. A294217 (triangle of n-node minimum vertex degree counts).

%Y Cf. A327366.

%K nonn,tabl,nice

%O 1,6

%A _Christian Stump_, Oct 13 2015

%E Rows n=9 and 10 added by _Eric W. Weisstein_, Oct 24 2017