

A317060


a(n) is the number of timedependent assembly trees satisfying the edge gluing rule for a cycle on n vertices.


2



1, 1, 3, 14, 85, 642, 5782, 60484, 720495, 9627210, 142583430, 2318126196, 41042117558, 786002475244, 16189215818220, 356847596226840, 8381418010559225, 208967274455769810, 5511890008010697306
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

A timedependent 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:
1) each internal node has at least two children,
2) there are leaves labeled (v, 0) for each vertex v in V,
3) the label on the root is (V, m) for 1 <= m <= n1,
4) for each node (U, i) with i < m, U is the union of the {u} for the children (u, 0) of (U, i),
5) if (U, i) and (U', i') are adjacent nodes with U a subset of U', then i<i',
6) for each 0 <= i <= m, there exists a node (U, i) with U a subset of V.
A timedependent 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.


LINKS

Table of n, a(n) for n=1..19.
M. Bona and A. Vince, The Number of Ways to Assemble a Graph, arXiv preprint arXiv:1204.3842 [math.CO], 2012.
A. Dougherty, N. Mayers, and R. Short, How to Build a Graph in n Days: Some Variants on Graph Assembly, arXiv preprint arXiv:1807.08079 [math.CO], 2018.


FORMULA

a(n) = Sum_{j=1..floor(n/2)}(binomial(nj, n2j)+binomial(nj1,n2j))*a(nj), a(1)=a(2)=1.


MATHEMATICA

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 *)


PROG

(Sage)
@cached_function
def TimeDepenEdgeCyc(n):
if n==1:
return 1
elif n==2:
return 1
else:
return sum((binomial(nj, n2*j)+binomial(nj1, n2*j))*TimeDepenEdgeCyc(nj) for j in range(1, (n//2)+1))
print(', '.join(str(TimeDepenEdgeCyc(i)) for i in range(1, 20)))
(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(nj, n2*j)+binomial(nj1, n2*j))*v[nj]))); v; \\ Michel Marcus, Aug 08 2018


CROSSREFS

Cf. A047781, A317057, A317058, A317059.
Sequence in context: A005189 A331608 A331615 * A308940 A276313 A074520
Adjacent sequences: A317057 A317058 A317059 * A317061 A317062 A317063


KEYWORD

easy,nonn


AUTHOR

Nick Mayers, Robert Short, Aria Dougherty, Jul 20 2018


STATUS

approved



