A053507 -id:A053507 - cp's OEIS frontend

A053506 a(n) = (n-1)*n^(n-2).

0, 1, 6, 48, 500, 6480, 100842, 1835008, 38263752, 900000000, 23579476910, 681091006464, 21505924728444, 737020860878848, 27246730957031250, 1080863910568919040, 45798768824157052688, 2064472028642102280192, 98646963440126439346902, 4980736000000000000000000

Offset: 1

N. J. A. Sloane, Jan 15 2000

nonn

a(n) is the number of endofunctions f of [n] which interchange a pair a<->b and for all x in [n] some iterate f^k(x) = a. E.g., a(3) = 6: 1<->2<-3; 3->1<->2; 2<->3<-1; 1->2<->3; 1<->3<-2; 2->1<->3. - Len Smiley, Nov 27 2001
If offset is 0: right side of the binomial sum n-> sum( i^(i-1) * (n-i+1)^(n-i)*binomial(n, i), i=1..n) - Yong Kong (ykong(AT)curagen.com), Dec 28 2000
a(n) is the number of birooted labeled trees on n nodes in which the two root nodes are adjacent. - N. J. A. Sloane, May 01 2018
a(n) is the number of ways to partition the complete graph K_n into two components and choose an arborescence on each component. - Harry Richman, May 11 2022

A. P. Prudnikov, Yu. A. Brychkov and O. I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.2.36)
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Prop. 5.3.2.

G. C. Greubel, Table of n, a(n) for n = 1..250
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Eric Weisstein's World of Mathematics, Graph Edge

Cf. A000169, A000312, A053507, A053508, A053509, A083483, A195242.

Cf. A001865 which is the sum of A000169 + A053506 + A065513 + A065888 + ...

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

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

Mathematica
```
Table[(n-1)*n^(n-2), {n,20}]
```

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

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

E.g.f.: LambertW(-x)^2/2. - Vladeta Jovovic, Apr 07 2001
E.g.f. if offset 0: W(-x)^2/((1+W(-x))*x), W(x) Lambert's function (principal branch).
The sequence 1, 1, 6, 48, ... satisfies a(n) = (n*(n+1)^n + 0^n)/(n+1); it is the main diagonal of A085388. - Paul Barry, Jun 30 2003
a(n) = Sum_{i=1..n-1} binomial(n-1,i-1)*i^(i-2)*(n-i)^(n-i). - Dmitry Kruchinin, Oct 28 2013
If offset = 0 and a(0) = 1 then a(n) = Sum_{k=0..n} (-1)^(n-k)* binomial(-k,-n)*n^k (cf. A195242). - Peter Luschny, Apr 11 2016

A081131 a(n) = n^(n-2) * binomial(n,2).

Original entry on oeis.org

0, 0, 1, 9, 96, 1250, 19440, 352947, 7340032, 172186884, 4500000000, 129687123005, 4086546038784, 139788510734886, 5159146026151936, 204350482177734375, 8646911284551352320, 389289535005334947848, 18580248257778920521728, 937146152681201173795569

Offset: 0

Paul Barry, Mar 08 2003

Main diagonal of A081130.
a(n) is the number of partial functions f: {1,2,...,n} -> {1,2,...,n} that have exactly 2 undefined elements. - Geoffrey Critzer, Feb 08 2012
a(n+1) is the determinant of the circulant matrix having (n-1, n-2, ..., 0) as first row, for n >= 1. See A070896 for a variant, and A303260 for a related sequence. - M. F. Hasler, Apr 23 2018
a(n) is the number of birooted labeled trees on n nodes. - Brendan McKay, May 01 2018

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A070896, A081129, A081130, A303260.

Sequences of the form (n+m)^n*binomial(n+2,2): A081133 (m=0), A081132 (m=1), this sequence (m=2), A053507 (m=3), A081196 (m=4).

[n lt 2 select 0 else n^(n-2)*Binomial(n,2): n in [0..20]]; // G. C. Greubel, May 18 2021

Join[{0},Table[n^(n-2) Binomial[n, 2], {n, 1, 20}]] (* Vladimir Joseph Stephan Orlovsky, Apr 19 2011 *)

[0 if (n<2) else n^(n-2)*binomial(n,2) for n in (0..20)] # G. C. Greubel, May 18 2021

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

E.g.f.: T(x)^2/(2*(1-T(x))) where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Feb 08 2012

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

A081132 a(n) = (n+1)^n*binomial(n+2,2).

Original entry on oeis.org

1, 6, 54, 640, 9375, 163296, 3294172, 75497472, 1937102445, 55000000000, 1711870023666, 57954652913664, 2120125746145771, 83340051191685120, 3503151123046875000, 156797324626531188736, 7445162356977030877593

Offset: 0

Paul Barry, Mar 08 2003

A diagonal of A081130.

a(n) is the sum of all the fixed points in the set of endofunctions on {1,2,...,n+1}, i.e., the functions f:{1,2,...,n+1} -> {1,2,...,n+1}. - Geoffrey Critzer, Sep 17 2011

			a(1) = 6 because there are four functions from {1,2} into {1,2}: (1*,1) (1*,2*) (2,1) (2,2*) and the fixed points (marked *) sum to 6.

Vincenzo Librandi, Table of n, a(n) for n = 0..300

Sequences of the form (n+m)^n*binomial(n+2,2): A081133 (m=0), this sequence (m=1), A081131 (m=2), A053507 (m=3), A081196 (m=4).

[((n+1)^n*Binomial(n+2,2)): n in [0..20]]; // Vincenzo Librandi, Sep 21 2011

seq((n+1)^n*binomial(n+2,2), n=0..20); # G. C. Greubel, May 18 2021

Mathematica
```
Table[n^n*(n+1)/2,{n,20}]
```

[(n+1)^n*binomial(n+2,2) for n in (0..20)] # G. C. Greubel, May 18 2021

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

A081133 a(n) = n^n*binomial(n+2, 2).

Original entry on oeis.org

1, 3, 24, 270, 3840, 65625, 1306368, 29647548, 754974720, 21308126895, 660000000000, 22254310307658, 811365140791296, 31801886192186565, 1333440819066961920, 59553569091796875000, 2822351843277561397248

Offset: 0

Paul Barry, Mar 08 2003

A diagonal of A081130.

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

Sequences of the form (n+m)^n*binomial(n+2,2): this sequence (m=0), A081132 (m=1), A081131 (m=2), A053507 (m=3), A081196 (m=4).

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

seq(n^n*binomial(n+2,2), n=0..20); # G. C. Greubel, May 18 2021

Join[{1},Table[n^n Binomial[n+2,2],{n,20}]] (* Harvey P. Dale, Dec 27 2011 *)

[n^n*binomial(n+2,2) for n in (0..20)] # G. C. Greubel, May 18 2021

a(n) = n^n*(n+1)*(n+2)/2.

A053508 a(n) = binomial(n-1,3)*n^(n-4).

Original entry on oeis.org

0, 0, 0, 1, 20, 360, 6860, 143360, 3306744, 84000000, 2338460520, 70946979840, 2332989862060, 82726831323136, 3148511132812500, 128071114403348480, 5546563698427324720, 254873089955815096320, 12387799656377835411984, 635043840000000000000000

Offset: 1

N. J. A. Sloane, Jan 15 2000

nonn

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

G. C. Greubel, Table of n, a(n) for n = 1..250

Cf. A000169, A053506, A053507, A053509.

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

[Binomial(n-1,3)*n^(n-4): n in [1..25]]; // G. C. Greubel, Nov 14 2017

Table[Binomial[n-1,3]n^(n-4),{n,25}] (* Harvey P. Dale, Jun 17 2014 *)
With[{nmax = 25}, CoefficientList[Series[LambertW[-x]^4/4!, {x, 0, nmax}], x]*Range[0, nmax]!] (* G. C. Greubel, Nov 14 2017 *)

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

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

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

A053509 a(n) = binomial(n-1,4)*n^(n-5).

Original entry on oeis.org

0, 0, 0, 0, 1, 30, 735, 17920, 459270, 12600000, 372027810, 11824496640, 403786706895, 14772648450560, 577227041015625, 24013333950627840, 1060372471758165020, 49558656380297379840, 2444960458495625410260, 127008768000000000000000

Offset: 1

N. J. A. Sloane, Jan 15 2000

nonn

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

G. C. Greubel, Table of n, a(n) for n = 1..250

Cf. A000169, A053506, A053507, A053508.

List([1..25], n-> Binomial(n-1,4)*n^(n-5)) # G. C. Greubel, May 15 2019

[Binomial(n-1,4)*n^(n-5): n in [1..30]]; // G. C. Greubel, Nov 14 2017

Table[Binomial[n-1,4]*n^(n-5), {n,1,25}] (* G. C. Greubel, Jan 18 2017 *)

vector(25, n, binomial(n-1,4)*n^(n-5)) \\ G. C. Greubel, Jan 18 2017

[binomial(n-1,4)*n^(n-5) for n in (1..25)] # G. C. Greubel, May 15 2019

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

A065513 Number of endofunctions of [n] with a cycle a->b->c->a and for all x in [n], some iterate f^k(x)=a.

Original entry on oeis.org

