A095338 Total number of leaves in the labeled graphs of order n.

0, 2, 12, 96, 1280, 30720, 1376256, 117440512, 19327352832, 6184752906240, 3870280929771520, 4755801206503243776, 11510768301994760208384, 55006124792465627449131008, 519934816499859715457632174080, 9735556609752801803494680617287680, 361550014853497117429835520396253724672

Offset

1,2

Comments

A leaf is defined as a vertex of degree (or valence) 1. - Michael Somos, Mar 13 2014

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..80

Eric Weisstein's World of Mathematics, Tree Leaf

Formula

Conjecture: a(n) = n*(n-1)*2^binomial(n-1,2). - Vladeta Jovovic, Jan 26 2006

a(n) = n*(n-1)*2^binomial(n-1,2) is correct, since counting the total number of leaves in the labeled graphs of order n is equivalent to counting all labeled rooted graphs of order n where the root is a leaf. - Bertran Steinsky, Mar 04 2014

a(n) = 2^(n-1) * A182166(n) for n>=2. - Joerg Arndt, Mar 12 2014

Example

G.f. = 2*x^2 + 12*x^3 + 96*x^4 + 1280*x^5 + 30720*x^6 + 1376256*x^7 + ...

Maple

A095338:=n->n*(n-1)*2^binomial(n-1, 2): seq(A095338(n), n=1..20); # Wesley Ivan Hurt, Oct 17 2014

Mathematica

Table[n (n - 1) 2^(Binomial[n-1, 2]), {n, 20}] (* Vincenzo Librandi, Mar 14 2014 *)

Prog

(PARI) a(n) = n*(n-1)*2^binomial(n-1, 2); \\ Joerg Arndt, Mar 12 2014
(Magma) [n*(n-1)*2^Binomial(n-1, 2): n in [1..20]]; // Vincenzo Librandi, Mar 14 2014

Crossrefs

Cf. A182166.

Sequence in context: A052611 A340938 A059864 * A308820 A322717 A219538

Adjacent sequences: A095335 A095336 A095337 * A095339 A095340 A095341

Keyword

nonn,easy

Author

Eric W. Weisstein, Jun 02 2004

Status

approved