A001865 -id:A001865 - cp's OEIS frontend

A185391 a(n) = Sum_{k=0..n} A185390(n,k) * k.

0, 1, 10, 114, 1556, 25080, 468462, 9971920, 238551336, 6339784320, 185391061010, 5917263922944, 204735466350780, 7633925334590464, 305188474579874550, 13023103577435351040, 590850477768105474128, 28401410966866912051200, 1441935117039649859464986

Offset: 0

Geoffrey Critzer, Feb 09 2012

nonn

The total number of elements, x in the domain of definition of all partial functions on n labeled objects such that for all i in {1,2,3,...} (f^i)(x) is defined.

G. C. Greubel, Table of n, a(n) for n = 0..385

Cf. A000312, A001865, A076728, A185390.

nn=20; 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&];
  D[Range[0,nn]! CoefficientList[Series[Exp[tx]/(1-txy),{x,0,nn}],x],y]/.y->1

{a(n) = (n+1)^(n+1)-sum(k=1, n+1, binomial(n+1, k)*k^k*(n+1-k)^(n+1-k))/(n+1)} \\ Seiichi Manyama, Jun 01 2019

a(n) = (n+1)^(n+1) - A001865(n+1). - Seiichi Manyama, Jun 01 2019

A201685 Triangular array read by rows. T(n,k) is the number of connected endofunctions on {1,2,...,n} that have exactly k nodes in the unique cycle of its digraph representation.

Original entry on oeis.org

1, 2, 1, 9, 6, 2, 64, 48, 24, 6, 625, 500, 300, 120, 24, 7776, 6480, 4320, 2160, 720, 120, 117649, 100842, 72030, 41160, 17640, 5040, 720, 2097152, 1835008, 1376256, 860160, 430080, 161280, 40320, 5040, 43046721, 38263752, 29760696, 19840464, 11022480, 4898880, 1632960, 362880, 40320

Offset: 1

Geoffrey Critzer, Dec 03 2011

Column k=1: A000169,
Column k=2: A053506,
Column k=3: A065513.
Row sums:   A001865.
T(n,n) = (n-1)!, T(n,n-1) = n!.
Sum_{k=1..n} T(n,k)*k = n^n. - Geoffrey Critzer, May 13 2013
From the asymptotic given by N-E. Fahssi in A001865, we see the expected size of the cycle grows as (2*n/Pi)^(1/2). - Geoffrey Critzer, May 13 2013
Central terms: A277168. - Paul D. Hanna, Oct 01 2016

			Triangle begins as:
     1;
     2,    1;
     9,    6,    2;
    64,   48,   24,    6;
   625,  500,  300,  120,  24;
  7776, 6480, 4320, 2160, 720, 120;

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A000169, A001865, A053506, A065513, A277168.

Flat(List([1..12], n-> List([1..n], k-> Binomial(n-1,k-1)*n^(n-k)*Factorial(k-1) ))); # G. C. Greubel, Jan 08 2020

[Binomial(n-1,k-1)*n^(n-k)*Factorial(k-1): k in [1..n], n in [1..12]]; // G. C. Greubel, Jan 08 2020

T:= (n, k)-> binomial(n-1, k-1)*n^(n-k)*(k-1)!:
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Aug 14 2013

f[list_] := Select[list, # > 0 &]; t = Sum[n^(n - 1) x^n/n!, {n, 1, 20}]; Map[f, Drop[Range[0, 10]! CoefficientList[Series[Log[1/(1 - y t)], {x, 0, 10}], {x, y}], 1]] // Grid

T(n,k) = binomial(n-1,k-1)*n^(n-k)*(k-1)!; \\ G. C. Greubel, Jan 08 2020

[[binomial(n-1,k-1)*n^(n-k)*factorial(k-1) for k in (1..n)] for n in (1..12)] # G. C. Greubel, Jan 08 2020

E.g.f.: log(1/(1-y*A(x))) where A(x) is the e.g.f. for A000169.

T(n,k) = binomial(n-1,k-1)*n^(n-k)*(k-1)!. - Geoffrey Critzer, May 13 2013

A209327 Total number of nodes in the largest connected component of a functional digraph summed over all endofunctions f:{1,2,...,n}-> {1,2,...,n}.

Original entry on oeis.org

1, 7, 70, 863, 13056, 231187, 4737986, 109531991, 2835638008, 80950287311, 2533758258912, 86089196479255, 3161596017956936, 124590870125959343, 5251666647713483356, 235497961945975068767, 11205025852314462333408, 563351626162952600815087, 29864689571162209608920060, 1663796497123214306448307031

Offset: 1

Geoffrey Critzer, Jan 19 2013

nonn

a(n)/n^n is the average size of the largest component.

a(n)/n^(n + 1) is the probability that a particular node is in the largest component of the digraph.

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Welsey, 1996, Chapter 8.

Alois P. Heinz, Table of n, a(n) for n = 1..385

Cf. A001865, A209324, A350157.

g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, m) option remember; `if`(n=0, x^m, add(g(i)*
      b(n-i, max(m, i))*binomial(n-1, i-1), i=1..n))
    end:
a:= n-> (p-> add(coeff(p, x, i)*i, i=1..n))(b(n, 0)):
seq(a(n), n=1..20);  # Alois P. Heinz, Dec 17 2021

nn=20;g[list_]:= Sum[list[[i]]*i,{i,1,Length[list]}];t=Sum[n^(n-1)x^n/n!,{n,1,nn}];c=Log[1/(1-t)];b=Drop[Range[0,nn]!CoefficientList[Series[c,{x,0,nn}],x],1];f[list_]:=Select[list,#>0&];Map[g,Map[ f,Drop[Transpose[Table[Range[0,nn]!CoefficientList[Series[ Exp[Sum[b[[i]]x^i/i!,{i,1,n+1}]]-Exp[Sum[b[[i]]x^i/i!,{i,1,n}]],{x,0,nn}],x],{n,0,nn-1}]],1]]]

a(n) = Sum_{k=1..n} k * A209324(n,k).

A036360 a(n) = Sum_{k=1..n} n! * n^(n-k+1) / (n-k)!.

Original entry on oeis.org

0, 1, 12, 153, 2272, 39225, 776736, 17398969, 435538944, 12058401393, 366021568000, 12090393761721, 431832459644928, 16585599200808937, 681703972229640192, 29858718555221585625, 1388451967046195347456, 68316647610168842824161, 3546179063131198669848576, 193670918442059606406896473

Offset: 0

N. J. A. Sloane

This formula is given as a solution to Exercise 1.15a in the Harary and Palmer reference on page 30. However, the formula may not be correct and could be a misprint for Sum_{k=2..n} n! * n^(n-k-1) / (n-k)! which is a formula for A000435(n). - Andrew Howroyd, Feb 06 2024
It appears that a(n) * n^-(n+1) is the mean position of the first duplicate in sequences of n elements randomly drawn with replacement. - Brian P Hawkins, Jan 06 2024
Total count over all mappings from [n] to [n] of tail length plus cycle size of all nodes, where mappings are sets of cycles of trees and tail length is the distance to the cycle that eventually traps the iterates of a node of the mapping; cycle size is the size of that cycle. Alternatively, number of elements on the trajectory of iterates of a node until a repeat is seen, summed over all nodes and mappings. - Marko Riedel, Jul 20 2024

			Example: Consider the map [1,2,3,4] -> [2,3,4,4]. The trajectory of node one is [1,2,3,4]. Hence the tail length is three and the cycle size is one, a fixed point.

F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 30, Exercise 1.15a.
P. Flajolet and A. Odlyzko, Random Mapping Statistics, INRIA RR 1114.

N. J. A. Sloane, Table of n, a(n) for n = 0..100
Marko Riedel, Pusieux series of the tree function and random mapping statistics.

Cf. A000435, A001373, A007778, A262970.

a := proc(n) local k; add(n!*n^(n-k+1)/(n-k)!, k=0..n); end;
# Alternative, e.g.f.:
T := -LambertW(-x): egf := (T + T^2)/(1 - T)^4: ser := series(egf, x, 22):
seq(n!*coeff(ser, x, n), n = 0..19);  # Peter Luschny, Jul 20 2024

Table[Sum[n!*n^(n-k+1)/(n-k)!, {k, 1, n}], {n, 0, 19}] (* James C. McMahon, Feb 07 2024 *)
a[n_] := n E^n Gamma[n + 1, n] - n^(n + 1);
Table[a[n], {n, 0, 19}]  (* Peter Luschny, Jul 20 2024 *)

a(n) = sum(k=1, n, n! * n^(n-k+1) / (n-k)!) \\ Andrew Howroyd, Jan 06 2024

def a(n):
    total_sum = 0
    for k in range(1, n + 1):
        term = (math.factorial(n) / math.factorial(n - k))*(k**2)*(n**(n - k))
        total_sum += term
    return total_sum
# Brian P Hawkins, Jan 06 2024

a(n) = n^2 * A001865(n). - Gerald McGarvey, Apr 17 2008
a(n) = Sum_{k=1..n} n! * k^2 * n^(n-k) / (n-k)!. - Brian P Hawkins, Jan 06 2024
a(n) = n! * [z^n] (T+T^2)/(1-T)^4 where T is Cayley's tree function T(z) = Sum_{n >= 1} n^(n-1) * z^n/n!. - Marko Riedel, Jul 20 2024
a(n) ~ n^n * ((1/2) * n * sqrt(2 * Pi * n) - (1/3) * n) - Marko Riedel, Jul 20 2024
a(n) = n * e^n * Gamma(n + 1, n) - n^(n + 1) = 2*A262970(n) - A007778(n). - Peter Luschny, Jul 20 2024

Offset corrected by Brian P Hawkins, Jan 06 2024
Name edited by Andrew Howroyd, Feb 06 2024
Offset set to 0 and a(0) = 0 prepended by Marko Riedel, Jul 20 2024

A323673 Expansion of e.g.f. log(1 - LambertW(-x)*(2 + LambertW(-x))/2).

Original entry on oeis.org

0, 1, 0, 2, 7, 69, 696, 9400, 148506, 2753793, 58255840, 1388008566, 36768832200, 1072407094693, 34151921130432, 1179292944433500, 43892264744070736, 1751768399754149025, 74633720517351765504, 3380997879130123703818, 162286529338732345488000, 8227876237310253918100581

Offset: 0

Ilya Gutkovskiy, Jan 23 2019

nonn

Cf. A000272, A001858, A001865, A133297.

seq(n!*coeff(series(log(1-LambertW(-x)*(2+LambertW(-x))/2),x=0,22),x,n),n=0..21); # Paolo P. Lava, Jan 28 2019

nmax = 21; CoefficientList[Series[Log[1 - LambertW[-x] (2 + LambertW[-x])/2], {x, 0, nmax}], x] Range[0, nmax]!
a[n_] := a[n] = n^(n - 2) - Sum[Binomial[n, k] (n - k)^(n - k - 2) k a[k], {k, 1, n - 1}]/n; a[0] = 0; Table[a[n], {n, 0, 21}]

E.g.f.: log(1 + Sum_{k>=1} k^(k-2)*x^k/k!).
a(0) = 0; a(n) = A000272(n) - (1/n)*Sum_{k=1..n-1} binomial(n,k)*A000272(n-k)*k*a(k).
a(n) ~ 2 * n^(n-2) / 3. - Vaclav Kotesovec, Jan 24 2019

A348590 Number of endofunctions on [n] with exactly one isolated fixed point.

Original entry on oeis.org

0, 1, 0, 9, 68, 845, 12474, 218827, 4435864, 102030777, 2625176150, 74701061831, 2329237613988, 78972674630005, 2892636060014050, 113828236497224355, 4789121681108775344, 214528601554419809777, 10193616586275094959534, 512100888749268955942015

Offset: 0

Alois P. Heinz, Dec 20 2021

nonn

			a(3) = 9: 122, 133, 132, 121, 323, 321, 113, 223, 213.

Alois P. Heinz, Table of n, a(n) for n = 0..386

Column k=1 of A350212.

Cf. A000035, A000240, A001865, A250105.

g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, t) option remember; `if`(n=0, t, add(g(i)*
      b(n-i, `if`(i=1, 1, t))*binomial(n-1, i-1), i=1+t..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..23);

g[n_] := g[n] = Sum[n^(n - j)*(n - 1)!/(n - j)!, {j, 1, n}] ;
b[n_, t_] := b[n, t] = If[n == 0, t, Sum[g[i]*
     b[n - i, If[i == 1, 1, t]]*Binomial[n - 1, i - 1], {i, 1 + t, n}]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, May 16 2022, after Alois P. Heinz *)

a(n) mod 2 = A000035(n).

A350135 Number of endofunctions on [2n] whose smallest connected component has size n.

Original entry on oeis.org

1, 1, 27, 2890, 705740, 310181886, 215071984512, 216357598418676, 298018065222408960, 538758820820128412790, 1237604585414359892787200, 3521561770316172974098259916, 12159265179096745219044911480832, 50086112147669900240287215353718700, 242646275221231775443338250567758643200

Offset: 0

Alois P. Heinz, Dec 15 2021

nonn

a(0) = 1 by convention.

Number of endofunctions on [2n] with two connected components of size n.

			a(1) = 1: 12.

Alois P. Heinz, Table of n, a(n) for n = 0..193

Cf. A001865, A065456, A088218, A347999.

a:= n-> `if`(n=0, 1, add(n^(n-j)*(n-1)!/(n-j)!, j=1..n)^2*binomial(2*n, n)/2):
seq(a(n), n=0..14);

a(n) = A347999(2n,n).

a(n) = A001865(n)^2 * A088218(n) for n >= 1.

A350202 Number T(n,k) of nodes in the k-th connected component of all endofunctions on [n] when components are ordered by increasing size; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 7, 1, 61, 19, 1, 709, 277, 37, 1, 9911, 4841, 811, 61, 1, 167111, 91151, 19706, 1876, 91, 1, 3237921, 1976570, 486214, 60229, 3739, 127, 1, 71850913, 47203241, 13110749, 1892997, 152937, 6721, 169, 1, 1780353439, 1257567127, 380291461, 62248939, 5971291, 340729, 11197, 217, 1

Offset: 1

Alois P. Heinz, Dec 19 2021

			Triangle T(n,k) begins:
         1;
         7,        1;
        61,       19,        1;
       709,      277,       37,       1;
      9911,     4841,      811,      61,      1;
    167111,    91151,    19706,    1876,     91,    1;
   3237921,  1976570,   486214,   60229,   3739,  127,   1;
  71850913, 47203241, 13110749, 1892997, 152937, 6721, 169, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened

Column k=1 gives A350157.
Row sums give A007778.
T(n+1,n) gives A003215 for n>=1.
Cf. A001865, A319298, A322383.

g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, i, t) option remember; `if`(n=0, [1, 0], `if`(i>n, 0,
      add((p-> p+`if`(t>0 and t-j<1, [0, p[1]*i], 0))(g(i)^j*
        b(n-i*j, i+1, max(0, t-j))/j!*combinat[multinomial]
         (n, i$j, n-i*j)), j=0..n/i)))
    end:
T:= (n, k)-> b(n, 1, k)[2]:
seq(seq(T(n, k), k=1..n), n=1..10);

multinomial[n_, k_List] := n!/Times @@ (k!);
g[n_] := g[n] = Sum[n^(n - j)*(n - 1)!/(n - j)!, {j, 1, n}];
b[n_, i_, t_] := b[n, i, t] = If[n == 0, {1, 0}, If[i > n, {0, 0}, Sum[ Function[p, p + If[t > 0 && t - j < 1, {0, p[[1]]*i}, {0, 0}]][g[i]^j*b[n - i*j, i + 1, Max[0, t - j]]/j!*multinomial[n, Append[Table[i, {j}], n - i*j]]], {j, 0, n/i}]]];
T[n_, k_] := b[n, 1, k][[2]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 18 2022, after Alois P. Heinz *)

A200248 The number of (simultaneously) fixed and isolated points in the digraph representation of all functions f:{1,2,...,n}->{1,2,...,n}.

Original entry on oeis.org

0, 1, 2, 9, 68, 710, 9414, 151032, 2840648, 61247664, 1488691530, 40262372480, 1199047315212, 38984874829056, 1373954963380622, 52171222364513280, 2123286652815757200, 92201888436661409792, 4255016114128163220882, 207954945060162884960256

Offset: 0

Geoffrey Critzer, Nov 16 2011

nonn

A fixed point is a vertex with a self loop. An isolated point is a vertex that is not joined to any other vertex.

T. D. Noe, Table of n, a(n) for n = 0..101

t=Sum[n^(n-1)x^n/n!,{n,1,20}];Range[0,20]! CoefficientList[Series[x(Log[1/(1-t)]+1),{x,0,20}],x]

a(n)= n*A001865

E.g.f.: x*C(x) where C(x) is the e.g.f. for A001865

A225723 Triangular array read by rows: T(n,k) is the number of size k components in the digraph representation of all functions f:{1,2,...,n}->{1,2,...,n}; n>=1, 1<=k<=n.

Original entry on oeis.org

1, 2, 3, 12, 9, 17, 108, 72, 68, 142, 1280, 810, 680, 710, 1569, 18750, 11520, 9180, 8520, 9414, 21576, 326592, 196875, 152320, 134190, 131796, 151032, 355081, 6588344, 3919104, 2975000, 2544640, 2372328, 2416512, 2840648, 6805296

Offset: 1

Geoffrey Critzer, May 13 2013

T(n,1) = n*(n-1)^(n-1) = A055897(n).
Row sums = A190314.
T(n,n) = A001865(n).
Sum_{k=1..n} T(n,k)*k = n^(n+1).

			Triangle T(n,k) begins:
       1;
       2,      3;
      12,      9,     17;
     108,     72,     68,    142;
    1280,    810,    680,    710,   1569;
   18750,  11520,   9180,   8520,   9414,  21576;
  326592, 196875, 152320, 134190, 131796, 151032, 355081;
  ...

Alois P. Heinz, Rows n = 1..100, flattened

Cf. A225213.

b:= n-> n!*add(n^(n-k-1)/(n-k)!, k=1..n):
T:= (n, k)-> binomial(n,k)*b(k)*(n-k)^(n-k):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, May 13 2013

nn = 8; tx = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; txy =
Sum[n^(n - 1) (x y)^n/n!, {n, 1, nn}];
Map[Select[#, # > 0 &] &,
  Drop[Range[0, nn]! CoefficientList[
     Series[Log[1/(1 - txy)]/(1 - tx), {x, 0, nn}], {x, y}],
   1]] // Grid

E.g.f.: log(1/(1 - A(x*y)))/(1 - A(x)) where A(x) is the e.g.f. for A000169.

T(n,k) = C(n,k)*A001865(k)*A000312(n-k). - Alois P. Heinz, May 13 2013

cp's OEIS Frontend

A185391 a(n) = Sum_{k=0..n} A185390(n,k) * k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A201685 Triangular array read by rows. T(n,k) is the number of connected endofunctions on {1,2,...,n} that have exactly k nodes in the unique cycle of its digraph representation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A209327 Total number of nodes in the largest connected component of a functional digraph summed over all endofunctions f:{1,2,...,n}-> {1,2,...,n}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A036360 a(n) = Sum_{k=1..n} n! * n^(n-k+1) / (n-k)!.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A323673 Expansion of e.g.f. log(1 - LambertW(-x)*(2 + LambertW(-x))/2).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

A348590 Number of endofunctions on [n] with exactly one isolated fixed point.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A350135 Number of endofunctions on [2n] whose smallest connected component has size n.

Views

Author

Keywords