A060226 -id:A060226 - cp's OEIS frontend

A055897 a(n) = n*(n-1)^(n-1).

1, 2, 12, 108, 1280, 18750, 326592, 6588344, 150994944, 3874204890, 110000000000, 3423740047332, 115909305827328, 4240251492291542, 166680102383370240, 7006302246093750000, 313594649253062377472, 14890324713954061755186, 747581753430634213933056

Offset: 1

Christian G. Bower, Jun 12 2000

nonn

Total number of leaves in all labeled rooted trees with n nodes.
Number of endofunctions of [n] such that no element of [n-1] is fixed. E.g., a(3)=12: 123 -> 331, 332, 333, 311, 312, 313, 231, 232, 233, 211, 212, 213.
Number of functions f: {1, 2, ..., n} --> {1, 2, ..., n} such that f(1) != f(2), f(2) != f(3), ..., f(n-1) != f(n). - Warut Roonguthai, May 06 2006
Determinant of the n X n matrix ((2n, n^2, 0, ..., 0), (1, 2n, n^2, 0, ..., 0), (0, 1, 2n, n^2, 0, ..., 0), ..., (0, ..., 0, 1, 2n)). - Michel Lagneau, May 04 2010
For n > 1: a(n) = A240993(n-1) / A240993(n-2). - Reinhard Zumkeller, Aug 31 2014
Total number of points m such that f^(-1)(m) = {m}, (i.e., the preimage of m is the singleton set {m}) summed over all functions f:[n]->[n]. - Geoffrey Critzer, Jan 20 2022

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Frank Ellermann, Illustration of binomial transforms
Index entries for sequences related to rooted trees

Cf. A003227, A003228, A055314, A055540, A055541, A060226, A118537.

Cf. A240993. Diagonal of A265583.

List([1..20], n-> n*(n-1)^(n-1)); # G. C. Greubel, Aug 10 2019

a055897 n = n * (n - 1) ^ (n - 1) -- Reinhard Zumkeller, Aug 31 2014

[n*(n-1)^(n-1): n in [1..20]] // Wesley Ivan Hurt, Jun 26 2014

A055897:=n->`if`(n=1,1,n*(n-1)^(n-1)); seq(A055897(n), n=1..20); # Wesley Ivan Hurt, Jun 26 2014

Join[{1},Table[n(n-1)^(n-1), {n,2,20}]] (* Harvey P. Dale, Jul 18 2011 *)

{a(n)=polcoeff(1/(1-n*x+x*O(x^n))^2, n)} \\ Paul D. Hanna, Dec 27 2012

[n*(n-1)^(n-1) for n in (1..20)] # G. C. Greubel, Aug 10 2019

E.g.f.: x/(1-T), where T=T(x) is Euler's tree function (see A000169).
a(n) = Sum_{k=1..n} A055302(n, k)*k.
a(n) = the n-th term of the (n-1)-th binomial transform of {1, 1, 4, 18, 96, ..., (n-1)*(n-1)!, ...} (cf. A001563). - Paul D. Hanna, Nov 17 2003
a(n) = (n-1)^(n-1) + Sum_{i=2..n} (n-1)^(n-i)*binomial(n-1, i-1)*(i-1) *(i-1)!. - Paul D. Hanna, Nov 17 2003
a(n) = [x^(n-1)] 1/(1 - (n-1)*x)^2. - Paul D. Hanna, Dec 27 2012
a(n) ~ exp(-1) * n^n. - Vaclav Kotesovec, Nov 14 2014

Additional comments from Vladeta Jovovic, Mar 31 2001 and Len Smiley, Dec 11 2001

A185390 Triangular array read by rows. T(n,k) is the number of partial functions on n labeled objects in which the domain of definition contains exactly k elements such that for all i in {1,2,3,...}, (f^i)(x) is defined.

Original entry on oeis.org

1, 1, 1, 3, 2, 4, 16, 9, 12, 27, 125, 64, 72, 108, 256, 1296, 625, 640, 810, 1280, 3125, 16807, 7776, 7500, 8640, 11520, 18750, 46656, 262144, 117649, 108864, 118125, 143360, 196875, 326592, 823543, 4782969, 2097152, 1882384, 1959552, 2240000, 2800000, 3919104, 6588344, 16777216

Offset: 0

Geoffrey Critzer, Feb 09 2012

Here, for any x in the domain of definition (f^i)(x) denotes the i-fold composition of f with itself, e.g., (f^2)(x) = f(f(x)). The domain of definition is the set of all values x for which f(x) is defined.
T(n,n) = n^n, the partial functions that are total functions.
T(n,0) = A000272(offset), see comment and link by Dennis P. Walsh.

			Triangle begins:
      1;
      1,     1;
      3,     2,     4;
     16,     9,    12,    27;
    125,    64,    72,   108,   256;
   1296,   625,   640,   810,  1280,  3125;
  16807,  7776,  7500,  8640, 11520, 18750, 46656;
  ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Geoffrey Critzer, Distribution of non-functional points under a random partial function
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 132, II.21.

Row sums give A000169(n+1).
T(n,n-1) gives A055897(n).
T(n,n)-T(n,n-1) gives A060226(n).
Cf. A000272, A000312, A185391.

T(n, k) = binomial(n, k)*k^k*(n-k+1)^(n-k-1)
for n in 0:9 (println([T(n, k) for k in 0:n])) end
# Peter Luschny, Jan 12 2024

T:= (n, k)-> binomial(n,k)*k^k*(n-k+1)^(n-k-1):
seq(seq(T(n,k), k=0..n), n=0..10);  # Alois P. Heinz, Jan 12 2024

nn = 7; tx = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; txy = Sum[n^(n - 1) (x y)^n/n!, {n, 1, nn}]; f[list_] := Select[list, # > 0 &]; Map[f, Range[0, nn]! CoefficientList[Series[Exp[tx]/(1 - txy), {x, 0, nn}], {x, y}]] // Flatten

E.g.f.: exp(T(x))/(1-T(x*y)) where T(x) is the e.g.f. for A000169.
T(n,k) = binomial(n,k)*k^k*(n-k+1)^(n-k-1). - Geoffrey Critzer, Feb 28 2022
Sum_{k=0..n} k * T(n,k) = A185391(n). - Alois P. Heinz, Jan 12 2024

A132431 For n>0, let B_n be the subsemigroup of the full transformation monoid on the n-set [n] generated by the following functions: Let x be a certain element in [n]. Now the generators of B are those functions which map either x to any distinct element y in [n] leaving all the other elements fixed, or y to x leaving all the other elements fixed. Then a(n) = number of elements in B_n.

Original entry on oeis.org

0, 2, 9, 88, 1385, 24336, 466753, 9906688, 233522577, 6093136000, 174912502721, 5487091383456, 186891076515481, 6870622015481056, 271195480556337345, 11440127985767481856, 513639921634424850977, 24455974520989478444544, 1230835712617872016215265

Offset: 1

Simon Bogner (sisibogn(AT)stud.informatik.uni-erlangen.de), Nov 20 2007

Let b(n)=n^n be the cardinality of the full transformation monoid. The sequence of quotients a(n)/b(n) converges to 1-1/e.

S. Bogner, Eine Praesentation der Halbgruppe der singularen zyklisch-monotonen Abbildungen UND eine von Idempotenten erzeugte Unterhalbgruppe von T_n (Studienarbeit in Informatik, Advisor: Klaus Leeb), Friedrich-Alexander-Universitaet Erlangen-Nuernberg, 2007.

Reinhard Zumkeller, Table of n, a(n) for n = 1..250

Cf. A000312, A060226.

a132431 n = a060226 n - a062119 n + a002378 (n - 1)
-- Reinhard Zumkeller, Aug 27 2012

Join[{0},Table[n^n-n (n-1)^(n-1)-(n-1)n!+n(n-1),{n,2,20}]] (* Harvey P. Dale, Jun 07 2018 *)

a(n) = n^n - n*(n-1)^(n-1) - (n-1)*n! + n*(n-1).
a(n) = n*(n-1) + Sum_{k=1..n-2} k*Stirling2(n-1,k)*k!*C(n,k).
a(n) = A060226(n) - A062119(n) + A002378(n-1). - Reinhard Zumkeller, Aug 27 2012

cp's OEIS Frontend

A055897 a(n) = n*(n-1)^(n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A185390 Triangular array read by rows. T(n,k) is the number of partial functions on n labeled objects in which the domain of definition contains exactly k elements such that for all i in {1,2,3,...}, (f^i)(x) is defined.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Maple

Mathematica

Formula

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula