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

0, 1, 6, 28, 145, 876, 6139, 49120, 442089, 4420900, 48629911, 583558944, 7586266285, 106207728004, 1593115920075, 25489854721216, 433327530260689, 7799895544692420, 148198015349155999, 2963960306983120000, 62243166446645520021, 1369349661826201440484, 31495042222002633131155, 755881013328063195147744

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 2-node list - here are 3 operations. Then, each 2-node 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, n-1, n + n * a(n - 1)); \\ Joerg Arndt, Aug 04 2019

Crossrefs

Sequence in context: A283094 A110047 A163029 * A344755 A045722 A047129

Adjacent sequences: A309487 A309488 A309489 * A309491 A309492 A309493

Keyword

nonn

Author

Viktar Karatchenia, Aug 04 2019

Status

approved