|
%I #45 Mar 08 2020 06:54:49
%S 1,1,4,23,166,1437,14512,167491,2174746,31374953,497909380,8619976719,
%T 161667969646,3265326093109,70663046421208,1631123626335707,
%U 40004637435452866,1038860856732399105,28476428717448349996
%N a(n) is the number of time-dependent assembly trees satisfying the connected gluing rule for a cycle on n vertices.
%C A time-dependent assembly tree for a connected graph G=(V, E) on n vertices is a rooted tree, each node of which is label a subset U of V and a nonnegative integer i such that:
%C 1) each internal node has at least two children,
%C 2) there are leaves labeled (v, 0) for each vertex v in V,
%C 3) the label on the root is (V, m) for 1 <= m <= n-1,
%C 4) for each node (U, i) with i < m, U is the union of the {u} for the children (u, 0) of (U, i),
%C 5) if (U, i) and (U', i') are adjacent nodes with U a subset of U', then i < i',
%C 6) for each 0 <= i <= m, there exists a node (U, i) with U a subset of V.
%C A time-dependent assembly tree is said to satisfy the connected gluing rule if each internal vertex v of G, the graph induced by the vertices in the labels is connected.
%C Essentially the same as A053525. - _R. J. Mathar_, Aug 20 2018
%H M. Bona and A. Vince, <a href="https://arxiv.org/abs/1204.3842">The Number of Ways to Assemble a Graph</a>, arXiv preprint arXiv:1204.3842 [math.CO], 2012.
%H A. Dougherty, N. Mayers, and R. Short, <a href="https://arxiv.org/abs/1807.08079">How to Build a Graph in n Days: Some Variants on Graph Assembly</a>, arXiv preprint arXiv:1807.08079 [math.CO], 2018.
%F a(n) = 1 + Sum_{j=2..n-1} binomial(n, j)*a(j), a(1)=a(2)=1.
%F E.g.f.: (x - x*e^x + e^x - 1)/(2 - e^x).
%p A317057 := proc(n)
%p option remember;
%p if n <=2 then
%p 1;
%p else
%p 1+add(binomial(n,j)*procname(j), j=2..n-1) ;
%p end if;
%p end proc:
%p seq(A317057(n),n=1..30) ; # _R. J. Mathar_, Aug 08 2018
%t Nest[Function[{a, n}, Append[a, 1 + Sum[Binomial[n, j] a[[j]], {j, 2, n - 1}]]][#, Length@ # + 1] &, {1, 1}, 17] (* _Michael De Vlieger_, Jul 26 2018 *)
%o (Sage)
%o @cached_function
%o def TimeDepenConCycle(n):
%o if (n==1):
%o return 1
%o elif (n==2):
%o return 1
%o else:
%o return sum([binomial(n, j)*TimeDepenConCycle(j) for j in range(2, n)])+1
%o print(','.join(str(TimeDepenConCycle(i)) for i in range(1, 20)))
%o (GAP) a:=[1,1];; for n in [3..20] do a[n]:=1+Sum([2..n-1],j->Binomial(n,j)*a[j]); od; a; # _Muniru A Asiru_, Jul 25 2018
%o (PARI) lista(nn) = my(v = vector(nn)); for (n=1, nn, if (n<=2, v[n] = 1, v[n] = 1 + sum(j=2, n-1, binomial(n, j)*v[j]))); v; \\ _Michel Marcus_, Aug 08 2018
%Y Cf. A047781, A317058, A317059, A317060.
%K easy,nonn
%O 1,3
%A _Nick Mayers_, _Robert Short_, _Aria Dougherty_, Jul 20 2018
|
