A317057 -id:A317057 - cp's OEIS frontend

A142979 a(1) = 1, a(2) = 3, a(n+2) = 3a(n+1) + (n+1)^2a(n).

1, 3, 13, 66, 406, 2868, 23220, 210192, 2116656, 23375520, 281792160, 3673814400, 51599514240, 775673176320, 12440524320000, 211848037632000, 3820318338816000, 72685037892096000, 1455838255452672000

Offset: 1

Peter Bala, Jul 17 2008

This is the case m = 1 of the more general recurrence a(1) = 1, a(2) = 2*m + 1, a(n+2) = (2*m + 1)*a(n+1) + (n + 1)^2*a(n) (we suppress the dependence of a(n) on m), which arises when accelerating the convergence of Mercator's series for the constant log(2). For other cases see A024167 (m = 0), A142980 (m = 2), A142981 (m = 3) and A142982 (m = 4).
The solution to the general recurrence may be expressed as a sum: a(n) = n!*p_m(n)*Sum_{k = 1..n} (-1)^(k+1)/(k*p_m(k-1)*p_m(k)), where p_m(x) = Sum_{k = 0..m} 2^k*C(m,k)*C(x,k) = Sum_{k = 0..m} C(m,k)*C(x+k,m), is the Ehrhart polynomial of the m-dimensional cross polytope (the hyperoctahedron).
The first few values are p_0(x) = 1, p_1(x) = 2*x + 1, p_2(x) = 2*x^2 + 2*x + 1 and p_3(x) = (4*x^3 + 6*x^2 + 8*x + 3)/3.
The sequence {p_m(k)},k>=0 is the crystal ball sequence for the product lattice A_1 x... x A_1 (m copies). The table of values [p_m(k)]m,k>=0 is the array of Delannoy numbers A008288.
The polynomial p_m(x) is the unique polynomial solution of the difference equation (x + 1)*f(x+1) - x*f(x-1) = (2*m + 1)*f(x), normalized so that f(0) = 1. These polynomials have their zeros on the vertical line Re x = -1/2 in the complex plane, that is, the polynomials p_m(x-1), m = 1,2,3,..., satisfy a Riemann hypothesis [BUMP et al., Theorems 4 and 6]. The o.g.f. for the p_m(x) is (1 + t)^x/(1 - t)^(x+1) = 1 + (2*x + 1)*t + (2*x^2 + 2*x + 1)*t^2 + ....
The general recurrence in the first paragraph above also has a second solution b(n) = n!*p_m(n) with initial conditions b(1) = 2*m + 1, b(2) = (2*m + 1)^2 + 1.
Hence the behavior of a(n) for large n is given by lim_{n -> oo} a(n)/b(n) = Sum_{k >= 1} (-1)^(k+1)/(k*p_m(k-1)*p_m(k)) = 1/((2*m + 1) + 1^2/((2*m + 1) + 2^2/((2*m + 1) + 3^2/((2*m + 1) + ... + n^2/((2*m + 1) + ...))))) = (-1)^m * (log(2) - (1 - 1/2 + 1/3 - ... + (-1)^(m+1)/m)), where the final equality follows by a result of Ramanujan (see [Berndt, Chapter 12, Entry 29]).
For other sequences defined by similar recurrences and related to log(2) see A142983 and A142988. See also A142992 for the connection between log(2) and the C_n lattices. For corresponding results for the constants e, zeta(2) and zeta(3) see A000522, A142995 and A143003 respectively.

Bruce C. Berndt, Ramanujan's Notebooks Part II, Springer-Verlag.

Seiichi Manyama, Table of n, a(n) for n = 1..448
D. Bump, K. Choi, P. Kurlberg and J. Vaaler, A local Riemann hypothesis, I, Math. Zeit. 233, (2000), 1-19.

Cf. A008288, A024167, A142980, A142981, A142982, A142983, A142988, A142992, A317057.

p := n -> 2*n+1: a := n -> n!*p(n)*sum ((-1)^(k+1)/(k*p(k-1)*p(k)), k = 1..n): seq(a(n), n = 1..20)

RecurrenceTable[{a[1]==1,a[2]==3,a[n+2]==3a[n+1]+(n+1)^2 a[n]},a,{n,20}] (* Harvey P. Dale, May 20 2012 *)

