A095338 - OEIS

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

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

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.