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

Author

Chai Wah Wu, Aug 01 2014

Keywords

• nonn
• tabf

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).

Examples

			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
...
		

Links

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

Crossrefs

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

Cf. A000217, A050534, A053526, A152947.