A053506 -id:A053506 - cp's OEIS frontend

A000169 Number of labeled rooted trees with n nodes: n^(n-1).

1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 1000000000, 25937424601, 743008370688, 23298085122481, 793714773254144, 29192926025390625, 1152921504606846976, 48661191875666868481, 2185911559738696531968, 104127350297911241532841, 5242880000000000000000000

Offset: 1

N. J. A. Sloane

Also the number of connected transitive subtree acyclic digraphs on n vertices. - Robert Castelo, Jan 06 2001
For any given integer k, a(n) is also the number of functions from {1,2,...,n} to {1,2,...,n} such that the sum of the function values is k mod n. - Sharon Sela (sharonsela(AT)hotmail.com), Feb 16 2002
The n-th term of a geometric progression with first term 1 and common ratio n: a(1) = 1 -> 1,1,1,1,... a(2) = 2 -> 1,2,... a(3) = 9 -> 1,3,9,... a(4) = 64 -> 1,4,16,64,... - Amarnath Murthy, Mar 25 2004
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, 2, 3, ... . - Nick Hobson, Nov 30 2006
a(n+1) is also the number of partial functions on n labeled objects. - Franklin T. Adams-Watters, Dec 25 2006
In other words, if A is a finite set of size n-1, then a(n) is the number of binary relations on A that are also functions. Note that a(n) = Sum_{k=0..n-1} binomial(n-1,k)*(n-1)^k = n^(n-1), where binomial(n-1,k) is the number of ways to select a domain D of size k from A and (n-1)^k is the number of functions from D to A. - Dennis P. Walsh, Apr 21 2011
This is the fourth member of a set of which the other members are the symmetric group, full transformation semigroup, and symmetric inverse semigroup. For the first three, see A000142, A000312, A002720. - Peter J. Cameron, Nov 03 2024.
More generally, consider the class of sequences of the form a(n) = (n*c(1)*...*c(i))^(n-1). This sequence has c(1)=1. A052746 has a(n) = (2*n)^(n-1), A052756 has a(n) = (3*n)^(n-1), A052764 has a(n) = (4*n)^(n-1), A052789 has a(n) = (5*n)^(n-1) for n>0. These sequences have a combinatorial structure like simple grammars. - Ctibor O. Zizka, Feb 23 2008
a(n) is equal to the logarithmic transform of the sequence b(n) = n^(n-2) starting at b(2). - Kevin Hu (10thsymphony(AT)gmail.com), Aug 23 2010
Also, number of labeled connected multigraphs of order n without cycles except one loop. See link below to have a picture showing the bijection between rooted trees and multigraphs of this kind. (Note that there are no labels in the picture, but the bijection remains true if we label the nodes.) - Washington Bomfim, Sep 04 2010
a(n) is also the number of functions f:{1,2,...,n} -> {1,2,...,n} such that f(1) = 1.
For a signed version of A000169 arising from the Vandermonde determinant of (1,1/2,...,1/n), see the Mathematica section. - Clark Kimberling, Jan 02 2012
Numerator of (1+1/(n-1))^(n-1) for n>1. - Jean-François Alcover, Jan 14 2013
Right edge of triangle A075513. - Michel Marcus, May 17 2013
a(n+1) is the number of n x n binary matrices with no more than a single one in each row. Partitioning the set of such matrices by the number k of rows with a one, we obtain a(n+1) = Sum_{k=0..n} binomial(n,k)*n^k = (n+1)^n. - Dennis P. Walsh, May 27 2014
Central terms of triangle A051129: a(n) = A051129(2*n-1,n). - Reinhard Zumkeller, Sep 14 2014
a(n) is the row sum of the n-th rows of A248120 and A055302, so it enumerates the monomials in the expansion of [x(1) + x(2) + ... + x(n)]^(n-1). - Tom Copeland, Jul 17 2015
For any given integer k, a(n) is the number of sums x_1 + ... + x_m = k (mod n) such that: x_1, ..., x_m are nonnegative integers less than n, the order of the summands does not matter, and each integer appears fewer than n times as a summand. - Carlo Sanna, Oct 04 2015
a(n) is the number of words of length n-1 over an alphabet of n letters. - Joerg Arndt, Oct 07 2015
a(n) is the number of parking functions whose largest element is n and length is n. For example, a(3) = 9 because there are nine such parking functions, namely (1,2,3), (1,3,2), (2,3,1), (2,1,3), (3,1,2), (3,2,1), (1,1,3), (1,3,1), (3,1,1). - Ran Pan, Nov 15 2015
Consider the following problem: n^2 cells are arranged in a square array. A step can be defined as going from one cell to the one directly above it, to the right of it or under it. A step above cannot be followed by a step below and vice versa. Once the last column of the square array is reached, you can only take steps down. a(n) is the number of possible paths (i.e., sequences of steps) from the cell on the bottom left to the cell on the bottom right. - Nicolas Nagel, Oct 13 2016
The rationals c(n) = a(n+1)/a(n), n >= 1, appear in the proof of G. Pólya's "elementary, but not too elementary, theorem": Sum_{n>=1} (Product_{k=1..n} a_k)^(1/n) < exp(1)*Sum_{n>=1} a_n, for n >= 1, with the sequence {a_k}{k>=1} of nonnegative terms, not all equal to 0. - _Wolfdieter Lang, Mar 16 2018
Coefficients of the generating series for the preLie operadic algebra. Cf. p. 417 of the Loday et al. paper. - Tom Copeland, Jul 08 2018
a(n)/2^(n-1) is the square of the determinant of the n X n matrix M_n with elements m(j,k) = cos(Pi*j*k/n). See Zhi-Wei Sun, Petrov link. - Hugo Pfoertner, Sep 19 2021
a(n) is the determinant of the n X n matrix P_n such that, when indexed [0, n), P(0, j) = 1, P(i <= j) = i, and P(i > j) = i-n. - C.S. Elder, Mar 11 2024

			For n=3, a(3)=9 because there are exactly 9 binary relations on A={1, 2} that are functions, namely: {}, {(1,1)}, {(1,2)}, {(2,1)}, {(2,2)}, {(1,1),(2,1)}, {(1,1),(2,2)}, {(1,2),(2,1)} and {(1,2),(2,2)}. - _Dennis P. Walsh_, Apr 21 2011
