A294198 Labeled trees on n nodes with at least one node of degree two.

0, 0, 3, 12, 120, 1200, 16380, 255696, 4726008, 99107280, 2346042600, 61706210280, 1788467429892, 56618211155688, 1944581982268380, 72019509651227040, 2861473883255362800, 121414006972684901664, 5479661140682410928592, 262122044885503316203320

Offset

1,3

Links

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

Marko Riedel, Maple code for sequence including total enumeration and closed form.

Marko Riedel et al., How many trees have a vertex of degree two

Formula

a(n) = (n-2)!*Sum_{q=1..n-2} C(n,q)*(-1)^(q+1)*(n-q)^(n-2-q)/(n-2-q)! where n >= 2.

Example

When n=4 there are two types of trees: paths (24!/2  trees) or a star (4 trees) for a total of 4^(4-2) trees. Of these only the paths contain a vertex of degree 2 (2 in fact). When n=5 there are three types of trees: paths (5!/2 trees), a star (5 trees) or a fork (C(5,1) x C(4, 2) x 2) for a total of 5^(5-2) trees. Of these only the paths and the fork contain a vertex of degree 2.

Mathematica

a[1] = 0; a[n_] := (n-2)! Sum[Binomial[n, q] (-1)^(q+1) (n-q)^(n-2-q) / (n-2-q)!, {q, 1, n-2}]; Array[a, 20] (* Jean-François Alcover, Feb 15 2018 *)

Crossrefs

Cf. A007106, A274699.

Sequence in context: A359658 A194506 A280458 * A133553 A010571 A280248

Adjacent sequences: A294195 A294196 A294197 * A294199 A294200 A294201

Keyword

nonn

Author

Marko Riedel, Feb 11 2018

Status

approved