login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A317059 a(n) is the number of time-dependent assembly trees satisfying the edge gluing rule for a complete graph on n vertices. 2
1, 1, 3, 21, 255, 4815, 130095, 4763115, 226955925, 13646570175, 1010560060125, 90363456777825, 9599238270346725, 1194935000536101825, 172283712268118826375, 28481473075454845070625, 5351643310498951112521875, 1134140509146174954631081875, 269235074280949277622074328375 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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:

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 <= n-1,

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 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.

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)}(n!/((2^j)j!(n-2j)!))*a(n-j), a(1)=a(2)=1.

MATHEMATICA

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

PROG

(Sage)

@cached_function

def TimeDepenEdgeComp(n):

    if n==1:

        return 1

    elif n==2:

        return 1

    else:

        return sum((factorial(n)/((2^j)*factorial(j)*factorial(n-2*j)))*TimeDepenEdgeComp(n-j) for j in range(1, n//2+1))

print(", ".join(str(TimeDepenEdgeComp(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, (n!/((2^j)*j!*(n-2*j)!))*v[n-j]))); v; \\ Michel Marcus, Aug 08 2018

CROSSREFS

Cf. A047781, A317057, A317058, A317060.

Sequence in context: A209917 A179504 A197716 * A262939 A232470 A251573

Adjacent sequences:  A317056 A317057 A317058 * A317060 A317061 A317062

KEYWORD

easy,nonn

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 10 00:05 EDT 2020. Contains 335570 sequences. (Running on oeis4.)