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

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, 156, 1, 4, 41, 378, 2166, 4869, 3843, 1044, 1, 4, 65, 1095, 14306, 68774, 113622, 64455, 12346, 1, 5, 100, 3441, 104829, 1141597, 3953162, 4605833, 1921532, 274668

Offset

1,6

Comments

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

Links

Andrew Howroyd, Table of n, a(n) for n = 1..210 (first 20 rows)

FindStat - Combinatorial Statistic Finder, The degree of a graph

Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Formula

From Geoffrey Critzer, Sep 10 2016: (Start)

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

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

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

(End)

T(n, 0) = 1.

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

T(n, k) = A294217(n, n - 1 - k). - Andrew Howroyd, Sep 03 2019

Example

Triangle begins:
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,  156,
1,    4,   41,  378, 2166, 4869, 3843, 1044,
...

Crossrefs

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

Column k=2 is A324740.

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

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

Cf. A327366.

Sequence in context: A360594 A295313 A105022 * A230535 A349741 A257651

Adjacent sequences: A263290 A263291 A263292 * A263294 A263295 A263296

Keyword

nonn,tabl,nice

Author

Christian Stump, Oct 13 2015

Extensions

Rows n=9 and 10 added by Eric W. Weisstein, Oct 24 2017

Status

approved