A317058 -id:A317058 - 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

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

Original entry on oeis.org

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.

A317357 a(n) is the smallest composite k > n such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

Original entry on oeis.org

4, 341, 473, 6, 10, 133, 497, 14, 12, 15, 15, 16, 18, 143, 35, 20, 32, 51, 57, 38, 28, 77, 253, 36, 30, 65, 39, 36, 58, 115, 155, 62, 36, 187, 119, 40, 74, 57, 247, 52, 80, 287, 2051, 86, 55, 69, 69, 94, 54, 175, 85, 65, 65, 159, 69, 70, 64, 551, 1711, 72

Offset: 1

Thomas Ordowski, Jul 26 2018

nonn

According to the Agoh-Giuga conjecture, a(n) > n+1.
a(n) > A151800(n) for all n < 33.
a(n) <= A271221(n) for n > 1.

Chai Wah Wu, Table of n, a(n) for n = 1..9661
Wikipedia, Agoh-Giuga conjecture

Cf. A151800, A271221, A317058, A317358.

a[n_] := Block[{k = n+1}, While[PrimeQ[k] || Mod[Sum[PowerMod[j, k-1, k], {j, n}], k] != n, k++]; k]; Array[a, 60] (* Giovanni Resta, Jul 26 2018 *)

a(n) = forcomposite(k=n+1,, if (sum(j=1,n, Mod(j,k)^(k-1)) == n, return (k));); \\ Michel Marcus, Jul 26 2018

from sympy import isprime
def g(n,p,q): # compute (-n + sum_{k=1,n} k^p)  mod q
    c = (-n) % q
    for k in range(1,n+1):
        c = (c+pow(k,p,q)) % q
    return c
def A317357(n):
    k = n+1
    while isprime(k) or g(n,k-1,k):
        k += 1
    return k # Chai Wah Wu, Jul 31 2018

More terms from Giovanni Resta, Jul 26 2018

A317358 a(n) is the smallest number k > 1 such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

Original entry on oeis.org

2, 3, 5, 2, 2, 7, 11, 2, 2, 3, 3, 2, 2, 17, 17, 2, 2, 3, 3, 2, 2, 23, 29, 2, 2, 5, 3, 2, 2, 31, 37, 2, 2, 37, 35, 2, 2, 3, 41, 2, 2, 43, 47, 2, 2, 3, 3, 2, 2, 5, 5, 2, 2, 3, 3, 2, 2, 59, 61, 2, 2, 67, 3, 2, 2, 55, 71, 2, 2, 35, 35, 2, 2, 3, 5, 2, 2, 5, 5, 2, 2

Offset: 1

Thomas Ordowski, Jul 26 2018

nonn

a(n) = 2 if and only if n == {0, 1} (mod 4).
a(n) <= A151800(n).
A133906(n) <= a(n) <= A133907(n).
The sequence is unbounded.
Numbers n such that a(n-1) = n are 2, 3, 7, 23, 31, 43, 59, 139, 283, ...
By the Agoh-Giuga conjecture, if a(n-1) = n, then n is a prime.
It seems that if a(n) > n, then a(n) is a prime (the next prime after n).
If a(n) = n, then n is in A121707. These numbers are 35, 143, 187, 215, ...
Conjecture: all composite terms of the sequence are A121707.

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (n = 1..1000 from Seiichi Manyama)
Wikipedia, Agoh-Giuga conjecture

Cf. A133906, A133907, A151800, A121707, A317058, A317357.

a[n_] := Block[{k=2}, While[Mod[Sum[PowerMod[j, k-1, k], {j, n}], k] != Mod[n, k], k++]; k]; Array[a, 81] (* Giovanni Resta, Jul 29 2018 *)

a(n) = for(k=2,oo, if (sum(j=1,n, Mod(j,k)^(k-1)) == n, return (k));); \\ Michel Marcus, Jul 26 2018

def g(n,p,q): # compute (-n + sum_{k=1,n} k^p)  mod q
    c = (-n) % q
    for k in range(1,n+1):
        c = (c+pow(k,p,q)) % q
    return c
def A317358(n):
    k = 2
    while g(n,k-1,k):
        k += 1
    return k # Chai Wah Wu, Jul 30 2018

More terms from Michel Marcus, Jul 26 2018

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.

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

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

A317357 a(n) is the smallest composite k > n such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A317358 a(n) is the smallest number k > 1 such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

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