|
|
A136328
|
|
a(n) = Wiener index of the odd graph O_n.
|
|
5
|
|
|
0, 3, 75, 1435, 25515, 436821, 7339332, 121782375, 2005392675, 32835436777, 535550923908, 8707954925033, 141270179732500, 2287544190032700, 36988236910737360, 597341791692978975, 9637351741503033075, 155353556752487795625, 2502545930175392062500
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The odd graph O_n (n>=2) is a graph whose vertices represent the (n-1)-subsets of {1,2,...,2n-1} and two vertices are connected if and only if they correspond to disjoint subsets. It is a distance regular graph. [Emeric Deutsch, Aug 20 2013]
|
|
REFERENCES
|
Kailasam Viswanathan Iyer, Some computational and graph theoretical aspects of Wiener index, Ph.D. Dissertation, Dept. of Comp. Sci. & Engg., National Institute of Technology, Trichy, India, 2007.
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Odd Graph
|
|
FORMULA
|
a(n) = binomial(2*n - 1, n - 1)/2*(sum(((2*j + 1)*n)/(j + 1)*binomial(n - 1, j)^2, {j, 0, floor(n/2) - 1}) + sum((2*(n - 1 - j)*n)/(j + 1)*binomial(n - 1, j)^2, {j, floor(n/2), n - 2})). - Eric W. Weisstein, Sep 08 2017
A formula is "hidden" in the 2nd Maple program. B(n) and C(n) are the intersection arrays of O_n, H(n) is the Hosoya-Wiener polynomial of O_n, and Wi(n) is the Wiener index of O_n. - Emeric Deutsch, Aug 20 2013
|
|
EXAMPLE
|
a(2)=3 is the Wiener index of O_2 which is C_3.
a(3)=75 is the Wiener index of O_3 which is the Petersen graph.
|
|
MAPLE
|
A136328d := proc(k) add( (2*j+1)*binomial(k-1, j)^2/(1+j), j=0..(k/2-1) ); %+2*add( (k-1-j)*binomial(k-1, j)^2/(1+j), j=floor(k/2)..(k-2) ); k*% ; end proc:
A136328 := proc(n) binomial(2*n-1, n-1)*A136328d(n)/2 ; end proc: seq(A136328(n), n=1..20) ;
B := proc (n) options operator, arrow: [seq(n-floor((1/2)*m), m = 1 .. n-1)] end proc: C := proc (n) options operator, arrow: [seq(ceil((1/2)*m), m = 1 .. n-1)] end proc: H := proc (n) options operator, arrow: (1/2)*binomial(2*n-1, n-1)*(sum((product(B(n)[r]/C(n)[r], r = 1 .. j))*t^j, j = 1 .. n-1)) end proc: Wi := proc (n) options operator, arrow: subs(t = 1, diff(H(n), t)) end proc: seq(Wi(n), n = 2 .. 20);
|
|
MATHEMATICA
|
Table[Binomial[2 n - 1, n - 1]/2 (Sum[((2 j + 1) n)/(j + 1) Binomial[n - 1, j]^2, {j, 0, Floor[n/2] - 1}] + Sum[(2 (n - 1 - j) n)/(j + 1) Binomial[n - 1, j]^2, {j, Floor[n/2], n - 2}]), {n, 20}] (* Eric W. Weisstein, Sep 08 2017 *)
Table[Sum[k Binomial[n, Ceiling[k/2]] Binomial[n - 1, Floor[k/2]] Binomial[2 n - 1, n - 1]/2, {k, n - 1}], {n, 20}] (* Eric W. Weisstein, Mar 27 2018 *)
|
|
PROG
|
(PARI) a(n) = sum(k=1, n-1, k*binomial(n, ceil(k/2))*binomial(n-1, k\2))*binomial(2*n-1, n-1)/2 \\ Andrew Howroyd, Mar 26 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|