2, 24, 300, 4320, 72030, 1376256, 29760696, 720000000, 19292299290, 567575838720, 18197320924068, 631732166467584, 23613833496093750, 945755921747804160, 40410678374256222960, 1835086247681868693504, 88263072551692077310386, 4482662400000000000000000

Offset: 3

Len Smiley, Nov 27 2001

nonn

			a(4)=24: 1->2->3->1<-4; 2->3->1->2<-4; 3->1->2->3<-4 1->3->2->1<-4; 3->2->1->3<-4; 2->1->3->2<-4 (repeat with 1,2, then 3 excluded from cycle)

Alois P. Heinz, Table of n, a(n) for n = 3..150

Cf. A000169 (unique cycle is length 1), A053506 (unique cycle has length 2).

Column k=3 of A201685.

[(n-1)*(n-2)*n^(n-3): n in [3..50]]; // G. C. Greubel, Nov 14 2017

T := x->-LambertW(-x); a := []; f := series((T(x))^3/3,x,24); for m from 1 to 24 do a := [op(a),op(2*m-1,f)*(m+2)! ] od; print(a);

nn = 18; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}];
Range[0, nn]! CoefficientList[Series[2 t^3/3!, {x, 0, nn}], x] (* Geoffrey Critzer, Aug 14 2013 *)

for(n=3,50, print1((n-1)*(n-2)*n^(n-3), ", ")) \\ G. C. Greubel, Nov 14 2017

E.g.f.: T^3/3 where T=T(x) is Euler's tree function (see A000169).
a(n) = (n-1)*(n-2)*n^(n-3). - Vaclav Kotesovec, Oct 05 2013
a(n) = 2*A053507(n). - Vaclav Kotesovec, Oct 07 2016

A065889 a(n) = number of unicyclic connected simple graphs whose cycle has length 4.

Original entry on oeis.org

3, 60, 1080, 20580, 430080, 9920232, 252000000, 7015381560, 212840939520, 6998969586180, 248180493969408, 9445533398437500, 384213343210045440, 16639691095281974160, 764619269867445288960, 37163398969133506235952, 1905131520000000000000000

Offset: 4

Len Smiley, Nov 27 2001

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..150

A065888 ( = 2*A065889) counts sagittal graphs with one cycle (length 4).
A column of A098909, A053507.
Main diagonal of A144209.
Cf. A053508.

List([4..25], n-> 12*Binomial(n,4)*n^(n-5)); # G. C. Greubel, May 16 2019

[12*Binomial(n,4)*n^(n-5) : n in [4..25]]; // G. C. Greubel, May 16 2019

Table[12*Binomial[n,4]*n^(n-5), {n,4,25}] (* G. C. Greubel, May 16 2019 *)

{a(n) = 12*binomial(n,4)*n^(n-5)}; \\ G. C. Greubel, May 16 2019

[12*binomial(n,4)*n^(n-5) for n in (4..25)] # G. C. Greubel, May 16 2019

E.g.f.: T^4/8, where T = T(x) is Euler's tree function (see A000169).
a(n) = (n-1)*(n-2)*(n-3)*n^(n-4)/2. - Vladeta Jovovic, Oct 26 2004
a(n) = 3 * A053508(n). - Alois P. Heinz, Jan 09 2025

A081196 a(n) = (n+4)^n*binomial(n+2,2).

Original entry on oeis.org

1, 15, 216, 3430, 61440, 1240029, 28000000, 701538156, 19349176320, 583247465515, 19090807228416, 674680957031250, 25614222880669696, 1039980693455123385, 44977604109849722880, 2064633276062972568664

Offset: 0

Paul Barry, Mar 11 2003

Diagonal of A081130.

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Sequences of the form (n+m)^n*binomial(n+2,2): A081133 (m=0), A081132 (m=1), A081131 (m=2), A053507 (m=3), this sequence (m=4).

[(n+4)^n*Binomial(n+2,2): n in [0..20]]; // Vincenzo Librandi, Aug 07 2013

seq((n+4)^n*binomial(n+2,2), n=0..20); # G. C. Greubel, May 18 2021

Table[(n+4)^n Binomial[n+2, 2], {n, 0, 30}] (* Vincenzo Librandi, Aug 07 2013 *)

[(n+4)^n*binomial(n+2,2) for n in (0..20)] # G. C. Greubel, May 18 2021

a(n) = (n+4)^n*binomial(n+2,2).

cp's OEIS Frontend

A053506 a(n) = (n-1)*n^(n-2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A081131 a(n) = n^(n-2) * binomial(n,2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

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

A081132 a(n) = (n+1)^n*binomial(n+2,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

A081133 a(n) = n^n*binomial(n+2, 2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

A053508 a(n) = binomial(n-1,3)*n^(n-4).

Views

Author

Keywords

References

Links

Crossrefs

Programs

GAP