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
Andrew Howroyd, Table of n, a(n) for n = 1..200
R. Balakrishnan, N. Sridharan and K. Viswanathan Iyer, The Wiener index of odd graphs, J. Ind. Inst. Sci., vol. 86, no. 5, 2006.
R. Balakrishnan, N. Sridharan and K. Viswanathan Iyer,, The Wiener index of odd graphs, J. Ind. Inst. Sci., vol. 86, no. 5, 2006. [Cached copy]
Eric Weisstein's World of Mathematics, Odd Graph
Eric Weisstein's World of Mathematics, Wiener Index
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
a(n) = A301566(n)*binomial(2*n-1,n-1)/2. - Eric W. Weisstein, Mar 26 2018
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:
# R. J. Mathar, Sep 15 2010
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);
# Emeric Deutsch, Aug 20 2013
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
K.V.Iyer, Mar 27 2008
EXTENSIONS
Extended by R. J. Mathar, Sep 15 2010
Terms a(18) and beyond from Andrew Howroyd, Mar 26 2018
STATUS
approved