|
%I #12 Aug 06 2019 02:44:59
%S 0,1,6,28,145,876,6139,49120,442089,4420900,48629911,583558944,
%T 7586266285,106207728004,1593115920075,25489854721216,433327530260689,
%U 7799895544692420,148198015349155999,2963960306983120000,62243166446645520021,1369349661826201440484,31495042222002633131155,755881013328063195147744
%N Total number of adjacent node merge operations to turn a circular list of size n to a node.
%F a(n) = n + n * a(n - 1) for n >= 3, a(1) = 0, a(2) = 1.
%F For n > 1, a(n) = exp(1)*n*Gamma(n, 1) - 3*n!/2. - _Vaclav Kotesovec_, Aug 05 2019
%e For n=1, a(1)=0 - no ops since it is already a node.
%e For n=2, a(2)=1 - there is only 1 possible contraction of the 2 nodes.
%e 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.
%e 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).
%t Flatten[{0, Table[E*n*Gamma[n, 1] - 3/2*Gamma[n+1], {n, 2, 25}]}] (* _Vaclav Kotesovec_, Aug 05 2019 *)
%o (C) int CircularListContractOps(int n) { if (n <= 1) return 0; if (n == 2) return 1; return n*(CircularListContractOps(n - 1) + 1); }
%o (PARI) a(n) = if(n<=2,n-1,n + n * a(n - 1)); \\ _Joerg Arndt_, Aug 04 2019
%K nonn
%O 1,3
%A _Viktar Karatchenia_, Aug 04 2019
|
