login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A294198 Labeled trees on n nodes with at least one node of degree two. 1
0, 0, 3, 12, 120, 1200, 16380, 255696, 4726008, 99107280, 2346042600, 61706210280, 1788467429892, 56618211155688, 1944581982268380, 72019509651227040, 2861473883255362800, 121414006972684901664, 5479661140682410928592, 262122044885503316203320 (list; graph; refs; listen; history; text; internal format)
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: A133987 A194506 A280458 * A133553 A010571 A280248

Adjacent sequences:  A294195 A294196 A294197 * A294199 A294200 A294201

KEYWORD

nonn

AUTHOR

Marko Riedel, Feb 11 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 16 23:53 EDT 2021. Contains 347477 sequences. (Running on oeis4.)