login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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 * A045722 A047129 A173081

Adjacent sequences:  A309487 A309488 A309489 * A309491 A309492 A309493

KEYWORD

nonn

AUTHOR

Viktar Karatchenia, Aug 04 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 11 15:12 EDT 2020. Contains 336428 sequences. (Running on oeis4.)