OFFSET
1,3
COMMENTS
The permutation star graph of order n is a vertex transitive graph with n! vertices and degree n-1. The graph can be constructed as the Cayley graph of the permutations of 1..n with the n-1 generators (1 2), (1 3)..(1 n) where (1 k) is the transposition of 1 and k. The number of nodes at distance k from a specified node is given by A007799(n,k). - Andrew Howroyd, Sep 17 2017
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Permutation Star Graph
Eric Weisstein's World of Mathematics, Wiener Index
FORMULA
a(n) = n!/2 * Sum_{k=1..floor(3*(n-1)/2)} k*A007799(n, k). - Andrew Howroyd, Sep 17 2017
MATHEMATICA
a[n_, 0] = 1;
a[n_, 1] = n - 1;
a[n_, 2] = (n - 1) (n - 2);
a[n_, k_ /; k >= 2] := a[n, k] = (n - 1) a[n - 1, k - 1] + Sum[j a[j, k - 3], {j, 1, n - 2}];
Table[n!/2 Sum[k a[n, k], {k, Floor[3 (n - 1)/2]}], {n, 10}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Sep 13 2017
EXTENSIONS
Terms a(8) and beyond from Andrew Howroyd, Sep 17 2017
STATUS
approved