A245796 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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

...