G.f. = x + 2*x^2 + 9*x^3 + 64*x^4 + 625*x^5 + 7776*x^6 + 117649*x^7 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 169.
Jonathan L. Gross and Jay Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 524.
Hannes Heikinheimo, Heikki Mannila and Jouni K. Seppnen, Finding Trees from Unordered 01 Data, in Knowledge Discovery in Databases: PKDD 2006, Lecture Notes in Computer Science, Volume 4213/2006, Springer-Verlag. - N. J. A. Sloane, Jul 09 2009
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 63.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 128.
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).
Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 25, Prop. 5.3.2, and p. 37, (5.52).

N. J. A. Sloane, Table of n, a(n) for n = 1..100
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. - _N. J. A. Sloane_, Oct 08 2012
Washington Bomfim, Bijection between rooted forests and multigraphs without cycles except one loop in each connected component. [From _Washington Bomfim_, Sep 04 2010]
David Callan, A Combinatorial Derivation of the Number of Labeled Forests, J. Integer Seqs., Vol. 6, 2003.
Peter J. Cameron and Philippe Cara, Independent generating sets and geometries for symmetric groups, J. Algebra, Vol. 258, no. 2 (2002), 641-650.
Robert Castelo and Arno Siebes, A characterization of moral transitive directed acyclic graph Markov models as trees, Technical Report CS-2000-44, Faculty of Computer Science, University of Utrecht.
Robert Castelo and Arno Siebes, A characterization of moral transitive acyclic directed graph Markov models as labeled trees, Journal of Statistical Planning and Inference, Vol. 115, No. 1 (2003), pp. 235-259; alternative link.
Frédéric Chapoton, Florent Hivert and Jean-Christophe Novelli, A set-operad of formal fractions and dendriform-like sub-operads, Journal of Algebra, Vol. 465 (2016), pp. 322-355; arXiv preprint, arXiv:1307.0092 [math.CO], 2013.
Ali Chouria, Vlad-Florin Drǎgoi, Jean-Gabriel Luque, On recursively defined combinatorial classes and labelled trees, arXiv:2004.04203 [math.CO], 2020.
R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey and D. E. Knuth, On the Lambert W Function, Advances in Computational Mathematics, VOl. 5 (1996), pp. 329-359; alternative link.
Nick Hobson, Solution to puzzle 48: Exponential equation.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 67.
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 p. 33.
Jean-Louis Loday and Bruno Vallette, Algebraic Operads, version 0.99, 2012.
G. Pólya, With, or Without, Motivation?, Amer. Math. Monthly, Vol. 56, No. 10 (1949), pp. 684-691. Reprinted in "A Century of Mathematics", John Ewing (ed.), Math. Assoc. of Amer., 1994, pp. 195-200 (the reference there is wrong).
Gwenaël Richomme, Characterization of infinite LSP words and endomorphisms preserving the LSP property, International Journal of Foundations of Computer Science, Vol. 30, No. 1 (2019), pp. 171-196; arXiv preprint, arXiv:1808.02680 [cs.DM], 2018.
Marko Riedel, math.stackexchange.com, Proof of an identity relating the tree function T(z) and the second order Eulerian numbers. Feb. 28, 2021.
Marko Riedel, math.stackexchange.com, Asymptotics of tree function statistics using Pusieux series
Frank Ruskey, Information on Rooted Trees.
N. J. A. Sloane, Illustration of initial terms
Zhi-Wei Sun, Fedor Petrov, A surprising identity, discussion in MathOverflow, Jan 17 2019.
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See p. 12.
Eric Weisstein's World of Mathematics, Graph Vertex.
Dimitri Zvonkine, An algebra of power series arising in the intersection theory of moduli spaces of curves and in the enumeration of ramified coverings of the sphere, arXiv:math/0403092 [math.AG], 2004.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
Index entries for "core" sequences

