Aria Dougherty - cp's OEIS frontend

1, 1, 3, 21, 255, 4815, 130095, 4763115, 226955925, 13646570175, 1010560060125, 90363456777825, 9599238270346725, 1194935000536101825, 172283712268118826375, 28481473075454845070625, 5351643310498951112521875, 1134140509146174954631081875, 269235074280949277622074328375

Offset: 1

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

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 i5) if (U, i) and (U', i') are adjacent nodes with U a subset of U', then i6) 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.
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

Seiichi Manyama, Table of n, a(n) for n = 1..261
M. Bona and A. Vince, The Number of Ways to Assemble a Graph, arXiv preprint arXiv:1204.3842 [math.CO], 2012.
Emily H. Dickey and Noah A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307.
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.

Cf. A006472, A047781, A317057, A317058, A317060.

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

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

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

a(n) = Sum_{j=1..floor(n/2)}(n!/((2^j)j!(n-2j)!))*a(n-j), a(1)=a(2)=1.

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

Original entry on oeis.org

1, 1, 3, 14, 85, 642, 5782, 60484, 720495, 9627210, 142583430, 2318126196, 41042117558, 786002475244, 16189215818220, 356847596226840, 8381418010559225, 208967274455769810, 5511890008010697306

Offset: 1

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

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

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.

Cf. A047781, A317057, A317058, A317059.

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

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

@cached_function
def TimeDepenEdgeCyc(n):
    if n==1:
        return 1
    elif n==2:
        return 1
    else:
        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))
print(','.join(str(TimeDepenEdgeCyc(i)) for i in range(1, 20)))

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.

A317057 a(n) is the number of time-dependent assembly trees satisfying the connected gluing rule for a cycle on n vertices.

Original entry on oeis.org

1, 1, 4, 23, 166, 1437, 14512, 167491, 2174746, 31374953, 497909380, 8619976719, 161667969646, 3265326093109, 70663046421208, 1631123626335707, 40004637435452866, 1038860856732399105, 28476428717448349996

Offset: 1

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

A time-dependent assembly tree for a connected graph G = (V, E) on n vertices is a rooted tree, each node of which is labeled with 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 connected gluing rule if each internal vertex v of G, the graph induced by the vertices in the labels is connected.
Essentially the same as A053525. - R. J. Mathar, Aug 20 2018

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.

Cf. A047781, A317058, A317059, A142979, A317060.

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

A317057 := proc(n)
    option remember;
    if n <=2 then
        1;
    else
        1+add(binomial(n,j)*procname(j), j=2..n-1) ;
    end if;
end proc:
seq(A317057(n),n=1..30) ; # R. J. Mathar, Aug 08 2018

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

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

@cached_function
def TimeDepenConCycle(n):
    if (n==1):
        return 1
    elif (n==2):
        return 1
    else:
        return sum([binomial(n, j)*TimeDepenConCycle(j) for j in range(2, n)])+1
print(','.join(str(TimeDepenConCycle(i)) for i in range(1, 20)))

a(n) = 1 + Sum_{j = 2..n-1} binomial(n, j)*a(j), a(1) = a(2) = 1.
E.g.f.: (x - x*e^x + e^x - 1)/(2 - e^x).
a(n+1) = Sum_{k = 1..n} Stirling_2(n, k) * A142979(k). - Peter Bala, Dec 09 2024

cp's OEIS Frontend

User: Aria Dougherty

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A317057 a(n) is the number of time-dependent assembly trees satisfying the connected gluing rule for a cycle on n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Sage

Formula