A317059 -id:A317059 - cp's OEIS frontend

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

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

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.

A381486 Number of labeled histories for rooted ternary trees with 2n+1 leaves if simultaneous trifurcations are allowed.

Original entry on oeis.org

1, 1, 10, 420, 43960, 9347800, 3513910400, 2131249120000, 1952028782704000, 2568150610833808000, 4666919676058159520000, 11351087418588355518080000, 36008099327884173922432000000, 145785514242304854141480256000000, 739598808823839440680777500928000000, 4627885522642342503645368137231360000000

Offset: 0

Noah A Rosenberg, Feb 25 2025

nonn

a(n) is also the number of single-elimination sports tournament schedules possible for 2n+1 teams if matches involve three teams, arbitrarily many arenas are available, and labeled teams have been specified, but the bracket of matches has not been specified.

			Consider 7 named players in a sport in which players compete 3 at a time (e.g. the television gameshow "Jeopardy!"). The number of ways a single-elimination tournament can be arranged, if simultaneous matches can take place, is a(3)=420. Three of these 420 are: (1) A, B, and C play; the winner plays against D and E; the winner plays against F and G. (2) D, E, and F play; the winner plays against A and B; the winner plays against C and G. (3) A, B, and C play simultaneous with D, E, and F; the winners of these matches play against G.

Emily H. Dickey and Noah A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307.

Cf. A317059 for binary rather than ternary trees, A339411 if simultaneity is disallowed.

a:= proc(n) option remember; `if`(n=0, 1, add((2*n+1)!/
      (i!*6^i*(2*n+1-3*i)!)*a(n-i), i=1..(2*n+1)/3))
    end:
seq(a(n), n=0..15);  # Alois P. Heinz, Feb 25 2025

a(n) = Y(2n+1), where Y(n) = Sum_{i=1..floor(n/3)} (n!/(i!*6^i*(n-3*i)!))*Y(n-2*i), with Y(1)=1.

A381523 Number of labeled histories for rooted 4-furcating trees with 3n+1 leaves if simultaneous 4-furcations are allowed.

Original entry on oeis.org

1, 1, 35, 8925, 8033025, 19010866875, 97622651251125, 958647115051250625, 16437666902498106890625, 459581350409578975249546875, 19861812620603175030206132109375, 1271123241419341933758758697996796875, 116303414318027015186301064741488195703125, 14773177703549629967524262172307456486365234375

Offset: 0

Noah A Rosenberg, Feb 26 2025

nonn

Emily H. Dickey and Noah A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307. (see Table 4)

Cf. A317059 for binary trees and A381486 for ternary trees.

a:= proc(n) option remember; `if`(n=0, 1, add((3*n+1)!/
      (i!*24^i*(3*n+1-4*i)!)*a(n-i), i=1..(3*n+1)/4))
    end:
seq(a(n), n=0..15);  # Alois P. Heinz, Feb 26 2025

a(n) = Y(3n+1), where Y(n) = Sum_{i=1..floor(n/4)} (n!/(i!*24^i*(n-4*i)!))*Y(n-3*i), with Y(1)=1.

A381533 Number of labeled histories for rooted 5-furcating trees with 4n+1 leaves if simultaneous 5-furcations are allowed.

Original entry on oeis.org

1, 1, 126, 198198, 1552358808, 41269930621920, 2917021792126858416, 466738566750935966462976, 150642168106131265276308435840, 89930728809765858827345682838905216, 92814015425659158860323886440105229380608, 156870775305420194841270876582071899442900414976, 415352074564676036635314305973768435826840253066044416

Offset: 0

Noah A Rosenberg, Feb 26 2025

nonn

Emily H. Dickey and Noah A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307 (see Table 4).

Cf. A317059, A381486, A381523.

a:= proc(n) option remember; `if`(n=0, 1, add((4*n+1)!/
      (i!*120^i*(4*n+1-5*i)!)*a(n-i), i=1..(4*n+1)/5))
    end:
seq(a(n), n=0..12);  # Alois P. Heinz, Feb 26 2025

a(n) = Y(4n+1), where Y(n) = Sum_{i=1..floor(n/5)} (n!/(i!*120^i*(n-5*i)!)) * Y(n-4*i), with Y(1)=1.

Showing 1-5 of 5 results.

cp's OEIS Frontend

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

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

A381486 Number of labeled histories for rooted ternary trees with 2n+1 leaves if simultaneous trifurcations are allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A381523 Number of labeled histories for rooted 4-furcating trees with 3n+1 leaves if simultaneous 4-furcations are allowed.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A381533 Number of labeled histories for rooted 5-furcating trees with 4n+1 leaves if simultaneous 5-furcations are allowed.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula