A000272 -id:A000272 - cp's OEIS frontend

A007778 a(n) = n^(n+1).

0, 1, 8, 81, 1024, 15625, 279936, 5764801, 134217728, 3486784401, 100000000000, 3138428376721, 106993205379072, 3937376385699289, 155568095557812224, 6568408355712890625, 295147905179352825856, 14063084452067724991009, 708235345355337676357632

Offset: 0

N. J. A. Sloane

Number of edges of the complete bipartite graph of order n+n^n, K_n,n^n. - Roberto E. Martinez II, Jan 07 2002
All rational solutions to the equation x^y = y^x, with x < y, are given by x = A000169(n+1)/A000312(n), y = A000312(n+1)/A007778(n), where n >= 1. - Nick Hobson, Nov 30 2006
a(n) is also the number of ways of writing an n-cycle as the product of n+1 transpositions. - Nikos Apostolakis, Nov 22 2008
a(n) is the total number of elements whose preimage is the empty set summed over all partial functions from [n] into [n]. - Geoffrey Critzer, Jan 12 2022

Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 67.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Nick Hobson, Exponential equation.
Yidong Sun and Jujuan Zhuang, lambda-factorials of n, arXiv:1007.1339 [math.CO], 2010. - _Peter Luschny_, Jul 09 2010

Cf. A000169, A000272, A000312, A007830, A008785, A008786, A008787, A008788, A008789, A008790, A008791, A135608.
Essentially the same as A065440.
Cf. A061250, A143857. [From Reinhard Zumkeller, Jul 23 2010]

[n^(n+1):n in [0..20]]; // Vincenzo Librandi, Jan 03 2012

seq( n^(n+1), n=0..20); # G. C. Greubel, Mar 05 2020

Table[n^(n+1), {n,0,20}] (* Vladimir Joseph Stephan Orlovsky, Oct 01 2008 *)

A007778[n]:=n^(n+1)$
makelist(A007778[n],n,0,30); /* Martin Ettl, Oct 29 2012 */

vector(21, n, my(m=n-1); m^(m+1)) \\ G. C. Greubel, Mar 05 2020

[n^(n+1) for n in (0..20)] # G. C. Greubel, Mar 05 2020

E.g.f.: -W(-x)/(1 + W(-x))^3, W(x) Lambert's function (principal branch).
a(n) = Sum_{k=0..n} binomial(n,k)*A000166(k+1)*(n+1)^(n-k). - Peter Luschny, Jul 09 2010
See A008517 and A134991 for similar e.g.f.s. and A048993. - Tom Copeland, Oct 03 2011
E.g.f.: d/dx {x/(T(x)*(1-T(x)))}, where T(x) = Sum_{n >= 1} n^(n-1)*x^n/n! is the tree function of A000169. - Peter Bala, Aug 05 2012
a(n) = n*A000312(n). - R. J. Mathar, Jan 12 2017
Sum_{n>=2} 1/a(n) = A135608. - Amiram Eldar, Nov 17 2020

A057500 Number of connected labeled graphs with n edges and n nodes.

Original entry on oeis.org

0, 0, 1, 15, 222, 3660, 68295, 1436568, 33779340, 880107840, 25201854045, 787368574080, 26667815195274, 973672928417280, 38132879409281475, 1594927540549217280, 70964911709203684440, 3347306760024413356032, 166855112441313024389625, 8765006377126199463936000

Offset: 1

Qing-Hu Hou and David C. Torney (dct(AT)lanl.gov), Sep 01 2000

Equivalently, number of connected unicyclic (i.e., containing one cycle) graphs on n labeled nodes. - Vladeta Jovovic, Oct 26 2004

a(n) is the number of trees on vertex set [n] = {1,2,...,n} rooted at 1 with one marked inversion (an inversion is a pair (i,j) with i > j and j a descendant of i in the tree). Here is a bijection from the title graphs (on [n]) to these marked trees. A title graph has exactly one cycle. There is a unique path from vertex 1 to this cycle, first meeting it at k, say (k may equal 1). Let i and j be the two neighbors of k in the cycle, with i the larger of the two. Delete the edge k<->j thereby forming a tree (in which j is a descendant of i) and take (i,j) as the marked inversion. To reverse this map, create a cycle by joining the smaller element of the marked inversion to the parent of the larger element. a(n) = binomial(n-1,2)*A129137(n). This is because, on the above marked trees, the marked inversion is uniformly distributed over 2-element subsets of {2,3,...,n} and so a(n)/binomial(n-1,2) is the number of trees on [n] (rooted at 1) for which (3,2) is an inversion. - David Callan, Mar 30 2007

			E.g., a(4)=15 because there are three different (labeled) 4-cycles and 12 different labeled graphs with a 3-cycle and an attached, external vertex.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.
C. L. Mallows, Letter to N. J. A. Sloane, 1980.
R. J. Riddell, Contributions to the theory of condensation, Dissertation, Univ. of Michigan, Ann Arbor, 1951.

