

A309490


Total number of adjacent node merge operations to turn a circular list of size n to a node.


0



0, 1, 6, 28, 145, 876, 6139, 49120, 442089, 4420900, 48629911, 583558944, 7586266285, 106207728004, 1593115920075, 25489854721216, 433327530260689, 7799895544692420, 148198015349155999, 2963960306983120000, 62243166446645520021, 1369349661826201440484, 31495042222002633131155, 755881013328063195147744
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


LINKS

Table of n, a(n) for n=1..24.


FORMULA

a(n) = n + n * a(n  1) for n >= 3, a(1) = 0, a(2) = 1.
For n > 1, a(n) = exp(1)*n*Gamma(n, 1)  3*n!/2.  Vaclav Kotesovec, Aug 05 2019


EXAMPLE

For n=1, a(1)=0  no ops since it is already a node.
For n=2, a(2)=1  there is only 1 possible contraction of the 2 nodes.
For n=3, a(3)=6. Consider an undirected circular list of 3 nodes A,B,C and 3 edges (A,B), (B,C), (C,A). Initially, any of the 3 edges can be contracted to get a 2node list  here are 3 operations. Then, each 2node list requires 1 more contraction to become the trivial graph, giving 3 extra operations summing to a(3)=3+3=6.
In general, firstly one of the n edges gets contracted to get a list of size n  1, secondly the list of size n  1 is contracted. So, each choice of the initial node has 1 + a(n  1) operations; the n choices sum up to a(n) = n + n * a(n  1).


MATHEMATICA

Flatten[{0, Table[E*n*Gamma[n, 1]  3/2*Gamma[n+1], {n, 2, 25}]}] (* Vaclav Kotesovec, Aug 05 2019 *)


PROG

(C) int CircularListContractOps(int n) { if (n <= 1) return 0; if (n == 2) return 1; return n*(CircularListContractOps(n  1) + 1); }
(PARI) a(n) = if(n<=2, n1, n + n * a(n  1)); \\ Joerg Arndt, Aug 04 2019


CROSSREFS

Sequence in context: A283094 A110047 A163029 * A045722 A047129 A173081
Adjacent sequences: A309487 A309488 A309489 * A309491 A309492 A309493


KEYWORD

nonn


AUTHOR

Viktar Karatchenia, Aug 04 2019


STATUS

approved