Cf. A000055, A000081, A000142, A000272, A000312, A002720, A007778, A007830, A008785-A008791, A055860, A002061, A052746, A052756, A052764, A052789, A051129, A098686, A247363, A055302, A248120, A130293, A053506-A053509, A262974.

Other classes of endofunctions: A275549-A275558.

a000169 n = n ^ (n - 1)  -- Reinhard Zumkeller, Sep 14 2014

[n^(n-1): n in [1..20]]; // Vincenzo Librandi, Jul 17 2015

A000169 := n -> n^(n-1);
# second program:
spec := [A, {A=Prod(Z, Set(A))}, labeled]; [seq(combstruct[count](spec, size=n), n=1..20)];
# third program:
A000169 := n -> add((-1)^(n+k-1)*pochhammer(n, k)*Stirling2(n-1, k), k = 0..n-1):
seq(A000169(n), n = 1 .. 23);  # Mélika Tebni, May 07 2023

Table[n^(n - 1), {n, 1, 20}] (* Stefan Steinerberger, Apr 01 2006 *)
Range[0, 18]! CoefficientList[ Series[ -LambertW[-x], {x, 0, 18}], x] // Rest (* Robert G. Wilson v, updated by Jean-François Alcover, Oct 14 2019 *)
(* Next, a signed version A000169 from the Vandermonde determinant of (1,1/2,...,1/n) *)
f[j_] := 1/j; z = 12;
v[n_] := Product[Product[f[k] - f[j], {j, 1, k - 1}], {k, 2, n}]
Table[v[n], {n, 1, z}]
1/%  (* A203421 *)
Table[v[n]/v[n + 1], {n, 1, z - 1}]  (* A000169 signed *)
(* Clark Kimberling, Jan 02 2012 *)
a[n_]:=Det[Table[If[i==0,1,If[i<=j,i,i-n]],{i,0,n-1},{j,0,n-1}]]; Array[a,20] (* Stefano Spezia, Mar 12 2024 *)

n^(n-1) $ n=1..20 /* Zerinvary Lajos, Apr 01 2007 */

PARI
```
a(n) = n^(n-1)
```

def a(n): return n**(n-1)
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Sep 19 2021

from sympy import Matrix
def P(n): return [[ (i-n if i > j else i) + (i == 0) for j in range(n) ] for i in range(n)]
print(*(Matrix(P(n)).det() for n in range(1, 21)), sep=', ') # C.S. Elder, Mar 12 2024

The e.g.f. T(x) = Sum_{n>=1} n^(n-1)*x^n/n! satisfies T(x) = x*exp(T(x)), so T(x) is the functional inverse (series reversion) of x*exp(-x).
Also T(x) = -LambertW(-x) where W(x) is the principal branch of Lambert's function.
T(x) is sometimes called Euler's tree function.
a(n) = A000312(n-1)*A128434(n,1)/A128433(n,1). - Reinhard Zumkeller, Mar 03 2007
E.g.f.: LambertW(x)=x*G(0); G(k) = 1 - x*((2*k+2)^(2*k))/(((2*k+1)^(2*k)) - x*((2*k+1)^(2*k))*((2*k+3)^(2*k+1))/(x*((2*k+3)^(2*k+1)) - ((2*k+2)^(2*k+1))/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 30 2011
a(n) = Sum_{i=1..n} binomial(n-1,i-1)*i^(i-2)*(n-i)^(n-i). - Dmitry Kruchinin, Oct 28 2013
Limit_{n->oo} a(n)/A000312(n-1) = e. - Daniel Suteu, Jul 23 2016
From Amiram Eldar, Nov 20 2020: (Start)
Sum_{n>=1} 1/a(n) = A098686.
Sum_{n>=1} (-1)^(n+1)/a(n) = A262974. (End)
a(n) = Sum_{k=0..n-1} (-1)^(n+k-1)*Pochhammer(n, k)*Stirling2(n-1, k). - Mélika Tebni, May 07 2023
In terms of Eulerian numbers A340556(n,k) of the second order Sum_{m>=1} m^(m+n) z^m/m! = 1/(1-T(z))^(2n+1) * Sum_{k=0..n} A2(n,k) T(z)^k. - Marko Riedel, Jan 10 2024

A049363 a(1) = 1; for n > 1, smallest digitally balanced number in base n.

Original entry on oeis.org

1, 2, 11, 75, 694, 8345, 123717, 2177399, 44317196, 1023456789, 26432593615, 754777787027, 23609224079778, 802772380556705, 29480883458974409, 1162849439785405935, 49030176097150555672, 2200618769387072998445, 104753196945250864004691, 5271200265927977839335179

Offset: 1

Harvey P. Dale

A037968(a(n)) = n and A037968(m) < n for m < a(n). - Reinhard Zumkeller, Oct 27 2003

Also smallest pandigital number in base n. - Franklin T. Adams-Watters, Nov 15 2006

			a(6) = 102345_6 = 1*6^5 + 2*6^3 + 3*6^2 + 4*6^1 + 5*6^0 = 8345.

Reinhard Zumkeller, Table of n, a(n) for n = 1..250
Eric Weisstein's World of Mathematics, Pandigital Number
Wikipedia, Pandigital number
Chai Wah Wu, Pandigital and penholodigital numbers, arXiv:2403.20304 [math.GM], 2024. See p. 1.

Column k=1 of A061845 and A378000 (for n>1).

Cf. A031443, A049354, A049355, A023811.

a049363 n = foldl (\v d -> n * v + d) 0 (1 : 0 : [2..n-1])
-- Reinhard Zumkeller, Apr 04 2012

a:= n-> n^(n-1)+add((n-i)*n^(i-1), i=1..n-2):
seq(a(n), n=1..23);  # Alois P. Heinz, May 02 2020

Table[FromDigits[Join[{1,0},Range[2,n-1]],n],{n,20}] (* Harvey P. Dale, Oct 12 2012 *)

A049363(n)=n^(n-1)+sum(i=1,n-2,n^(i-1)*(n-i))  \\ M. F. Hasler, Jan 10 2012

A049363(n)=if(n>1,(n^n-n)/(n-1)^2+n^(n-2)*(n-1)-1,1)  \\ M. F. Hasler, Jan 12 2012

def A049363(n): return (n**n-n)//(n-1)**2+n**(n-2)*(n-1)-1 if n>1 else 1 # Chai Wah Wu, Mar 13 2024

a(n) = (102345....n-1) in base n. - Ulrich Schimke (ulrschimke(AT)aol.com)
For n > 1, a(n) = (n^n-n)/(n-1)^2 + n^(n-2)*(n-1) - 1 = A023811(n) + A053506(n). - Franklin T. Adams-Watters, Nov 15 2006
a(n) = n^(n-1) + Sum_{m=2..n-1} m * n^(n - 1 - m). - Alexander R. Povolotsky, Sep 18 2022

More terms from Ulrich Schimke (ulrschimke(AT)aol.com)

A053507 a(n) = binomial(n-1,2)*n^(n-3).

Original entry on oeis.org

0, 0, 1, 12, 150, 2160, 36015, 688128, 14880348, 360000000, 9646149645, 283787919360, 9098660462034, 315866083233792, 11806916748046875, 472877960873902080, 20205339187128111480, 917543123840934346752, 44131536275846038655193

Offset: 1

N. J. A. Sloane, Jan 15 2000

Number of connected unicyclic simple graphs on n labeled nodes such that the unique cycle has length 3. - Len Smiley, Nov 27 2001

Each simple graph (of this type) corresponds to exactly two 'functional digraphs' counted by A065513.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Prop. 5.3.2.

Vincenzo Librandi, Table of n, a(n) for n = 1..100

Cf. A000169, A053506, A053508, A053509, A081133, A081132.

Equals 2*A065513. A diagonal of A081130.

List([1..20], n-> Binomial(n-1,2)*n^(n-3)); # G. C. Greubel, May 15 2019

[Binomial(n-1,2)*n^(n-3):n in [1..20]]; // Vincenzo Librandi, Sep 22 2011

[Binomial(n-1,2)*n^(n-3): n in [1..20]]; // G. C. Greubel, May 15 2019

nn = 20; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; Rest[Range[0, nn]! CoefficientList[Series[t^3/3!, {x, 0, nn}], x]] (* Geoffrey Critzer, Jan 22 2012 *)
Table[Binomial[n-1,2]n^(n-3),{n,20}] (* Harvey P. Dale, Sep 24 2019 *)

vector(20, n, binomial(n-1,2)*n^(n-3)) \\ G. C. Greubel, Jan 18 2017

[binomial(n-1,2)*n^(n-3) for n in (1..20)] # G. C. Greubel, May 15 2019

E.g.f.: -LambertW(-x)^3/3!. - Vladeta Jovovic, Apr 07 2001

A061356 Triangle read by rows: T(n, k) is the number of labeled trees on n nodes with maximal node degree k (0 < k < n).

Original entry on oeis.org

1, 2, 1, 9, 6, 1, 64, 48, 12, 1, 625, 500, 150, 20, 1, 7776, 6480, 2160, 360, 30, 1, 117649, 100842, 36015, 6860, 735, 42, 1, 2097152, 1835008, 688128, 143360, 17920, 1344, 56, 1, 43046721, 38263752, 14880348, 3306744, 459270, 40824, 2268, 72, 1

Offset: 2

Olivier Gérard, Jun 07 2001

Essentially the coefficients of the Abel polynomials (A137452). - Peter Luschny, Jun 12 2022
This is a formula from Comtet, Theorem F, vol. I, p. 81 (French edition) used in proving Theorem D.
If we let N = n+1, binomial(N-2, k-1)*(N-1)^(N-k-1) = binomial(n-1, k-1)*n^(n-k), so this sequence with offset 1,1 also gives the number of rooted forests of k trees over [n]. - Washington Bomfim, Jan 09 2008
Let S(n,k) be the signed triangle, S(n,k) = (-1)^(n-k)T(n,k), which starts 1, -2, 1, 9, -6, 1, ..., then the inverse of S is the triangle of idempotent numbers A059298. - Peter Luschny, Mar 13 2009
With offset 1 also number of labeled multigraphs of k components, n nodes, and no cycles except one loop in each component. See link below to have a picture showing the bijection between rooted forests and multigraphs of this kind. (Note that there are no labels in the picture, but the bijection remains true if we label the nodes.) - Washington Bomfim, Sep 04 2010
With offset 1, T(n,k) is the number of forests of rooted trees on n nodes with exactly k (rooted) trees. - Geoffrey Critzer, Feb 10 2012
Also the Bell transform of the sequence (n+1)^n (A000169(n+1)) without column 0. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 21 2016
Abel polynomials A(n,x) = x*(x+n)^(n-1) satisfy d/dx A(n,x) = n*A(n-1,x+1). - Michael Somos, May 10 2024
Also, T(n,k) is the number of parking functions with k ties. - Kyle Celano, Aug 18 2025

			Triangle begins
    1;
    2,     1;
    9,     6,     1;
   64,    48,    12,    1;
  625,   500,   150,   20,    1;
 7776,  6480,  2160,  360,   30,    1;
 ...
From _Peter Bala_, Sep 21 2012: (Start)
O.g.f.'s for the diagonals begin:
1/(1-x) = 1 + x + x^2 + x^3 + ...
2*x/(1-x)^3 = 2 + 6*x + 12*x^3 + ... A002378(n+1)
(9+3*x)/(1-x)^5 = 9 + 48*x + 150*x^2 + ... 3*A004320(n+1)
The numerator polynomials are the row polynomials of A155163.
(End)

L. Comtet, Analyse Combinatoire, P.U.F., Paris 1970. Volume 1, p 81.
L. Comtet, Advanced Combinatorics, Reidel, 1974.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
A. Avron and N. Dershowitz, Cayley's Formula, A Page From The Book, Amer. Math. Monthly, Vol. 123, No. 7, Aug.-Sep. 2016, 699-700 (2).
Peter Bala, Diagonals of triangles with generating function exp(t*F(x))
W. Bomfim, Bijection between rooted forests and multigraphs without cycles except one loop in each connected component. [From _Washington Bomfim_, Sep 04 2010]
J. W. Moon, Another proof of Cayley's formula for counting trees, Amer. Math. Monthly, Vol. 70, No. 8, Oct. 1963, 846-847.
Jim Pitman, Coalescent Random Forests, Technical Report No. 457, Department of Statistics, University of California.
Jim Pitman, Coalescent Random Forests, Journal of Combinatorial Theory, Series A, Volume 85, Issue 2, February 1999, Pages 165-193.
Paul R. F. Schumacher, Descents in parking functions, J. Integer Seq., Vol. 21 (2018), Article 18.2.3.
Eric Weisstein's World of Mathematics, Abel Polynomial.
Wikipedia, Lambert W function
J. Zeng, A Ramanujan sequence that refines the Cayley formula for trees, Ramanujan J., 3(1999) 1, 45-54.

Variant of A137452.
Columns are A000169, A053506, A053507, A053508, A053509.
First diagonal is A002378.
Row sums give A000272.
Cf. A028421, A059297, A139526 (row reverse), A155163, A202017.

# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0,...) as column 0 to the triangle.
BellMatrix(n -> (n+1)^n, 12); # Peter Luschny, Jan 21 2016

nn = 7; t = Sum[n^(n - 1)  x^n/n!, {n, 1, nn}]; f[list_] := Select[list, # > 0 &]; Map[f, Drop[Range[0, nn]! CoefficientList[Series[Exp[y t], {x, 0, nn}], {x, y}], 1]] // Flatten  (* Geoffrey Critzer, Feb 10 2012 *)
T[n_, m_] := T[n, m] = Binomial[n, m]*Sum[m^k*T[n-m, k], {k, 1, n-m}]; T[n_, n_] = 1; Table[T[n, m], {n, 1, 9}, {m, 1, n}] // Flatten (* Jean-François Alcover, Mar 31 2015, after Vladimir Kruchinin *)
Table[Binomial[n - 2, k - 1]*(n - 1)^(n - k - 1), {n, 2, 12}, {k, 1, n - 1}] // Flatten (* G. C. Greubel, Nov 12 2017 *)
BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len-1}, {k, 0, len-1}]];
rows = 10;
M = BellMatrix[(# + 1)^#&, rows];
Table[M[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 23 2018, after Peter Luschny *)

create_list(binomial(n,k)*(n+1)^(n-k),n,0,20,k,0,n); /* Emanuele Munarini, Apr 01 2014 */

for(n=2,11, for(k=1,n-1, print1(binomial(n-2, k-1)*(n-1)^(n-k-1), ", "))) \\ G. C. Greubel, Nov 12 2017

# uses[bell_matrix from A264428]
# Adds (1,0,0,0,...) as column 0 to the triangle.
bell_matrix(lambda n: (n+1)^n, 12) # Peter Luschny, Jan 21 2016

T(n, k) = binomial(n-2, k-1)*(n-1)^(n-k-1).
E.g.f.: (-LambertW(-y)/y)^(x+1)/(1+LambertW(-y)). - Vladeta Jovovic
From Peter Bala, Sep 21 2012: (Start)
Let T(x) = Sum_{n >= 0} n^(n-1)*x^n/n! denote the tree function of A000169. E.g.f.: F(x,t) := exp(t*T(x)) - 1 = -1 + {T(x)/x}^t = t*x + t*(2 + t)*x^2/2! + t*(9 + 6*t + t^2)*x^3/3! + ....
The compositional inverse with respect to x of (1/t)*F(x,t) is the e.g.f. for a signed version of the row reverse of A028421.
The row generating polynomials are the Abel polynomials A(n,x) = x*(x+n)^(n-1) for n >= 1.
Define B(n,x) = x^n/(1+n*x)^(n+1) = (-1)^n*A(-n,-1/x) for n >= 1. The k-th column entries are the coefficients in the formal series expansion of x^k in terms of B(n,x). For example, Col. 1: x = B(1,x) + 2*B(2,x) + 9*B(3,x) + 64*B(4,x) + ..., Col. 2: x^2 = B(2,x) + 6*B(3,x) + 48*B(4,x) + 500*B(5,x) + ... Compare with A059297.
n-th row sum = A000272(n+1).
Row reverse triangle is A139526.
The o.g.f.'s for the diagonals of the triangle are the rational functions R(n,x)/(1-x)^(2*n+1), where R(n,x) are the row polynomials of A155163. See below for examples.
(End)
T(n,m) = C(n,m)*Sum_{k=1..n-m} m^k*T(n-m,k), T(n,n) = 1. - Vladimir Kruchinin, Mar 31 2015

A368951 Number of connected labeled graphs with n edges and n vertices and with loops allowed.

Original entry on oeis.org

1, 1, 2, 10, 79, 847, 11436, 185944, 3533720, 76826061, 1880107840, 51139278646, 1530376944768, 49965900317755, 1767387701671424, 67325805434672100, 2747849045156064256, 119626103584870552921, 5533218319763109888000, 270982462739224265922466

Offset: 0

Andrew Howroyd, Jan 10 2024

nonn

Exponential transform appears to be A333331. - Gus Wiseman, Feb 12 2024

			From _Gus Wiseman_, Feb 12 2024: (Start)
The a(0) = 1 through a(3) = 10 loop-graphs:
  {}  {11}  {11,12}  {11,12,13}
            {22,12}  {11,12,23}
                     {11,13,23}
                     {22,12,13}
                     {22,12,23}
                     {22,13,23}
                     {33,12,13}
                     {33,12,23}
                     {33,13,23}
                     {12,13,23}
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Graph Loop.

Cf. A000169, A333331, A063170, A053506.
This is the connected covering case of A014068.
The case without loops is A057500, covering case of A370317.
Allowing any number of edges gives A062740, connected case of A322661.
This is the connected case of A368597.
The unlabeled version is A368983, connected case of A368984.
For at most n edges we have A369197.
A000085 counts set partitions into singletons or pairs.
A006129 counts covering graphs, connected A001187.
Cf. A000272, A000666, A054780, A116508, A136556, A367863, A368600.

egf:= (L-> 1-L/2-log(1+L)/2-L^2/4)(LambertW(-x)):
a:= n-> n!*coeff(series(egf, x, n+1), x, n):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 10 2024

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(-log(1-t)/2 + t/2 - t^2/4 + 1))}

a(n) = A000169(n) + A057500(n) for n > 0.
E.g.f.: 1 - log(1-T(x))/2 + T(x)/2 - T(x)^2/4 where T(x) = -LambertW(-x) is the e.g.f. of A000169.
From Peter Luschny, Jan 10 2024: (Start)
a(n) = (exp(n)*Gamma(n + 1, n) - (n - 1)*n^(n - 1))/(2*n) for n > 0.
a(n) = (1/2)*(A063170(n)/n - A053506(n)) for n > 0.  (End)

A055858 Coefficient triangle for certain polynomials.

Original entry on oeis.org

1, 1, 2, 4, 9, 6, 27, 64, 48, 36, 256, 625, 500, 400, 320, 3125, 7776, 6480, 5400, 4500, 3750, 46656, 117649, 100842, 86436, 74088, 63504, 54432, 823543, 2097152, 1835008, 1605632, 1404928, 1229312, 1075648, 941192, 16777216, 43046721

Offset: 0

Wolfdieter Lang, Jun 20 2000

The coefficients of the partner polynomials are found in triangle A055864.

			{1}; {1,2}; {4,9,6}; {27,64,48,36}; ...
Fourth row polynomial (n=3): p(3,x) = 27 + 64*x + 48*x^2 + 36*x^3.

Column sequences are A000312(n), n >= 1, A055860 (A000169), A055861 (A053506), A055862-3 for m=0..4, row sums: A045531(n+1)= |A039621(n+1, 2)|, n >= 0.

a[n_, m_] /; n < m = 0; a[0, 0] = 1; a[n_, 0] := n^n; a[n_, m_] := n^(m-1)*(n+1)^(n-m+1); Table[a[n, m], {n, 0, 8}, {m, 0, n}] // Flatten (* Jean-François Alcover, Jun 20 2013 *)

a(n, m)=0 if n < m; a(0, 0)=1, a(n, 0) = n^n, n >= 1, a(n, m) = n^(m-1)*(n+1)^(n-m+1), n >= m >= 1;

E.g.f. for column m: A(m, x); A(0, x) = 1/(1+W(-x)); A(1, x) = -1 - (d/dx)W(-x) = -1-W(-x)/((1+W(-x))*x); A(2, x) = A(1, x)-int(A(1, x), x)/x-(1/x+x); recursion: A(m, x) = A(m-1, x)-int(A(m-1, x), x)/x-((m-1)^(m-1))*(x^(m-1))/(m-1)!, m >= 3; W(x) principal branch of Lambert's function.

A303831 Birooted graphs: number of unlabeled connected graphs with n nodes rooted at 2 indistinguishable roots.

Original entry on oeis.org

0, 1, 3, 16, 98, 879, 11260, 230505, 7949596, 483572280, 53011686200, 10589943940654, 3880959679322754, 2623201177625659987, 3286005731275218388682, 7663042204550840483139108, 33407704152242477510352455230, 273327599183687887638526170380380

Offset: 1

Brendan McKay, May 01 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..40
Jean-François Alcover, Mathematica program

Cf. A303829 (not necessarily connected). 3rd column of A304311.

Cf. A000088 (not rooted), A126100 (connected single root), A053506 (2 roots adjacent).

Mathematica
```
(* See the links section. *)
```

G.f.: B(x)/G(x) - (C(x^2) + C(x)^2)/2 where B(x) is the g.f. of A303829, G(x) is the g.f. of A000088 and C(x) is the g.f. of A126100. - Andrew Howroyd, May 03 2018

a(n) = A303830(n) + A304071(n). - Brendan McKay, May 05 2018

a(12)-a(18) from Andrew Howroyd, May 03 2018

A195242 Expansion of Sum_{n>=0} n^nx^n/(1 - nx)^n.

Original entry on oeis.org

1, 1, 5, 44, 548, 8808, 173352, 4036288, 108507968, 3307368320, 112703108480, 4245680193024, 175200825481728, 7859411394860032, 380810598813553664, 19819617775693512704, 1102737068471914938368, 65316500202537025634304, 4103422475123595857854464

Offset: 0

Paul D. Hanna, Sep 13 2011

nonn

Compare g.f. to the identity (cf. A001710):

Sum_{n>=0} n^n*x^n/(1 + n*x)^n = 1 + (1/2)*Sum_{n>=1} (n+1)!*x^n.

			G.f.: A(x) = 1 + x + 5*x^2 + 44*x^3 + 548*x^4 + 8808*x^5 + 173352*x^6 +...
where
A(x) = 1 + x/(1-x) + 2^2*x^2/(1-2*x)^2 + 3^3*x^3/(1-3*x)^3 + 4^4*x^4/(1-4*x)^4 +...

Seiichi Manyama, Table of n, a(n) for n = 0..371

Cf. A001710, A053506, A242449.

a[n_] := Sum[Binomial[n - 1, k] (k + 1)^n, {k, 0, n}];
Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Jun 26 2019 *)

{a(n)=polcoeff(sum(m=0,n,m^m*x^m/(1-m*x+x*O(x^n))^m),n)}

{a(n)=sum(k=0,n,binomial(n-1,k)*(k+1)^n)}

{a(n)=(n+1)!/2 + 2*sum(k=0,n\2,binomial(n-1,n-2*k)*(n-2*k+1)^n)}

a(n) = Sum_{k=0..n} C(n-1,k)*(k+1)^n.
a(n) = (n+1)!/2 + 2*Sum_{k=0..[n/2]} C(n-1,n-2*k)*(n-2*k+1)^n for n>0 with a(0)=1.
a(n) ~ n^n * r^(n+3/2) / (exp(n) * (1-r)^n), where r = 1/(1+LambertW(exp(-1))) = 0.78218829428019990122... . - Vaclav Kotesovec, May 14 2014
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(-k,-n)*k^n. Cf. A053506. - Peter Luschny, Apr 11 2016

A083483 Number of forests with two connected components in the complete graph K_{n}.

Original entry on oeis.org

0, 1, 3, 15, 110, 1080, 13377, 200704, 3542940, 72000000, 1656409535, 42568187904, 1208912928522, 37603105146880, 1271514111328125, 46443371157258240, 1822442358054692408, 76461926986744528896, 3415753581721829617275

Offset: 1

Woong Kook (andrewk(AT)math.uri.edu), Jun 08 2003

nonn

Note that the above sequence is dominated by the sequence n^{n-2} (n > 0), A000272, which enumerates the number of spanning trees in K_{n} : 1, 1, 3, 16, 125, 1296, 16807, 262144, ... This is a consequence of the result in [EKT] which shows that the sequence of independent set numbers of cycle matroid of K_{n} is (strictly) monotone increasing (when n > 3).

W. Kook, Categories of acyclic graphs and automorphisms of free groups, Ph.D. thesis (G. Carlsson, advisor), Stanford University, 1996.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
N. Eaton, W. Kook, and L. Thoma, Monotonicity for complete graphs, preprint
A. Kassel, R. Kenyon, and W. Wu, Random two-component spanning forests, Ann. Inst. H. Poincaré Probab. Statist., 51 (2015), 1457-1464.
C. J. Liu and Yutze Chow, On operator and formal sum methods for graph enumeration problems, SIAM J. Algebraic Discrete Methods, 5 (1984), no. 3, 384--406. MR0752043 (86d:05059). See Eq. (47). - From _N. J. A. Sloane_, Apr 09 2014

Cf. A000272, A053506, A239910.

Column m=2 of A105599. A diagonal of A138464. - Alois P. Heinz, Apr 10 2014

[n^(n-4)*(n-1)*(n+6)/2 : n in [1..20]]; // Vincenzo Librandi, Apr 10 2014

f:=n->(n-1)!*n^(n-4)*(n+6)/(2*(n-2)!); [seq(f(n),n=2..30)]; # N. J. A. Sloane, Apr 09 2014

(* first 20 terms starting with n=1 *) T := Sum[i^(i - 2)*(x^i)/i!, {i, 1, 20}]; T2 := Expand[(T^{2})/2! ]; C2[i_] := Coefficient[T2, x^{i}]*i!; M := MatrixForm[Table[C2[i], {i, 20}]]; M
Table[n^(n - 4) (n - 1) (n + 6)/2, {n, 1, 40}] (* Vincenzo Librandi, Apr 10 2014 *)

for(n=1,30, print1(n^(n-4)*(n-1)*(n+6)/2, ", ")) \\ G. C. Greubel, Nov 14 2017

E.g.f.: T(x)^{2}/2!, where T(x) is the e.g.f. for the number of spanning trees in K_{n}, i.e., T(x) = Sum_{i>=1} i^(i-2)*x^i/i!.
E.g.f.: (1/8)*LambertW(-x)^2*(2+LambertW(-x))^2. - Vladeta Jovovic, Jul 08 2003
a(n) = n^(n-4)*(n-1)*(n+6)/2. - Vaclav Kotesovec, Oct 18 2013

Edited by N. J. A. Sloane, Apr 09 2014

cp's OEIS Frontend

A055861 Essentially A053506 but with leading 0 (instead of 1) and offset 0.

Views

Author

Keywords

Crossrefs

Formula

A000169 Number of labeled rooted trees with n nodes: n^(n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

Python

Python

Formula

A049363 a(1) = 1; for n > 1, smallest digitally balanced number in base n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A053507 a(n) = binomial(n-1,2)*n^(n-3).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Magma

Mathematica

PARI

Sage

Formula

A061356 Triangle read by rows: T(n, k) is the number of labeled trees on n nodes with maximal node degree k (0 < k < n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Sage

Formula

A368951 Number of connected labeled graphs with n edges and n vertices and with loops allowed.

Views

Author

Keywords

Comments

A195242 Expansion of Sum_{n>=0} n^nx^n/(1 - nx)^n.