Alois P. Heinz, Table of n, a(n) for n = 1..300 (terms n = 1..50 from Washington G. Bomfim)
Federico Ardila, Matthias Beck, Jodi McWhirter, The Arithmetic of Coxeter Permutahedra, arXiv:2004.02952 [math.CO], 2020.
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 133.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, arXiv:math/9310236 [math.PR], 1993.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
Younng-Jin Kim and Woong Kook, Winding number and Cutting number of Harmonic cycle, arXiv:1812.04930 [math.CO], 2018.
C. L. Mallows, Letter to N. J. A. Sloane, 1980
Marko Riedel et al., Non-isomorphic, connected, unicyclic graphs, Math Stackexchange, November 2018. (Proof of closed form by Cauchy Coefficient Formula / Lagrange Inversion.)
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.

A diagonal of A343088.
Cf. A000272 = labeled trees on n nodes; connected labeled graphs with n nodes and n+k edges for k=0..8: this sequence, A061540, A061541, A061542, A061543, A096117, A061544, A096150, A096224.
Cf. A001429 (unlabeled case), A052121.
For any number of edges we have A001187, unlabeled A001349.
This is the connected and covering case of A116508.
For #edges <= #nodes we have A129271, covering A367869.
For #edges > #nodes we have A140638, covering A367868.
This is the connected case of A367862 and A367863, unlabeled A006649.
The version with loops is A368951, unlabeled A368983.
This is the covering case of A370317.
Counting only covering vertices gives A370318.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
Cf. A062734, A098909, A123527, A129137, A133686, A143543, A323818, A367916, A367917, A369191, A369197.

egf:= -1/2*ln(1+LambertW(-x)) +1/2*LambertW(-x) -1/4*LambertW(-x)^2:
a:= n-> n!*coeff(series(egf, x, n+3), x, n):
seq(a(n), n=1..25);  # Alois P. Heinz, Mar 27 2013

