A245796 T(n,k) is the number of labeled graphs of n vertices and k edges that have endpoints, where an endpoint is a vertex with degree 1.

0, 1, 3, 3, 6, 15, 16, 12, 10, 45, 110, 195, 210, 120, 20, 15, 105, 435, 1320, 2841, 4410, 4845, 3360, 1350, 300, 30, 21, 210, 1295, 5880, 19887, 51954, 106785, 171360, 208565, 186375, 120855, 56805, 19110, 4410, 630, 42

Offset

1,3

Comments

The length of the rows are 1,1,2,4,7,11,16,22,...: (1+(n-1)*(n-2)/2) = A152947(n).

T(n,k) = 0 if k > (n-1)*(n-2)/2 + 1.

Let j = (n-1)*(n-2)/2. For i >=0, n >= 4+i, T(n,j-i+1) = n*(n-1)*binomial(j,i).

For k <= 3, T(n,k) is equal to the number of labeled bipartite graphs with n vertices and k edges. In particular, T(n,1) = A000217(n-1), T(n,2) = A050534(n) and T(n,3) = A053526(n).

Links

Table of n, a(n) for n=1..42.

Chai Wah Wu, Graphs whose normalized Laplacian matrices are separable as density matrices in quantum mechanics, arXiv:1407.5663 [quant-ph], 2014.

Example

Triangle starts:
..0
..1
..3......3
..6.....15.....16.....12
.10.....45....110....195....210....120.....20
.15....105....435...1320...2841...4410...4845...3360...1350....300.....30
...

Crossrefs

Sum of n-th row is A245797(n).

Cf. A000217, A050534, A053526, A152947.

Sequence in context: A143418 A336452 A092370 * A345908 A006807 A298180

Adjacent sequences: A245793 A245794 A245795 * A245797 A245798 A245799

Keyword

nonn,tabf

Author

Chai Wah Wu, Aug 01 2014

Status

approved