|
|
A360716
|
|
Number of unordered pairs of self-avoiding paths whose sets of nodes are disjoint subsets of a set of n points on a circle; one-node paths are not allowed.
|
|
3
|
|
|
0, 0, 0, 3, 45, 435, 3465, 24794, 165942, 1061730, 6578550, 39796053, 236309931, 1382504669, 7989938775, 45704622660, 259155482652, 1458298435572, 8151155034300, 45290328792695, 250308998693145, 1376766613411959, 7539656755416885, 41126122248463038, 223513887538508850, 1210707873300202550, 6537847299012919890
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Although each path is self-avoiding, the different paths are allowed to intersect.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = n*(n-1)*2^(-5)*(5^(n-2) - 2*3^(n-2) + 1).
a(n) = 27*a(n-1) - 312*a(n-2) + 2016*a(n-3) - 7986*a(n-4) + 19998*a(n-5) - 31472*a(n-6) + 29880*a(n-7) - 15525*a(n-8) + 3375*a(n-9) for n > 9.
G.f.: x^4*(3 - 36*x + 156*x^2 - 288*x^3 + 197*x^4)/((1 - x)*(1 - 3*x)*(1 - 5*x))^3.
E.g.f.: exp(x)*(exp(2*x) - 1)^2*x^2/32.
(End)
|
|
EXAMPLE
|
a(5)=30+15=45: the first summand corresponds to the case when one of the paths has three nodes (5*4*3/2=30 variants; division by 2 is due to directional independence) and the second to the case when both paths have two nodes (5!/(2!2!2!)=15 variants).
|
|
CROSSREFS
|
If there is only one path, we get A261064. If all n points need to be used, we get A332426.
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|