a(n) = n!*p(n)*Sum_{k = 1..n} (-1)^(k+1)/(k*p(k-1)*p(k)), where p(n) = 2*n + 1.
Recurrence: a(1) = 1, a(2) = 3, a(n+2) = 3*a(n+1) + (n + 1)^2*a(n).
The sequence b(n):= n!*p(n) satisfies the same recurrence with b(1) = 3, b(2) = 10.
Hence we obtain the finite continued fraction expansion a(n)/b(n) = 1/(3 + 1^2/(3 + 2^2/(3 + 3^2/(3 + ... + (n-1)^2/3)))), for n >= 2.
Limit_{n -> oo} a(n)/b(n) = 1/(3 + 1^2/(3 + 2^2/(3 + 3^2/(3 + ... + (n-1)^2/(3 + ...))))) = Sum_{k >= 1} (-1)^(k+1)/(k*(4k^2 - 1)) = 1 - log(2).
Thus a(n) ~ c*n*n! as n -> oo, where c = 2*(1 - log(2)).
From Peter Bala, Dec 09 2024: (Start)
E.g.f.: A(x) = (2*x - (1 + x)*log(1 + x))/(1 - x)^2 satisfies the differential equation 1 + (x + 3)*A(x) + (x^2 - 1)*A'(x) = 0 with A(0) = 0.
Sum_{k = 1..n} Stirling_2(n, k) * a(k) = A317057(n+1). (End)

A005840 Expansion of (1-x)*e^x/(2-e^x).

Original entry on oeis.org

1, 1, 2, 8, 46, 332, 2874, 29024, 334982, 4349492, 62749906, 995818760, 17239953438, 323335939292, 6530652186218, 141326092842416, 3262247252671414, 80009274870905732, 2077721713464798210, 56952857434896699992, 1643312099715631960910

Offset: 0

Simon Plouffe

Also number of distinct resistances possible for n arbitrary resistors each connected in series or parallel with previous ones (cf. A051045).
The n-th term of A051045 uses the n different resistances 1, ..., n ohms, whereas the problem corresponding to A005840 allows arbitrary general resistances a1, a2, ..., an, chosen so as to give the maximum possible number of distinct equivalent resistances - Eric Weisstein
Stanley's Problem 5.4(a) involves threshold graphs; Problem 5.4(c) involves hyperplane arrangements.
a(n) is the number of labeled threshold graphs on n vertices. [This is more specific than the reference to Stanley.] [Svante Janson, Apr 01 2009]
If circuits were allowed that combine complex subcircuits in series or parallel, rather than requiring that one of them consists of a single resistor, then there are more additional possible resistances. For n = 4, there are additional 6 possible values. See illustration in links. - Kival Ngaokrajang, Aug 26 2013 (rephrased by Dave R.M. Langers, Nov 13 2013)
Conjecture: A285868 (with offset 1) shows the associated connected threshold graphs. - R. J. Mathar, Apr 29 2019
Re: above conjecture - the number of connected threshold graphs on n labeled vertices is A317057 (see also A053525). [David Galvin, Oct 18 2021]

			exp(x)*(1-x)/(2-exp(x)) = 1 + x + x^2 + 4/3*x^3 + 23/12*x^4 + 83/30*x^5 + 479/120*x^6 + 1814/315*x^7 + O(x^8); then the coefficients are multiplied by n! to get 1, 1, 2, 8, 46, 332, 2874, 29024, ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.4(a).

T. D. Noe, Table of n, a(n) for n=0..100
J. S. Beissinger and U. N. Peled, Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials, J Graphs Combin., 3 (1987), 213--219. MR903610 [From _Svante Janson_, Apr 01 2009]
Chao-Ping Chen and Xue-Feng Han, On Somos' quadratic recurrence constant, J. Number Theory, 166 (2016) 31-40. See page 34 equation (2.3).
Mike de Vries, Graphical realizations of degree sequences, packing multiple colors and random graphs, Master's Thesis, Utrecht Univ. (Netherlands, 2023).
Priyavrat Deshpande and Krishna Menon, Sketches, moves and partitions: counting regions of deformations of reflection arrangements, arXiv:2308.16653 [math.CO], 2023.
P. Diaconis, S. Holmes and S. Janson, Threshold graph limits and random threshold graphs, Internet. math 5 (3) (2008) 267-320.
D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.
Venkatesan Guruswami, Enumerative aspects of certain subclasses of perfect graphs, Discrete Math. 205 (1999), 97-117.
Andrew H. Hoefel and Jeff Mermin, Gotzmann squarefree ideals, Ill. J. Math. 56, No. 2, 397-414 (2012), Proposition 3.13.
Ricky I. Liu, K. Mészáros and A. H. Morales, Flow polytopes and the space of diagonal harmonics, arXiv preprint arXiv:1610.08370 [math.CO], 2016.
Kival Ngaokrajang, Illustration for n = 4; [a1, a2, a3, a4] = [3, 5, 7, 9]
Seunghyun Seo, The Catalan Threshold Arrangement, Journal of Integer Sequences, 2017 Vol. 20, #17.1.1.
Sam Spiro, Counting Threshold Graphs with Eulerian Numbers, arXiv:1909.06518 [math.CO], 2019.
R. P. Stanley, A zonotope associated with graphical degree sequences, in Applied Geometry and Discrete Combinatorics. DIMACS Series in Discrete Math., Amer. Math. Soc., Vol. 4, pp. 555-570, 1991.
Eric Weisstein's World of Mathematics, Resistor Network

