cp's OEIS Frontend

A317059 a(n) is the number of time-dependent assembly trees satisfying the edge gluing rule for a complete graph on n vertices.

%I A317059 #42 Mar 09 2025 12:26:37
%S A317059 1,1,3,21,255,4815,130095,4763115,226955925,13646570175,1010560060125,
%T A317059 90363456777825,9599238270346725,1194935000536101825,
%U A317059 172283712268118826375,28481473075454845070625,5351643310498951112521875,1134140509146174954631081875,269235074280949277622074328375
%N A317059 a(n) is the number of time-dependent assembly trees satisfying the edge gluing rule for a complete graph on n vertices.
%C A317059 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 A317059 1) each internal node has at least two children,
%C A317059 2) there are leaves labeled (v, 0) for each vertex v in V,
%C A317059 3) the label on the root is (V, m) for 1 <= m <= n-1,
%C A317059 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 A317059 5) if (U, i) and (U', i') are adjacent nodes with U a subset of U', then i<i',
%C A317059 6) for each 0 <= i <= m, there exists a node (U, i) with U a subset of V.
%C A317059 A time-dependent assembly tree is said to satisfy the edge gluing rule if each internal vertex v of G has exactly two children and if U_1 and U_2 are the labels of the children of internal vertex v, then there is an edge (v_1,v_2) in the edge set of G such that v_1 is in U_1 and v_2 is in U_2.
%C A317059 a(n) is also the number of labeled histories possible for n leaves if simultaneous bifurcations are allowed. a(n) is also the number of single-elimination sports tournament schedules possible for n teams if matches involve pairs of teams, arbitrarily many arenas are available, and labeled teams have been specified, but the bracket of matches has not been specified. - _Noah A Rosenberg_, Feb 20 2025
%H A317059 Seiichi Manyama, <a href="/A317059/b317059.txt">Table of n, a(n) for n = 1..261</a>
%H A317059 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 A317059 Emily H. Dickey and Noah A. Rosenberg, <a href="https://doi.org/10.1098/rstb.2023.0307">Labelled histories with multifurcation and simultaneity</a>, Phil. Trans. R. Soc. B 380 (2025), 20230307.
%H A317059 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 A317059 a(n) = Sum_{j=1..floor(n/2)}(n!/((2^j)j!(n-2j)!))*a(n-j), a(1)=a(2)=1.
%t A317059 Nest[Function[{a, n}, Append[a, Sum[(n!/((2^j) j! (n - 2 j)!)) a[[n - j]], {j, Floor[n/2]}]]][#, Length@ # + 1] &, {1, 1}, 17] (* _Michael De Vlieger_, Jul 26 2018 *)
%o A317059 (Sage)
%o A317059 @cached_function
%o A317059 def TimeDepenEdgeComp(n):
%o A317059     if n==1:
%o A317059         return 1
%o A317059     elif n==2:
%o A317059         return 1
%o A317059     else:
%o A317059         return sum((factorial(n)/((2^j)*factorial(j)*factorial(n-2*j)))*TimeDepenEdgeComp(n-j) for j in range(1, n//2+1))
%o A317059 print(",".join(str(TimeDepenEdgeComp(i)) for i in range(1, 20)))
%o A317059 (PARI) lista(nn) = my(v = vector(nn)); for (n=1, nn, if (n<=2, v[n] = 1, v[n] = sum(j=1, n\2, (n!/((2^j)*j!*(n-2*j)!))*v[n-j]))); v; \\ _Michel Marcus_, Aug 08 2018
%Y A317059 Cf. A006472, A047781, A317057, A317058, A317060.
%K A317059 easy,nonn
%O A317059 1,3
%A A317059 _Nick Mayers_, _Robert Short_, _Aria Dougherty_, Jul 20 2018