A317060 - OEIS

%I #27 Mar 13 2020 16:59:28

%S 1,1,3,14,85,642,5782,60484,720495,9627210,142583430,2318126196,

%T 41042117558,786002475244,16189215818220,356847596226840,

%U 8381418010559225,208967274455769810,5511890008010697306

%N a(n) is the number of time-dependent assembly trees satisfying the edge 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 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.

%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) = Sum_{j=1..floor(n/2)}(binomial(n-j, n-2j)+binomial(n-j-1,n-2j))*a(n-j), a(1)=a(2)=1.

%t Nest[Function[{a, n}, Append[a, Sum[(Binomial[n - j, n - 2 j] + Binomial[n - j - 1, n - 2 j]) a[[n - j]], {j, Floor[n/2]}]]][#, Length@ # + 1] &, {1, 1}, 17] (* _Michael De Vlieger_, Jul 26 2018 *)

%o (Sage)

%o @cached_function

%o def TimeDepenEdgeCyc(n):

%o     if n==1:

%o         return 1

%o     elif n==2:

%o         return 1

%o     else:

%o         return sum((binomial(n-j,n-2*j)+binomial(n-j-1, n-2*j))*TimeDepenEdgeCyc(n-j) for j in range(1, (n//2)+1))

%o print(','.join(str(TimeDepenEdgeCyc(i)) for i in range(1, 20)))

%o (PARI) lista(nn) = my(v = vector(nn)); for (n=1, nn, if (n<=2, v[n] = 1, v[n] = sum(j=1, n\2, (binomial(n-j, n-2*j)+binomial(n-j-1,n-2*j))*v[n-j]))); v; \\ _Michel Marcus_, Aug 08 2018

%Y Cf. A047781, A317057, A317058, A317059.

%K easy,nonn

%O 1,3

%A _Nick Mayers_, _Robert Short_, _Aria Dougherty_, Jul 20 2018