nn=20; t=Sum[n^(n-1) x^n/n!, {n,1,nn}]; Drop[Range[0,nn]! CoefficientList[Series[Log[1/(1-t)]/2-t^2/4-t/2, {x,0,nn}], x], 1]  (* Geoffrey Critzer, Oct 07 2012 *)
a[n_] := (n-1)!*n^n/2*Sum[1/(n^k*(n-k)!), {k, 3, n}]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jan 15 2014, after Vladeta Jovovic *)
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[#]==n&&Length[csm[#]]<=1&]],{n,0,5}] (* Gus Wiseman, Feb 19 2024 *)

# Warning: Floating point calculation. Adjust precision as needed!
from mpmath import mp, chop, gammainc
mp.dps = 200; mp.pretty = True
for n in (1..100):
    print(chop((n^(n-2)*(1-3*n)+exp(n)*gammainc(n+1, n)/n)/2))
# Peter Luschny, Jan 27 2016

The number of labeled connected graphs with n nodes and m edges is Sum_{k=1..n} (-1)^(k+1)/k*Sum_{n_1+n_2+..n_k=n, n_i>0} n!/(Product_{i=1..k} (n_i)!)* binomial(s, m), s=Sum_{i..k} binomial(n_i, 2). - Vladeta Jovovic, Apr 10 2001
E.g.f.: (1/2) Sum_{k>=3} T(x)^k/k, with T(x) = Sum_{n>=1} n^(n-1)/n! x^n. R. J. Riddell's thesis contains a closed-form expression for the number of connected graphs with m nodes and n edges. The present series applies to the special case m=n.
E.g.f.: -1/2*log(1+LambertW(-x))+1/2*LambertW(-x)-1/4*LambertW(-x)^2. - Vladeta Jovovic, Jul 09 2001
Asymptotic expansion (with xi=sqrt(2*Pi)): n^(n-1/2)*[xi/4-7/6*n^(-1/2)+xi/48* n^(-1)+131/270*n^(-3/2)+xi/1152*n^(-2)+4/2835*n^(-5/2)+O(n^(-3))]. - Keith Briggs, Aug 16 2004
Row sums of A098909: a(n) = (n-1)!*n^n/2*Sum_{k=3..n} 1/(n^k*(n-k)!). - Vladeta Jovovic, Oct 26 2004
a(n) = Sum_{k=0..C(n-1,2)} k*A052121(n,k). - Alois P. Heinz, Nov 29 2015
a(n) = (n^(n-2)*(1-3*n)+exp(n)*Gamma(n+1,n)/n)/2. - Peter Luschny, Jan 27 2016
a(n) = A062734(n,n+1) = A123527(n,n). - Gus Wiseman, Feb 19 2024

More terms from Vladeta Jovovic, Jul 09 2001

A005195 Number of forests with n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, 8599, 20514, 49905, 122963, 307199, 775529, 1977878, 5086638, 13184156, 34402932, 90328674, 238474986, 632775648, 1686705630, 4514955632, 12132227370, 32717113805, 88519867048, 240235675303

Offset: 0

N. J. A. Sloane

Same as "Number of forests with n nodes that are perfect graphs" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015

Number of unlabeled acyclic graphs on n vertices. The labeled version is A001858. The covering case is A144958, connected A000055. - Gus Wiseman, Apr 29 2024

			From _Gus Wiseman_, Apr 29 2024: (Start)
Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 10 forests:
  {}  {}  {}    {}       {}          {}
          {12}  {12}     {12}        {12}
                {13,23}  {12,34}     {12,34}
                         {13,23}     {13,23}
                         {13,24,34}  {12,35,45}
                         {14,24,34}  {13,24,34}
                                     {14,24,34}
                                     {13,24,35,45}
                                     {14,25,35,45}
                                     {15,25,35,45}
(End)

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 5 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Forest.
Index entries for sequences related to forests

Cf. A095133 (by number of trees), A136605 (by number of edges).
A diagonal of A144215.
The connected case is A000055.
The labeled version is A001858.
The covering case is A144958, labeled A105784.
For triangles instead of cycles we have A006785, covering A372169.
Unique cycle: A236570 (labeled A372193), covering A372191 (labeled A372195).
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A000272, A002807, A054548, A137917, A367863, A372176.

EulerTransform[ seq_List ] := With[{m = Length[seq]}, CoefficientList[ Series[ Times @@ (1/(1 - x^Range[m])^seq), {x, 0, m}], x]];
b[n_] := b[n] = If[n <= 1, n, Sum[ Sum[ d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}]/(n - 1)];
a55[n_] := a55[n] = If[n == 0, 1, b[n] - (Sum[ b[k]*b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; A000055 = Table[ a55[n], {n, 1, 31}]; EulerTransform[ A000055 ] (* Jean-François Alcover, Mar 15 2012 *)

Euler transform of A000055: Product_{n>0} (1-x^n)^(-A000055(n)). a(n) = 1/n*Sum_{k=1..n} b(k)*a(n-k), where b(k) = Sum_{d divides k} d*A000055(d). - Vladeta Jovovic, Sep 05 2002
G.f.: exp(sum_{k>0} B(x^k)/k ), where B(x) = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + ... = C(x)-1 and C is the g.f. for A000055.
a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.9557652856519949747148..., c = 1.023158422... . - Vaclav Kotesovec, Nov 16 2014
First differences are A144958. - Gus Wiseman, Apr 29 2024

More terms from Vladeta Jovovic, Sep 05 2002

A129271 Number of labeled n-node connected graphs with at most one cycle.

Original entry on oeis.org

1, 1, 1, 4, 31, 347, 4956, 85102, 1698712, 38562309, 980107840, 27559801736, 849285938304, 28459975589311, 1030366840792576, 40079074477640850, 1666985134587145216, 73827334760713500233, 3468746291121007607808, 172335499299097826575564, 9027150377126199463936000

Offset: 0

Washington Bomfim, May 10 2008

The majority of those graphs of order 4 are trees since we have 16 trees and only 9 unicycles. See example.

Also connected graphs covering n vertices with at most n edges. The unlabeled version is A005703. - Gus Wiseman, Feb 19 2024

			a(4) = 16 + 3*3 = 31.
From _Gus Wiseman_, Feb 19 2024: (Start)
The a(0) = 1 through a(3) = 4 graph edge sets:
  {}  .  {{1,2}}  {{1,2},{1,3}}
                  {{1,2},{2,3}}
                  {{1,3},{2,3}}
                  {{1,2},{1,3},{2,3}}
(End)

J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.

Andrew Howroyd, Table of n, a(n) for n = 0..100
Wikipedia, PseudoForest.

Cf. A129137, A000272.
For any number of edges we have A001187, unlabeled A001349.
The unlabeled version is A005703.
The case of equality is A057500, covering A370317, cf. A370318.
The non-connected non-covering version is A133686.
The connected complement is A140638, unlabeled A140636, covering A367868.
The non-connected covering version is A367869 or A369191.
The version with loops is A369197, non-connected A369194.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A062734 counts connected graphs by number of edges.
Cf. A006649, A116508, A134964, A143543, A323818, A367862, A367863, A367867, A367916, A367917, A368951.

a := n -> `if`(n=0,1,((n-1)*exp(n)*GAMMA(n-1,n)+n^(n-2)*(3-n))/2):
seq(simplify(a(n)),n=0..16); # Peter Luschny, Jan 18 2016

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[Series[ Log[1/(1-t)]/2+t/2-3t^2/4+1,{x,0,nn}],x]  (* Geoffrey Critzer, Mar 23 2013 *)

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(log(1/(1-t))/2 + t/2 - 3*t^2/4 + 1))} \\ Andrew Howroyd, Nov 07 2019

a(0) = 1, for n >=1, a(n) = A000272(n) + A057500(n) = n^{n-2} + (n-1)(n-2)/2Sum_{r=1..n-2}( (n-3)!/(n-2-r)! )n^(n-2-r)
E.g.f.: log(1/(1-T(x)))/2 + T(x)/2 - 3*T(x)^2/4 + 1, where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Mar 23 2013
a(n) = ((n-1)*e^n*GAMMA(n-1,n)+n^(n-2)*(3-n))/2 for n>=1. - Peter Luschny, Jan 18 2016

Terms a(17) and beyond from Andrew Howroyd, Nov 07 2019

A001858 Number of forests of trees on n labeled nodes.

Original entry on oeis.org

1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616

Offset: 0

N. J. A. Sloane and Simon Plouffe

The number of integer lattice points in the permutation polytope of {1,2,...,n}. - Max Alekseyev, Jan 26 2010
Equals the number of score sequences for a tournament on n vertices. See Prop. 7 of the article by Bartels et al., or Example 3.1 in the article by Stanley. - David Radcliffe, Aug 02 2022
Number of labeled acyclic graphs on n vertices. The unlabeled version is A005195. The covering case is A105784, connected A000272. - Gus Wiseman, Apr 29 2024

			From _Gus Wiseman_, Apr 29 2024: (Start)
Edge-sets of the a(4) = 38 forests:
  {}  {12}  {12,13}  {12,13,14}
      {13}  {12,14}  {12,13,24}
      {14}  {12,23}  {12,13,34}
      {23}  {12,24}  {12,14,23}
      {24}  {12,34}  {12,14,34}
      {34}  {13,14}  {12,23,24}
            {13,23}  {12,23,34}
            {13,24}  {12,24,34}
            {13,34}  {13,14,23}
            {14,23}  {13,14,24}
            {14,24}  {13,23,24}
            {14,34}  {13,23,34}
            {23,24}  {13,24,34}
            {23,34}  {14,23,24}
            {24,34}  {14,23,34}
                     {14,24,34}
(End)

B. Bollobas, Modern Graph Theory, Springer, 1998, p. 290.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..388 (first 101 terms from T. D. Noe)
J. E. Bartels, J. Mount, and D. J. A. Welsh, The polytope of win vectors. Annals of Combinatorics 1, 1-15 (1997). https://doi.org/10.1007/BF02558460
David Callan, A Combinatorial Derivation of the Number of Labeled Forests, J. Integer Seqs., Vol. 6, 2003.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.o
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 132.
Samuele Giraudo, Combalgebraic structures on decorated cliques, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 7, arXiv:1709.08416 [math.CO], 2017.
Anton Izosimov, Matrix polynomials, generalized Jacobians, and graphical zonotopes, arXiv:1506.05179 [math.AG], 2015.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See pp. 32-33.
Arun P. Mani and Rebecca J. Stones, Congruences for weighted number of labeled forests, INTEGERS 16 (2016). #A17.
J. Pitman, Coalescent Random Forests, J. Combin. Theory, A85 (1999), 165-193.
J. Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.
J. Riordan, Letter to N. J. A. Sloane, Oct 19 1970
J. Riordan, Letter to N. J. A. Sloane, Nov 10 1975
John Riordan and N. J. A. Sloane, Correspondence, 1974
N. J. A. Sloane, Letter to J. Riordan, Nov. 1970
R. Stanley, Decompositions of rational convex polytopes, Ann. Discrete Math 6.6 (1980): 333-342.
L. Takacs, On the number of distinct forests, SIAM J. Discrete Math., 3 (1990), 574-581.
E. M. Wright, A relationship between two sequences, Proc. London Math. Soc. (3) 17 (1967) 296-304.
Index entries for sequences related to forests

The connected case is A000272, rooted A000169.
The unlabeled version is A005195, connected A000055.
The covering case is A105784, unlabeled A144958.
Row sums of A138464.
For triangles instead of cycles we have A213434, covering A372168.
For a unique cycle we have A372193, covering A372195.
A002807 counts cycles in a complete graph.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A006572, A006573, A088956.
Cf. A053530, A054548, A137916, A263340, A322661, A367863, A372176.

exp(x+x^2+add(n^(n-2)*x^n/n!, n=3..50));
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
      binomial(n-1, j-1)*j^(j-2)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Sep 15 2008
# third Maple program:
F:= exp(-LambertW(-x)*(1+LambertW(-x)/2)):
S:= series(F,x,51):
seq(coeff(S,x,j)*j!, j=0..50); # Robert Israel, May 21 2015

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[Exp[t-t^2/2],{x,0,nn}],x] (* Geoffrey Critzer, Sep 05 2012 *)
nmax = 20; CoefficientList[Series[-LambertW[-x]/(x*E^(LambertW[-x]^2/2)), {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jul 19 2019 *)

a(n)=if(n<0,0,sum(m=0,n,sum(j=0,m,binomial(m,j)*binomial(n-1,n-m-j)*n^(n-m-j)*(m+j)!/(-2)^j)/m!)) /* Michael Somos, Aug 22 2002 */

E.g.f.: exp( Sum_{n>=1} n^(n-2)*x^n/n! ). This implies (by a theorem of Wright) that a(n) ~ exp(1/2)*n^(n-2). - N. J. A. Sloane, May 12 2008 [Corrected by Philippe Flajolet, Aug 17 2008]
E.g.f.: exp(T - T^2/2), where T = T(x) = Sum_{n>=1} n^(n-1)*x^n/n! is Euler's tree function (see A000169). - Len Smiley, Dec 12 2001
Shifts 1 place left under the hyperbinomial transform (cf. A088956). - Paul D. Hanna, Nov 03 2003
a(0) = 1, a(n) = Sum_{j=0..n-1} C(n-1,j) (j+1)^(j-1) a(n-1-j) if n>0. - Alois P. Heinz, Sep 15 2008

More terms from Michael Somos, Aug 22 2002

A014068 a(n) = binomial(n*(n+1)/2, n).

Original entry on oeis.org

1, 1, 3, 20, 210, 3003, 54264, 1184040, 30260340, 886163135, 29248649430, 1074082795968, 43430966148115, 1917283000904460, 91748617512913200, 4730523156632595024, 261429178502421685800, 15415916972482007401455, 966121413245991846673830, 64123483527473864490450300

Offset: 0

N. J. A. Sloane

nonn

Product of next n numbers divided by product of first n numbers. E.g., a(4) = (7*8*9*10)/(1*2*3*4)= 210. - Amarnath Murthy, Mar 22 2004

Also the number of labeled loop-graphs with n vertices and n edges. The covering case is A368597. - Gus Wiseman, Jan 25 2024

			From _Gus Wiseman_, Jan 25 2024: (Start)
The a(0) = 1 through a(3) = 20 loop-graph edge-sets (loops shown as singletons):
  {}  {{1}}  {{1},{2}}    {{1},{2},{3}}
             {{1},{1,2}}  {{1},{2},{1,2}}
             {{2},{1,2}}  {{1},{2},{1,3}}
                          {{1},{2},{2,3}}
                          {{1},{3},{1,2}}
                          {{1},{3},{1,3}}
                          {{1},{3},{2,3}}
                          {{2},{3},{1,2}}
                          {{2},{3},{1,3}}
                          {{2},{3},{2,3}}
                          {{1},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}
                          {{1},{1,3},{2,3}}
                          {{2},{1,2},{1,3}}
                          {{2},{1,2},{2,3}}
                          {{2},{1,3},{2,3}}
                          {{3},{1,2},{1,3}}
                          {{3},{1,2},{2,3}}
                          {{3},{1,3},{2,3}}
                          {{1,2},{1,3},{2,3}}
(End)

Harvey P. Dale, Table of n, a(n) for n = 0..370
R. Mestrovic, Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862-2011), arXiv:1111.3057 [math.NT], 2011.
Eric Weisstein's World of Mathematics, Graph Loop.

Cf. A000217, A022915, A135860, A135861, A135862.
Diagonal of A084546.
Without loops we have A116508, covering A367863, unlabeled A006649.
Allowing edges of any positive size gives A136556, covering A054780.
The covering case is A368597.
The unlabeled version is A368598, covering A368599.
The connected case is A368951.
A000666 counts unlabeled loop-graphs, covering A322700.
A006125 (shifted left) counts loop-graphs, covering A322661.
A006129 counts covering simple graphs, connected A001187.
A058891 counts set-systems, unlabeled A000612.
Cf. A000085, A000272, A057500, A333331, A368596, A368730.

[Binomial(Binomial(n+1,2), n): n in [0..40]]; // G. C. Greubel, Feb 19 2022

Binomial[First[#],Last[#]]&/@With[{nn=20},Thread[{Accumulate[ Range[ 0,nn]], Range[ 0,nn]}]] (* Harvey P. Dale, May 27 2014 *)

from math import comb
def A014068(n): return comb(comb(n+1,2),n) # Chai Wah Wu, Jul 14 2024

[(binomial(binomial(n+1, n-1), n)) for n in range(20)] # Zerinvary Lajos, Nov 30 2009

For n >= 1, Product_{k=1..n} a(k) = A022915(n). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 08 2001
For n > 0, a(n) = A022915(n)/A022915(n-1). - Gerald McGarvey, Jul 26 2004
a(n) = binomial(T(n+1), T(n)) where T(n) = the n-th triangular number. - Amarnath Murthy, Jul 14 2005
a(n) = binomial(binomial(n+2, n), n+1) for n >= -1. - Zerinvary Lajos, Nov 30 2009
From Peter Bala, Feb 27 2020: (Start)
a(p) == (p + 1)/2 ( mod p^3 ) for prime p >= 5 (apply Mestrovic, equation 37).
Conjectural: a(2*p) == p*(2*p + 1) ( mod p^4 ) for prime p >= 5. (End)
a(n) = A084546(n,n). - Gus Wiseman, Jan 25 2024
a(n) = [x^n] (1+x)^(n*(n+1)/2). - Vaclav Kotesovec, Aug 06 2025

A000806 Bessel polynomial y_n(-1).

Original entry on oeis.org

1, 0, 1, -5, 36, -329, 3655, -47844, 721315, -12310199, 234615096, -4939227215, 113836841041, -2850860253240, 77087063678521, -2238375706930349, 69466733978519340, -2294640596998068569, 80381887628910919255, -2976424482866702081004, 116160936719430292078411

Offset: 0

N. J. A. Sloane

a(n) can be seen as a subset of the unordered pairings of the first 2n integers (A001147) with forbidden pairs (i,i+1) for all i in [1,2n-1] (all adjacent integers). The circular version of this constraint is A003436. - Olivier Gérard, Feb 08 2011
|a(n)| is the number of perfect matchings in the complement of P_{2n} where P_{2n} is the path graph on 2n vertices. - Andrew Howroyd, Mar 15 2016
The unsigned version of these numbers now has its own entry: see A278990. - N. J. A. Sloane, Dec 07 2016

			For n=3, the a(3) = 5 solutions are (14) (25) (36), (14) (26) (35), (15) (24) (36), (16) (24) (35), (13) (25) (46) excluding 10 other possible pairings.
G.f. = 1 + x^2 - 5*x^3 + 36*x^4 - 329*x^5 + 3655*x^6 - 47844*x^7 + ...

G. Kreweras and Y. Poupard, Sur les partitions en paires d'un ensemble fini totalement ordonné, Publications de l'Institut de Statistique de l'Université de Paris, 23 (1978), 57-74.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 77.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 0..404 (first 101 terms from T. D. Noe)
Ron M. Adin, Arkady Berenstein, Jacob Greenstein, Jian-Rong Li, Avichai Marmor, and Yuval Roichman, Transitive and Gallai colorings, arXiv:2309.11203 [math.CO], 2023. See p. 6.
G. Kreweras and Y. Poupard, Sur les partitions en paires d'un ensemble fini totalement ordonné, Publications de l'Institut de Statistique de l'Université de Paris, 23 (1978), 57-74. (Annotated scanned copy)
R. J. Mathar, A class of multinomial permutations avoiding object clusters, vixra:1511.0015 (2015), sequence M_{c,2}/c!.
J. Riordan, Letter to N. J. A. Sloane, Aug. 1970
Everett Sullivan, Linear chord diagrams with long chords, arXiv preprint arXiv:1611.02771 [math.CO], 2016.
J. Touchard, Nombres exponentiels et nombres de Bernoulli, Canad. J. Math., 8 (1956), 305-320.
Donovan Young, Linear k-Chord Diagrams, arXiv:2004.06921 [math.CO], 2020.
Index entries for sequences related to Bessel functions or polynomials

Polynomial coefficients are in A001498. Cf. A003436.

Cf. A001515, A101682, A278990.

I:=[0,1]; [1] cat [n le 2 select I[n] else (1-2*n)*Self(n-1)+Self(n-2): n in [1..30]]; // Vincenzo Librandi, Apr 19 2015

A000806 := proc(n) option remember; if n<=1 then 1-n else (1-2*n)*procname(n-1)+procname(n-2); fi; end proc;
a := n -> hypergeom([n+1,-n],[],1/2): seq(simplify(a(n)),n=0..20); # Peter Luschny, Nov 10 2016

a[n_] := a[n] = (-2n+1)*a[n-1] + a[n-2]; a[0] = 1; a[1] = 0; Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Nov 29 2011, after T. D. Noe *)
Table[Sum[Binomial[n, i]*(2*n-i)!/2^(n-i)*(-1)^(n-i)/n!, {i, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Aug 07 2013 *)
a[ n_] := With[ {m = If[ n<0, -n-1, n]}, (-1)^m (2 m - 1)!! Hypergeometric1F1[ -m, -2 m, -2] ]; (* Michael Somos, Jan 27 2014 *)
a[ n_] := With[ {m = If[ n<0, -n-1, n]}, Sum[ (-1)^(m - i) (2 m - i)! / (2^(m - i) i! (m - i)!), {i, 0, m}] ]; (* Michael Somos, Jan 27 2014 *)
a[ n_] := With[ {m = If[ n<0, -n-1, n]}, If[ m<1, 1, (-1)^m Numerator @ FromContinuedFraction[ Table[ (-1)^Quotient[k, 2] If[ OddQ[k], k, 1], {k, 2 m}] ] ] ]; (* Michael Somos, Jan 27 2014 *)
Table[(-1)^n (2 n - 1)!! Hypergeometric1F1[-n, -2 n, -2], {n, 0, 20}] (* Eric W. Weisstein, Nov 14 2018 *)

{a(n) = if( n<0, n = -n-1); sum(k=0, n, (2*n-k)! / (k! * (n-k)!) * (-1/2)^(n-k) )}; /* Michael Somos, Apr 02 2007 */

{a(n) = local(A); if( n<0, n = -n-1); A = sqrt(1 + 2*x + x * O(x^n)); n! * polcoeff( exp(A-1) / A, n)}; /* Michael Somos, Apr 02 2007 */

{a(n) = local(A); if( n<0, n = -n-1); n+=2; -(-1)^n * n! * polcoeff( serreverse( sum(k=1, n, k^(k-2)* x^k / k!, x * O(x^n))), n)}; /* Michael Somos, Apr 02 2007 */

{a(n) = if( n<0, n=-n-1); contfracpnqn( vector( 2*n, k, (-1)^(k\2) * if( k%2, k, 1))) [1,1] }; /* Michael Somos, Jan 27 2014 */

E.g.f.: exp(sqrt(1 + 2*x) - 1) / sqrt(1 + 2*x). - Michael Somos, Feb 16 2002
D-finite with recurrence a(n) = (-2*n+1)*a(n-1) + a(n-2). - T. D. Noe, Oct 26 2006
If y = x + Sum_{k>1} A000272(k) * x^k/k!, then y = x + Sum{k>1} a(k-2) * (-y)^k/k!. - Michael Somos, Sep 07 2005
a(-1-n) = a(n). - Michael Somos, Apr 02 2007
a(n) = Sum_{m=0..n} A001498(n,m)*(-1)^m, n>=0 (alternating row sums of Bessel triangle).
E.g.f. for unsigned version: -exp(sqrt(1-2*x)-1). - Karol A. Penson, Mar 20 2010 [gives -1, 1, 0, 1, 5, 36, 329, ... ]
E.g.f. for unsigned version: 1/(sqrt(1-2*x))*exp(sqrt(1-2*x)-1). - Sergei N. Gladkovskii, Jul 03 2012
G.f.: 1/G(0) where G(k) = 1 - x + x*(2*k+1)/(1 - x + 2*x*(k+1)/G(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Jul 10 2012
G.f.: 1+x/U(0)  where U(k) = 1 - x + x*(k+1)/U(k+1) ; (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Oct 06 2012
a(n) = BesselK[n+1/2,-1]/BesselK[5/2,-1]. - Vaclav Kotesovec, Aug 07 2013
|a(n)| ~ 2^(n+1/2)*n^n/exp(n+1). - Vaclav Kotesovec, Aug 07 2013
0 = a(n) * (a(n+2)) + a(n+1) * (-a(n+1) + 2*a(n+2) + a(n+3)) + a(n+2) * (-a(n+2)) for all n in Z. - Michael Somos, Jan 27 2014
a(n) = -i*(BesselK[3/2,1]*BesselI[n+3/2,-1] - BesselI[3/2,-1]*BesselK[n+3/2,1]), n>=0 for unsigned version - G. C. Greubel , Apr 19 2015
a(n) = hypergeom( [n+1, -n], [], 1/2). - Peter Luschny, Nov 10 2016
From G. C. Greubel, Aug 16 2017: (Start)
a(n) = (1/2)_{n} * (-2)^n * hypergeometric1f1(-n; -2*n; -2).
G.f.: (1/(1-t))*hypergeometric2f0(1, 1/2; -; -2*t/(1-t)^2). (End)

A005703 Number of n-node connected graphs with at most one cycle.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 19, 44, 112, 287, 763, 2041, 5577, 15300, 42419, 118122, 330785, 929469, 2621272, 7411706, 21010378, 59682057, 169859257, 484234165, 1382567947, 3952860475, 11315775161, 32430737380, 93044797486, 267211342954, 768096496093, 2209772802169

Offset: 0

N. J. A. Sloane, R. K. Guy

a(n) is the number of pseudotrees on n nodes. - Eric W. Weisstein, Jun 11 2012

Also unlabeled connected graphs covering n vertices with at most n edges. For this definition we have a(1) = 0 and possibly a(0) = 0. - Gus Wiseman, Feb 20 2024

			From _Gus Wiseman_, Feb 20 2024: (Start)
Representatives of the a(0) = 1 through a(5) = 8 graphs:
  {}  .  {12}  {12,13}     {12,13,14}     {12,13,14,15}
               {12,13,23}  {12,13,24}     {12,13,14,25}
                           {12,13,14,23}  {12,13,24,35}
                           {12,13,24,34}  {12,13,14,15,23}
                                          {12,13,14,23,25}
                                          {12,13,14,23,45}
                                          {12,13,14,25,35}
                                          {12,13,24,35,45}
(End)

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Washington Bomfim, Table of n, a(n) for n = 0..500
R. K. Guy, Letters to N. J. A. Sloane and J. W. Moon, 1988
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
Eric Weisstein's World of Mathematics, Pseudotree
Wikipedia, Pseudoforest

Cf. A000055, A000081, A001429 (labeled A057500), A134964 (number of pseudoforests, labeled A133686).
The labeled version is A129271.
The connected complement is A140636, labeled A140638.
Non-connected: A368834 (labeled A367869) or A370316 (labeled A369191).
A001187 counts connected graphs, unlabeled A001349.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A062734 counts connected graphs by number of edges.
Cf. A000272, A006649, A116508, A140637, A143543, A367862, A367863, A368951, A369197, A370317, A370318.

Needs["Combinatorica`"]; nn = 20; t[x_] := Sum[a[n] x^n, {n, 1, nn}];
a[0] = 0;
b = Drop[Flatten[
    sol = SolveAlways[
      0 == Series[
        t[x] - x Product[1/(1 - x^i)^a[i], {i, 1, nn}], {x, 0, nn}],
      x]; Table[a[n], {n, 0, nn}] /. sol], 1];
r[x_] := Sum[b[[n]] x^n, {n, 1, nn}]; c =
Drop[Table[
    CoefficientList[
     Series[CycleIndex[DihedralGroup[n], s] /.
       Table[s[i] -> r[x^i], {i, 1, n}], {x, 0, nn}], x], {n, 3,
     nn}] // Total, 1];
d[x_] := Sum[c[[n]] x^n, {n, 1, nn}]; CoefficientList[
Series[r[x] - (r[x]^2 - r[x^2])/2 + d[x] + 1, {x, 0, nn}], x] (* Geoffrey Critzer, Nov 17 2014 *)

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(t=TreeGf(n)); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); Vec(1 + g(1) + (g(2) - g(1)^2)/2 + sum(k=3, n, sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/k + if(k%2, g(1)*g(2)^(k\2), (g(1)^2+g(2))*g(2)^(k/2-1)/2))/2)}; \\ Andrew Howroyd and Washington Bomfim, May 15 2021

a(n) = A000055(n) + A001429(n).

More terms from Vladeta Jovovic, Apr 19 2000 and from Michael Somos, Apr 26 2000

a(27) corrected and a(28) and a(29) computed by Washington Bomfim, May 14 2008

A140638 Number of connected graphs on n labeled nodes that contain at least two cycles.

Original entry on oeis.org

0, 0, 0, 7, 381, 21748, 1781154, 249849880, 66257728763, 34495508486976, 35641629989151608, 73354595357480683904, 301272202621204113362497, 2471648811029413368450098688, 40527680937730440155535277704046, 1328578958335783199341353852258282496

Offset: 1

Washington Bomfim, May 21 2008

nonn

These are the connected graphs that are neither trees nor unicyclic.

Also connected non-choosable graphs covering n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The unlabeled version is A140636. The complement is counted by A129271. - Gus Wiseman, Feb 20 2024

J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.

Andrew Howroyd, Table of n, a(n) for n = 1..50

The unlabeled version is A140636.
Cf. A000272 (trees), A001187 (connected graphs), A057500 (connected unicyclic graphs).
The complement is counted by A129271, unlabeled A005703.
The non-connected complement is A133686, covering A367869.
The non-connected version is A367867, unlabeled A140637.
The non-connected covering version is A367868.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A143543 counts simple labeled graphs by number of connected components.
Cf. A001349, A116508, A355740, A367769, A367863, A367901, A367903, A370317.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]<=1&&Select[Tuples[#],UnsameQ@@#&]=={}&]],{n,0,5}] (* Gus Wiseman, Feb 19 2024 *)

seq(n)={my(A=O(x*x^n), t=-lambertw(-x + A)); Vec(serlaplace( log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, A)) - log(1/(1-t))/2 - t/2 + 3*t^2/4), -n)} \\ Andrew Howroyd, Jan 15 2022

a(n) = A001187(n) - A129271(n).

a(n) = A001187(n) - A000272(n) - A057500(n).

Definition clarified by Andrew Howroyd, Jan 15 2022

A054581 Number of unlabeled 2-trees with n nodes.

Original entry on oeis.org

0, 1, 1, 1, 2, 5, 12, 39, 136, 529, 2171, 9368, 41534, 188942, 874906, 4115060, 19602156, 94419351, 459183768, 2252217207, 11130545494, 55382155396, 277255622646, 1395731021610, 7061871805974, 35896206800034, 183241761631584

Offset: 1

Vladeta Jovovic, Apr 11 2000

A 2-tree is recursively defined as follows: K_2 is a 2-tree and any 2-tree on n+1 vertices is obtained by joining a vertex to a 2-clique in a 2-tree on n vertices. Care is needed with the term 2-tree (and k-tree in general) because it has at least two commonly used definitions.
A036361 gives the labeled version of this sequence, which has an easy formula analogous to Cayley's formula for the number of trees.
Also, number of unlabeled 3-gonal 2-trees with n 3-gons.

			a(1)=0 because K_1 is not a 2-tree;
a(2)=a(3)=1 because K_2 and K_3 are the only 2-trees on those sizes.
a(4)=1 because there is a unique example obtained by joining a triangle to K_3 along an edge (thus forming K_4\e). The two graphs on 5 nodes are obtained by joining a triangle to K_4\e, either along the shared edge or along one of the non-shared edges.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 327-328.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 76, t(x), (3.5.19).

Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
T. Fowler, I. Gessel, G. Labelle, and P. Leroux, The specification of 2-trees, Adv. Appl. Math. 28 (2) (2002) 145-168, Table 1.
Nick Early, Anaëlle Pfister, and Bernd Sturmfels, Minimal Kinematics on M_{0,n}, arXiv:2402.03065 [math.AG], 2024.
Andrew Gainer-Dewar, Gamma-Species and the Enumeration of k-Trees, Electronic Journal of Combinatorics, Volume 19 (2012), #P45. - From _N. J. A. Sloane_, Dec 15 2012
Gilbert Labelle, Cédric Lamathe, and Pierre Leroux, Labeled and unlabeled enumeration of k-gonal 2-trees, arXiv:math/0312424 [math.CO], 2003.
Eric Weisstein's World of Mathematics, k-Tree.
Index entries for sequences related to trees

Column k=3 of A340811, column k=2 of A370770.

Cf. A000272 (labeled trees), A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A000055 (unlabeled trees).

Additional comments from Gordon F. Royle, Dec 02 2002

Missing initial term 0 inserted by Brendan McKay, Aug 07 2023

cp's OEIS Frontend

A007778 a(n) = n^(n+1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

Sage

Formula

A057500 Number of connected labeled graphs with n edges and n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

A005195 Number of forests with n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A129271 Number of labeled n-node connected graphs with at most one cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A001858 Number of forests of trees on n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A014068 a(n) = binomial(n*(n+1)/2, n).

Views

Author

Keywords

Comments