2*A053525(n), n>1.

A005840 := proc(n) option remember;
1 - n + add(binomial(n, k) * A005840(k), k = 0..n-1) end:
seq(A005840(n), n = 0..20); # Peter Luschny, Oct 25 2021

nn = 20; Range[0, nn]! CoefficientList[Series[(1 - x) Exp[x]/(2 - Exp[x]), {x, 0, nn}], x] (* Harvey P. Dale, Jul 20 2011 *)

my(x='x+O('x^30)); Vec(serlaplace((1-x)*exp(x)/(2-exp(x)))); \\ Michel Marcus, Jan 04 2016

a(n) ~ n! * (1-log(2)) / (log(2))^(n+1). - Vaclav Kotesovec, Sep 29 2014
E.g.f.: (1 - x) * e^x / (2 - e^x).
E.g.f. A(x) satisfies (1 - x) * A'(x) = A(x) * (A(x) - x). - Michael Somos, Aug 01 2016
a(n+1) = n*(a(n) - a(n-1)) + Sum_{k=0..n} binomial(n, k) * a(k) * a(n-k). - Michael Somos, Aug 01 2016
a(n) = (1-n) + Sum_{k=0..n-1} binomial(n, k) * a(k). - Michael Somos, Aug 01 2016
BINOMIAL transform of A053525. - Michael Somos, Aug 01 2016
a(n) = Sum_{k=1..n-1} (n-k)*A008292(n-1,k-1)*2^k, for n>=2. - Sam Spiro, Sep 22 2019

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.

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.

A348436 Triangle read by rows. T(n,k) is the number of labeled threshold graphs on n vertices with k components, for 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 4, 3, 1, 23, 16, 6, 1, 166, 115, 40, 10, 1, 1437, 996, 345, 80, 15, 1, 14512, 10059, 3486, 805, 140, 21, 1, 167491, 116096, 40236, 9296, 1610, 224, 28, 1, 2174746, 1507419, 522432, 120708, 20916, 2898, 336, 36, 1, 31374953, 21747460, 7537095, 1741440, 301770, 41832, 4830, 480, 45, 1

Offset: 1

David Galvin, Oct 18 2021

The class of threshold graphs is the smallest class of graphs that includes K1 and is closed under adding isolated vertices and dominating vertices.

			Triangle begins:
         1;
         1,        1;
         4,        3,       1;
        23,       16,       6,       1;
       166,      115,      40,      10,      1;
      1437,      996,     345,      80,     15,     1;
     14512,    10059,    3486,     805,    140,    21,    1;
    167491,   116096,   40236,    9296,   1610,   224,   28,   1;
   2174746,  1507419,  522432,  120708,  20916,  2898,  336,  36,  1;
  31374953, 21747460, 7537095, 1741440, 301770, 41832, 4830, 480, 45, 1;
...

D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.
Sam Spiro, Counting Threshold Graphs with Eulerian Numbers, arXiv:1909.06518 [math.CO], 2019.

Cf. A005840 (row sums), A317057 (column k=1), A053525.

T := (n, k) -> `if`(n = k, 1, binomial(n, k-1)*A053525(n-k+1)):
for n from 1 to 10 do seq(T(n, k), k=1..n) od; # Peter Luschny, Oct 24 2021

eulerian[0, 0] := 1; eulerian[n_, m_] := eulerian[n, m] =
Sum[((-1)^k)*Binomial[n + 1, k]*((m + 1 - k)^n), {k, 0, m + 1}];
(* t[n] counts the labeled threshold graphs on n vertices *)
t[0] = 1; t[1] = 1;
t[n_] := t[n] = Sum[(n - k)*eulerian[n - 1, k - 1]*(2^k), {k, 1, n - 1}];
T[1, 1] := 1; T[n_, 1] := T[n, 1] = (1/2)*t[n]; T[n_, n_] := T[n, n] = 1;
T[n_, k_] := T[n, k] = Binomial[n, k - 1]*T[n - k + 1, 1];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten

T(1,1) = 1; for n >= 2, T(n,1) = A005840(n)/2; for n >= 3 and 2 <= k <= n-1, T(n,k) = binomial(n,k-1)*T(n-k+1,1); and for n >= 2, T(n,n)=1.

T(n, k) = binomial(n, k-1)*A053525(n - k + 1) if k != n, otherwise 1. - Peter Luschny, Oct 24 2021

Showing 1-5 of 5 results.

cp's OEIS Frontend

A142979 a(1) = 1, a(2) = 3, a(n+2) = 3*a(n+1) + (n+1)^2*a(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A005840 Expansion of (1-x)*e^x/(2-e^x).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

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

A348436 Triangle read by rows. T(n,k) is the number of labeled threshold graphs on n vertices with k components, for 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A142979 a(1) = 1, a(2) = 3, a(n+2) = 3a(n+1) + (n+1)^2a(n).