A001372 -id:A001372 - cp's OEIS frontend

A000312 a(n) = n^n; number of labeled mappings from n points to themselves (endofunctions).

1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, 10000000000, 285311670611, 8916100448256, 302875106592253, 11112006825558016, 437893890380859375, 18446744073709551616, 827240261886336764177, 39346408075296537575424, 1978419655660313589123979

Offset: 0

N. J. A. Sloane

Also number of labeled pointed rooted trees (or vertebrates) on n nodes.
For n >= 1 a(n) is also the number of n X n (0,1) matrices in which each row contains exactly one entry equal to 1. - Avi Peretz (njk(AT)netvision.net.il), Apr 21 2001
Also the number of labeled rooted trees on (n+1) nodes such that the root is lower than its children. Also the number of alternating labeled rooted ordered trees on (n+1) nodes such that the root is lower than its children. - Cedric Chauve (chauve(AT)lacim.uqam.ca), Mar 27 2002
With p(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different parts of the i-th partition of n, p(j, i) = the j-th part of the i-th partition of n, m(i, j) = multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i=1..p(n)} (n!/(Product_{j=1..p(i)} p(i, j)!)) * ((n!/(n - p(i)))!/(Product_{j=1..d(i)} m(i, j)!)). - Thomas Wieder, May 18 2005
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) is the total number of leaves in all (n+1)^(n-1) trees on {0,1,2,...,n} rooted at 0. For example, with edges directed away from the root, the trees on {0,1,2} are {0->1,0->2},{0->1->2},{0->2->1} and contain a total of a(2)=4 leaves. - David Callan, Feb 01 2007
Limit_{n->infinity} A000169(n+1)/a(n) = exp(1). Convergence is slow, e.g., it takes n > 74 to get one decimal place correct and n > 163 to get two of them. - Alonso del Arte, Jun 20 2011
Also smallest k such that binomial(k, n) is divisible by n^(n-1), n > 0. - Michel Lagneau, Jul 29 2013
For n >= 2 a(n) is represented in base n as "one followed by n zeros". - R. J. Cano, Aug 22 2014
Number of length-n words over the alphabet of n letters. - Joerg Arndt, May 15 2015
Number of prime parking functions of length n+1. - Rui Duarte, Jul 27 2015
The probability density functions p(x, m=q, n=q, mu=1) = A000312(q)*E(x, q, q) and p(x, m=q, n=1, mu=q) = (A000312(q)/A000142(q-1))*x^(q-1)*E(x, q, 1), with q >= 1, lead to this sequence, see A163931, A274181 and A008276. - Johannes W. Meijer, Jun 17 2016
Satisfies Benford's law [Miller, 2015]. - N. J. A. Sloane, Feb 12 2017
A signed version of this sequence apart from the first term (1, -4, -27, 256, 3125, -46656, ...), has the following property: for every prime p == 1 (mod 2n), (-1)^(n(n-1)/2)*n^n = A057077(n)*a(n) is always a 2n-th power residue modulo p. - Jianing Song, Sep 05 2018
From Juhani Heino, May 07 2019: (Start)
n^n is both Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)
  and Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)*i.
The former is the familiar binomial distribution of a throw of n n-sided dice, according to how many times a required side appears, 0 to n. The latter is the same but each term is multiplied by its amount. This means that if the bank pays the player 1 token for each die that has the chosen side, it is always a fair game if the player pays 1 token to enter - neither bank nor player wins on average.
Examples:
2-sided dice (2 coins): 4 = 1 + 2 + 1 = 1*0 + 2*1 + 1*2 (0 omitted from now on);
3-sided dice (3 long triangular prisms): 27 = 8 + 12 + 6 + 1 = 12*1 + 6*2 + 1*3;
4-sided dice (4 long square prisms or 4 tetrahedrons): 256 = 81 + 108 + 54 + 12 + 1 = 108*1 + 54*2 + 12*3 + 1*4;
5-sided dice (5 long pentagonal prisms): 3125 = 1024 + 1280 + 640 + 160 + 20 + 1 = 1280*1 + 640*2 + 160*3 + 20*4 + 1*5;
6-sided dice (6 cubes): 46656 = 15625 + 18750 + 9375 + 2500 + 375 + 30 + 1 = 18750*1 + 9375*2 + 2500*3 + 375*4 + 30*5 + 1*6.
(End)
For each n >= 1 there is a graph on a(n) vertices whose largest independent set has size n and whose independent set sequence is constant (specifically, for each k=1,2,...,n, the graph has n^n independent sets of size k). There is no graph of smaller order with this property (Ball et al. 2019). - David Galvin, Jun 13 2019
For n >= 2 and 1 <= k <= n, a(n)*(n + 1)/4 + a(n)*(k - 1)*(n + 1 - k)/2*n is equal to the sum over all words w = w(1)...w(n) of length n over the alphabet {1, 2, ..., n} of the following quantity: Sum_{i=1..w(k)} w(i). Inspired by Problem 12432 in the AMM (see links). - Sela Fried, Dec 10 2023
Also, dimension of the unique cohomology group of the smallest interval containing the poset of partitions decorated by Perm, i.e. the poset of pointed partitions. - Bérénice Delcroix-Oger, Jun 25 2025

			G.f. = 1 + x + 4*x^2 + 27*x^3 + 256*x^4 + 3125*x^5 + 46656*x^6 + 823543*x^7 + ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 62, 63, 87.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 173, #39.
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.37)
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).

Kenny Lau, Table of n, a(n) for n = 0..385 [First 100 terms computed by T. D. Noe]
Taylor Ball, David Galvin, Katie Hyry, and Kyle Weingartner, Independent set and matching permutations, arXiv:1901.06579 [math.CO], 2019.
Arthur T. Benjamin and Fritz Juhnke, Another way of counting n^n, SIAM J. Discrete Math., Vol. 5, No. 3 (1992), pp. 377-379. - _N. J. A. Sloane_, Jun 09 2011
H. Bottomley, Illustration of initial terms.
H. J. Brothers and J. A. Knox, New closed-form approximations to the logarithmic constant e, The Mathematical Intelligencer, Vol. 20 (4), 1998, pp. 25-29. (Sequence appears as formula in Eq. (8))
C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.
Bérénice Delcroix-Oger and Clément Dupont, Lie-operads and operadic modules from poset cohomology, arXiv:2505.06094 [math.CO], 2025. See p. 34.
Frank Ellermann, Illustration of binomial transforms.
José María Grau and Antonio M. Oller-Marcén, On the last digit and the last non-zero digit of n^n in base b, Bulletin of the Korean Mathematical Society, Vol. 51, No. 5 (2014), pp. 1325-1337; arXiv preprint, arXiv:1203.4066 [math.NT], 2012.
Nick Hobson, Solution to puzzle 48: Exponential equation.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 36.
Steven J. Miller (ed.), Exercises to "The Theory and Applications of Benford's Law", Princeton University Press, 2015.
Mustafa Obaid et al., The number of complete exceptional sequences for a Dynkin algebra, arXiv preprint arXiv:1307.7573 [math.RT], 2013.
Franck Ramaharo, A generating polynomial for the pretzel knot, arXiv:1805.10680 [math.CO], 2018.
E. Vigren (Proposer), Problem 12432, Amer. Math. Monthly 130 (2023), p. 953.
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See pp. 12-13.
Eric Weisstein's World of Mathematics, Hadamard's Maximum Determinant Problem.
Eric Weisstein's World of Mathematics, Hankel Matrix.
Dimitri Zvonkine, An algebra of power series..., arXiv:math/0403092 [math.AG], 2004.
Index entries for "core" sequences
Index entries for sequences related to rooted trees
Index entries for sequences related to Benford's law

Cf. A000107, A000169, A000272, A001372, A007778, A007830, A008785-A008791, A019538, A048993, A008279, A085741, A062206, A212333.
First column of triangle A055858. Row sums of A066324.
Cf. A001923 (partial sums), A002109 (partial products), A007781 (first differences), A066588 (sum of digits).
Cf. A056665, A081721, A130293, A168658, A275549-A275558 (various classes of endofunctions).
Cf. A174824, A204688.
Cf. A055137, A083648.

a000312 n = n ^ n
a000312_list = zipWith (^) [0..] [0..]  -- Reinhard Zumkeller, Jul 07 2012

A000312 := n->n^n: seq(A000312(n), n=0..17);

Array[ #^# &, 16] (* Vladimir Joseph Stephan Orlovsky, May 01 2008 *)
Table[Sum[StirlingS2[n, i] i! Binomial[n, i], {i, 0, n}], {n, 0, 20}] (* Geoffrey Critzer, Mar 17 2009 *)
a[ n_] := If[ n < 1, Boole[n == 0], n^n]; (* Michael Somos, May 24 2014 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1 / (1 + LambertW[-x]), {x, 0, n}]]; (* Michael Somos, May 24 2014 *)
a[ n_] := If[n < 0, 0, n! SeriesCoefficient[ Nest[ 1 / (1 - x / (1 - Integrate[#, x])) &, 1 + O[x], n], {x, 0, n}]]; (* Michael Somos, May 24 2014 *)
a[ n_] := If[ n < 0, 0, With[{m = n + 1}, m! SeriesCoefficient[ InverseSeries[ Series[ (x - 1) Log[1 - x], {x, 0, m}]], m]]]; (* Michael Somos, May 24 2014 *)

A000312[n]:=if n=0 then 1 else n^n$
makelist(A000312[n],n,0,30); /* Martin Ettl, Oct 29 2012 */

PARI
```
{a(n) = n^n};
```

is(n)=my(b,k=ispower(n,,&b));if(k,for(e=1,valuation(k,b), if(k/b^e == e, return(1)))); n==1 \\ Charles R Greathouse IV, Jan 14 2013

{a(n) = my(A = 1 + O(x)); if( n<0, 0, for(k=1, n, A = 1 / (1 - x / (1 - intformal( A)))); n! * polcoeff( A, n))}; /* Michael Somos, May 24 2014 */

def A000312(n): return n**n # Chai Wah Wu, Nov 07 2022

a(n-1) = -Sum_{i=1..n} (-1)^i*i*n^(n-1-i)*binomial(n, i). - Yong Kong (ykong(AT)curagen.com), Dec 28 2000
E.g.f.: 1/(1 + W(-x)), W(x) = principal branch of Lambert's function.
a(n) = Sum_{k>=0} binomial(n, k)*Stirling2(n, k)*k! = Sum_{k>=0} A008279(n,k)*A048993(n,k) = Sum_{k>=0} A019538(n,k)*A007318(n,k). - Philippe Deléham, Dec 14 2003
E.g.f.: 1/(1 - T), where T = T(x) is Euler's tree function (see A000169).
a(n) = A000169(n+1)*A128433(n+1,1)/A128434(n+1,1). - Reinhard Zumkeller, Mar 03 2007
Comment on power series with denominators a(n): Let f(x) = 1 + Sum_{n>=1} x^n/n^n. Then as x -> infinity, f(x) ~ exp(x/e)*sqrt(2*Pi*x/e). - Philippe Flajolet, Sep 11 2008
E.g.f.: 1 - exp(W(-x)) with an offset of 1 where W(x) = principal branch of Lambert's function. - Vladimir Kruchinin, Sep 15 2010
a(n) = (n-1)*a(n-1) + Sum_{i=1..n} binomial(n, i)*a(i-1)*a(n-i). - Vladimir Shevelev, Sep 30 2010
With an offset of 1, the e.g.f. is the compositional inverse ((x - 1)*log(1 - x))^(-1) = x + x^2/2! + 4*x^3/3! + 27*x^4/4! + .... - Peter Bala, Dec 09 2011
a(n) = denominator((1 + 1/n)^n) for n > 0. - Jean-François Alcover, Jan 14 2013
a(n) = A089072(n,n) for n > 0. - Reinhard Zumkeller, Mar 18 2013
a(n) = (n-1)^(n-1)*(2*n) + Sum_{i=1..n-2} binomial(n, i)*(i^i*(n-i-1)^(n-i-1)), n > 1, a(0) = 1, a(1) = 1. - Vladimir Kruchinin, Nov 28 2014
log(a(n)) = lim_{k->infinity} k*(n^(1+1/k) - n). - Richard R. Forberg, Feb 04 2015
From Ilya Gutkovskiy, Jun 18 2016: (Start)
Sum_{n>=1} 1/a(n) = 1.291285997... = A073009.
Sum_{n>=1} 1/a(n)^2 = 1.063887103... = A086648.
Sum_{n>=1} n!/a(n) = 1.879853862... = A094082. (End)
A000169(n+1)/a(n) -> e, as n -> oo. - Daniel Suteu, Jul 23 2016
a(n) = n!*Product_{k=1..n} binomial(n, k)/Product_{k=1..n-1} binomial(n-1, k) = n!*A001142(n)/A001142(n-1). - Tony Foster III, Sep 05 2018
a(n-1) = abs(p_n(2-n)), for n > 2, the single local extremum of the n-th row polynomial of A055137 with Bagula's sign convention. - Tom Copeland, Nov 15 2019
Sum_{n>=1} (-1)^(n+1)/a(n) = A083648. - Amiram Eldar, Jun 25 2021
Limit_{n->oo} (a(n+1)/a(n) - a(n)/a(n-1)) = e (see Brothers/Knox link). - Harlan J. Brothers, Oct 24 2021
Conjecture: a(n) = Sum_{i=0..n} A048994(n, i) * A048993(n+i, n) for n >= 0; proved by Mike Earnest, see link at A354797. - Werner Schulte, Jun 19 2022

A181162 Number of commuting functions: the number of ordered pairs (f,g) of functions from {1..n} to itself such that fg=gf (i.e., f(g(i))=g(f(i)) for all i).

Original entry on oeis.org

1, 1, 10, 141, 2824, 71565, 2244096, 83982199, 3681265792, 186047433225, 10716241342240, 697053065658411, 50827694884298784, 4129325095108122637, 371782656333674104624, 36918345387693628911375, 4025196918605160943576576, 479796375191949916361466897

Offset: 0

Jeffrey Norden, Oct 07 2010

Also, the total number of endomorphisms of all directed graphs on n labeled vertices with outdegree of each vertex equal 1. - Max Alekseyev, Jan 09 2015
Seems to be relatively hard to compute for large n. (a(n)-n^n)/2 is always an integer, since it gives the number of unordered pairs of distinct commuting functions.
a(n) is divisible by n as proved by Holloway and Shattuck (2015).
From Joerg Arndt, Jul 21 2014: (Start)
Multiply fg=gf from the right by f to obtain fgf=gff, and use f(gf)=f(fg)=ffg to see ffg=gff; iterate to see f^k g = g f^k for all k>=1; by symmetry g^k f = f g^k holds as well.
More generally, if X and Y are words of length w over the alphabet {f,g}, then X = Y (as functional composition) whenever both words contain j symbols f and k symbols g (and j+k=w).  (End)
Functions with the same mapping pattern have the same number of commuting functions, so there is no need to check every pair. - Martin Fuller, Feb 01 2015

			The a(2) = 10 pairs of maps [2] -> [2] are:
01:  [ 1 1 ]  [ 1 1 ]
02:  [ 1 1 ]  [ 1 2 ]
03:  [ 1 2 ]  [ 1 1 ]
04:  [ 1 2 ]  [ 1 2 ]
05:  [ 1 2 ]  [ 2 1 ]
06:  [ 1 2 ]  [ 2 2 ]
07:  [ 2 1 ]  [ 1 2 ]
08:  [ 2 1 ]  [ 2 1 ]
09:  [ 2 2 ]  [ 1 2 ]
10:  [ 2 2 ]  [ 2 2 ]
- _Joerg Arndt_, Jul 22 2014

Martin Fuller, Table of n, a(n) for n = 0..20
Joerg Arndt, the a(3) = 141 pairs of maps [3] -> [3]
Stephen M. Buckley, Minimal order semigroups with specified commuting probability, 04-03-2013. - _W. Edwin Clark_, Jul 21 2014
Martin Fuller, a(6) from the A001372(6)=130 mapping patterns
M. Holloway and M. Shattuck, Commuting pairs of functions on a finite set, 2015.
Math Overflow, What is the probability two random maps on n symbols commute?, 2013. - _W. Edwin Clark_, Jul 21 2014
Math Overflow, Counting and understanding commuting functions, 2010.

A053529 is a similar count for permutations. A254529 is for permutations commuting with functions.

Cf. A000312, A001372, A239749-A239785, A239836-A239841.

(* This brute force code allows to get a few terms *)
a[n_] := a[n] = If[n == 0, 1, Module[{f, g, T}, T = Tuples[Range[n], n]; Table[f = T[[j, #]]&; g = T[[k, #]] &; Table[True, {n}] == Table[f[g[i]] == g[f[i]], {i, n}], {j, n^n}, {k, n^n}] // Flatten // Count[#, True]&]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 5}] (* Jean-François Alcover, Sep 24 2022 *)

a(11)-a(20) from Martin Fuller, Feb 01 2015

A056665 Number of equivalence classes of n-valued Post functions of 1 variable under action of complementing group C(1,n).

Original entry on oeis.org

1, 3, 11, 70, 629, 7826, 117655, 2097684, 43046889, 1000010044, 25937424611, 743008623292, 23298085122493, 793714780783770, 29192926025492783, 1152921504875290696, 48661191875666868497, 2185911559749720272442, 104127350297911241532859

Offset: 1

Vladeta Jovovic, Aug 09 2000

Diagonal of arrays defined in A054630 and A054631.
Given n colors, a(n) = number of necklaces with n beads and 1 up to n colors effectively assigned to them (super_labeled: which also generates n different monochrome necklaces). - Wouter Meeussen, Aug 09 2002
Number of endofunctions on a set with n objects up to cyclic permutation (rotation). E.g., for n = 3, the 11 endofunctions are 1,1,1; 2,2,2; 3,3,3; 1,1,2; 1,2,2; 1,1,3; 1,3,3; 2,2,3; 2,3,3; 1,2,3; and 1,3,2. - Franklin T. Adams-Watters, Jan 17 2007
Also number of pre-necklaces in Sigma(n,n) (see Ruskey and others). - Peter Luschny, Aug 12 2012
From Olivier Gérard, Aug 01 2016: (Start)
Decomposition of the endofunctions by class size.
.
  n |  1   2   3   4    5     6       7
  --+----------------------------------
  1 |  1
  2 |  2   1
  3 |  3   0   8
  4 |  4   6   0  60
  5 |  5   0   0   0  624
  6 |  6  15  70   0    0  7735
  7 |  7   0   0   0    0     0  117648
.
The right diagonal gives the number of Lyndon Words or aperiodic necklaces, A075147. By multiplying each column by the corresponding size and summing, one gets A000312.
(End)

			The 11 necklaces for n=3 are (grouped by partition of 3): (RRR,GGG,BBB),(RRG,RGG, RRB,RBB, GGB,GBB), (RGB,RBG).

D. E. Knuth. Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, 7.2.1.1. Addison-Wesley, 2005.

Alois P. Heinz, Table of n, a(n) for n = 1..200
M. A. Harrison and R. G. High, On the cycle index of a product of permutation groups, J. Combin. Theory, 4 (1968), 277-299.
F. Ruskey, C. Savage, and T. M. Y. Wang, Generating necklaces, Journal of Algorithms, 13(3), 414 - 430, 1992.
Index entries for sequences related to groups

Cf. A001323, A001324, A001372, A000312.
Diagonal of arrays defined in A054630, A054631 and A075195.
Cf. A075147 Aperiodic necklaces, a subset of this sequence.
Cf. A000169 Classes under translation mod n
Cf. A168658 Classes under complement to n+1
Cf. A130293 Classes under translation and rotation
Cf. A081721 Classes under rotation and reversal
Cf. A275549 Classes under reversal
Cf. A275550 Classes under reversal and complement
Cf. A275551 Classes under translation and reversal
Cf. A275552 Classes under translation and complement
Cf. A275553 Classes under translation, complement and reversal
Cf. A275554 Classes under translation, rotation and complement
Cf. A275555 Classes under translation, rotation and reversal
Cf. A275556 Classes under translation, rotation, complement and reversal
Cf. A275557 Classes under rotation and complement
Cf. A275558 Classes under rotation, complement and reversal
Cf. A228640.

with(numtheory):
a:= n-> add(phi(d)*n^(n/d), d=divisors(n))/n:
seq(a(n), n=1..25);  # Alois P. Heinz, Jun 18 2013

Table[Fold[ #1+EulerPhi[ #2] n^(n/#2)&, 0, Divisors[n]]/n, {n, 7}]

a(n) = sum(k=1,n,n^gcd(k,n)) / n; \\ Joerg Arndt, Mar 19 2017

# This algorithm counts all n-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime. It is algorithm F in Knuth 7.2.1.1.
def A056665_list(n):
    C = []
    for m in (1..n):
        a = [0]*(n+1); a[0]=-1;
        j = 1; count = 0
        while(true):
            if m%j == 0 : count += 1;
            j = n
            while a[j] >= m-1 : j -= 1
            if j == 0 : break
            a[j] += 1
            for k in (j+1..n): a[k] = a[k-j]
        C.append(count)
    return C

def A056665(n): return sum(euler_phi(d)*n^(n//d)//n for d in divisors(n))
[A056665(n) for n in (1..18)] # Peter Luschny, Aug 12 2012

a(n) = Sum_{d|n} phi(d)*n^(n/d)/n.
a(n) ~ n^(n-1). - Vaclav Kotesovec, Sep 11 2014
a(n) = (1/n) * Sum_{k=1..n} n^gcd(k,n). - Joerg Arndt, Mar 19 2017
a(n) = [x^n] -Sum_{k>=1} phi(k)*log(1 - n*x^k)/k. - Ilya Gutkovskiy, Mar 21 2018
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = (1/n)*Sum_{k=1..n} n^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).
a(n) = (1/n)*A228640(n). (End)

A027852 Number of connected functions on n points with a loop of length 2.

Original entry on oeis.org

0, 1, 1, 3, 6, 16, 37, 96, 239, 622, 1607, 4235, 11185, 29862, 80070, 216176, 586218, 1597578, 4370721, 12003882, 33077327, 91433267, 253454781, 704429853, 1962537755, 5479855546, 15332668869, 42983656210, 120716987723, 339596063606, 956840683968

Offset: 1

Christian G. Bower, Dec 14 1997

nonn

Number of unordered pairs of rooted trees with a total of n nodes.
Equivalently, the number of rooted trees on n+1 nodes where the root has degree 2.
Number of trees on n nodes rooted at an edge. - Washington Bomfim, Jul 06 2012
Guy (1988) calls these tadpole graphs. - N. J. A. Sloane, Nov 04 2014
Number of unicyclic graphs of n nodes with a cycle length of two (in other words, a double edge). - Washington Bomfim, Dec 02 2020

Alois P. Heinz, Table of n, a(n) for n = 1..2136
Washington Bomfim, Illustration of initial terms
R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy) Includes illustrations for n <= 6.
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 [math.CO] (2016), Eq. (75).
Index entries for sequences related to rooted trees

Column 2 of A033185 (forests of rooted trees), A217781 (unicyclic graphs), A339303 (unoriented linear forests) and A339428 (connected functions).

Cf. A000081, A000106, A000226, A000631, A001372, A002861.

with(numtheory): b:= proc(n) option remember; local d, j; `if`(n<=1, n, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= n-> (add(b(i) *b(n-i), i=0..n) +`if`(irem(n, 2)=0, b(n/2), 0))/2: seq(a(n), n=1..50);  # Alois P. Heinz, Aug 22 2008, revised Oct 07 2011
# second, re-usable version
A027852 := proc(N::integer)
    local dh, Nprime;
    dh := 0 ;
    for Nprime from 0 to N do
        dh := dh+A000081(Nprime)*A000081(N-Nprime) ;
    end do:
    if type(N,'even') then
        dh := dh+A000081(N/2) ;
    end if;
    dh/2 ;
end proc: # R. J. Mathar, Mar 06 2017

Needs["Combinatorica`"];nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n - 1, i] i, {i, 1, n - 1}]/(n - 1); rt = Table[a[i], {i, 1, nn}]; Take[CoefficientList[CycleIndex[DihedralGroup[2], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], {2, nn}]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
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)];
a[n_] := (Sum[b[i] b[n-i], {i, 0, n}] + If[Mod[n, 2] == 0, b[n/2], 0])/2;
Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Oct 30 2018, after Alois P. Heinz *)

seq(max_n)= { my(V = f = vector(max_n), i=1,s); f[1]=1;
for(j=1, max_n - 1, f[j+1] = 1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1]));
for(n = 1, max_n, s = sum(k = 1, (n-1)/2, ( f[k] * f[n-k] ));
if(n % 2 == 1, V[i] = s, V[i] = s + (f[n/2]^2 + f[n/2])/2); i++); V };
\\ Washington Bomfim, Jul 06 2012 and Dec 01 2020

G.f.: A(x) = (B(x)^2 + B(x^2))/2 where B(x) is g.f. of A000081.
a(n) = Sum_{k=1..(n-1)/2}( f(k)*f(n-k) ) + [n mod 2 = 0] * ( f(n/2)^2+f(n/2) ) /2, where f(n) = A000081(n). - Washington Bomfim, Jul 06 2012 and Dec 01 2020
a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = A187770 = 0.43992401257102530404090339... . - Vaclav Kotesovec, Sep 12 2014
2*a(n) = A000106(n) + A000081(n/2), where A(.)=0 if the argument is non-integer. - R. J. Mathar, Jun 04 2020

Edited by Christian G. Bower, Feb 12 2002

A002861 Number of connected functions (or mapping patterns) on n unlabeled points, or number of rings and branches with n edges.

Original entry on oeis.org

1, 2, 4, 9, 20, 51, 125, 329, 862, 2311, 6217, 16949, 46350, 127714, 353272, 981753, 2737539, 7659789, 21492286, 60466130, 170510030, 481867683, 1364424829, 3870373826, 10996890237, 31293083540, 89173833915, 254445242754, 726907585652, 2079012341822

Offset: 1

N. J. A. Sloane

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.
R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.399.
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 = 1..1000 (first 500 terms from C. G. Bower)
A. L. Agore, A. Chirvasitu, and G. Militaru, The set-theoretic Yang-Baxter equation, Kimura semigroups and functional graphs, arXiv:2303.06700 [math.QA], 2023.
C. G. Bower, Transforms (2)
Oscar Defrain, Antonio E. Porreca and Ekaterina Timofeeva, Polynomial-delay generation of functional digraphs up to isomorphism, Disc. Appl. Math., vol 357 (2024), pp. 24-33.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 480
R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 118

Row sums of A339428.
Cf. A000081, A001372.
Cf. A027852, A029852, A029853, A029868.

spec2861 := [B, {A=Prod(Z,Set(A)), B=Cycle(A)}, unlabeled]; [seq(combstruct[count](spec2861,size=n), n=1..27)];

Needs["Combinatorica`"];
nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n - 1, i] i, {i, 1, n - 1}]/(n - 1); rt = Table[a[i],{i, 1, nn}]; Apply[Plus, Table[Take[CoefficientList[CycleIndex[CyclicGroup[n], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k * i), {i, nn}], {k, 1, nn}][[j]], {j, nn}], x], nn], {n, 30}]]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
M = 66; A = Table[1, {M + 1}]; For[n = 1, n <= M, n++, A[[n + 1]] = 1/n * Sum[Sum[d * A[[d]], {d, Divisors[k]}] * A[[n - k + 1]], {k, n}]]; A81 = {0} ~ Join ~ A; H[t_] = A81.t^Range[0, Length[A81] - 1]; L = Sum[EulerPhi[j]/j * Log[1/(1 - H[x^j])], {j, M}] + O[x]^M; CoefficientList[L, x] // Rest (* Jean-François Alcover, Dec 28 2019, after Joerg Arndt *)

N=66;  A=vector(N+1, j, 1);
for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );
A000081=concat([0], A);
H(t)=subst(Ser(A000081, 't), 't, t);
x='x+O('x^N);
L=sum(j=1,N, eulerphi(j)/j * log(1/(1-H(x^j))));
Vec(L)
\\ Joerg Arndt, Jul 10 2014

CIK transform of A000081.

a(n) = A000081 + A027852 + A029852 + A029853 + A029868 + ... - Geoffrey Critzer, Oct 12 2012

More terms from Philippe Flajolet and Paul Zimmermann, Mar 15 1996

A048888 a(n) = Sum_{m=1..n} T(m,n+1-m), array T as in A048887.

Original entry on oeis.org

0, 1, 2, 4, 7, 13, 23, 42, 76, 139, 255, 471, 873, 1627, 3044, 5718, 10779, 20387, 38673, 73561, 140267, 268065, 513349, 984910, 1892874, 3643569, 7023561, 13557019, 26200181, 50691977, 98182665, 190353369, 369393465, 717457655

Offset: 0

Clark Kimberling

nonn

From Marc LeBrun, Dec 12 2001: (Start)
Define a "numbral arithmetic" by replacing addition with binary bitwise inclusive-OR (so that [3] + [5] = [7] etc.) and multiplication becomes shift-&-OR instead of shift-&-add (so that [3] * [3] = [7] etc.). [d] divides [n] means there exists an [e] with [d] * [e] = [n]. For example the six divisors of [14] are [1], [2], [3], [6], [7] and [14]. Then it appears that this sequence gives the number of proper divisors of [2^n-1]. Conjecture confirmed by Richard C. Schroeppel, Dec 14 2001. (End)
The number of "prime endofunctions" on n points, meaning the cardinality of the subset of the A001372(n) mappings (or mapping patterns) up to isomorphism from n (unlabeled) points to themselves (endofunctions) which are neither the sum of prime endofunctions (i.e., whose disjoint connected components are prime endofunctions) nor the categorical product of prime endofunctions. The n for which a(n) is prime (n such that the number of prime endofunctions on n points is itself prime) are 2, 4, 5, 6, 9, 13, 19, ... - Jonathan Vos Post, Nov 19 2006
For n>=1, compositions p(1)+p(2)+...+p(m)=n such that p(k)<=p(1)+1, see example. - Joerg Arndt, Dec 28 2012

			From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(6)=23 compositions p(1)+p(2)+...+p(m)=6 such that p(k)<=p(1)+1:
[ 1]  [ 1 1 1 1 1 1 ]
[ 2]  [ 1 1 1 1 2 ]
[ 3]  [ 1 1 1 2 1 ]
[ 4]  [ 1 1 2 1 1 ]
[ 5]  [ 1 1 2 2 ]
[ 6]  [ 1 2 1 1 1 ]
[ 7]  [ 1 2 1 2 ]
[ 8]  [ 1 2 2 1 ]
[ 9]  [ 2 1 1 1 1 ]
[10]  [ 2 1 1 2 ]
[11]  [ 2 1 2 1 ]
[12]  [ 2 1 3 ]
[13]  [ 2 2 1 1 ]
[14]  [ 2 2 2 ]
[15]  [ 2 3 1 ]
[16]  [ 3 1 1 1 ]
[17]  [ 3 1 2 ]
[18]  [ 3 2 1 ]
[19]  [ 3 3 ]
[20]  [ 4 1 1 ]
[21]  [ 4 2 ]
[22]  [ 5 1 ]
[23]  [ 6 ]
(End)

D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, J. Integer Seq., Vol. 9 (2006), Article 06.3.1.

Cf. A007059.

Cf. A000312, A001372, A002861, A006961, A001373, A054050, A054745, A125024.

N = 66;  x = 'x + O('x^N);
gf = sum(n=0,N,  (1-x^n)*x^n/(1-2*x+x^(n+1)) ) + 'c0;
v = Vec(gf);  v[1]-='c0;  v
/* Joerg Arndt, Apr 14 2013 */

G.f.: Sum_{k>0} x^k*(1-x^k)/(1-2*x+x^(k+1)). - Vladeta Jovovic, Feb 25 2003

a(m) = Sum_{ n=2..m+1 } Fn(m) where Fn is a Fibonacci n-step number (Fibonacci, tetranacci, etc.) indexed as in A000045, A000073, A000078. - Gerald McGarvey, Sep 25 2004

cp's OEIS Frontend

A125023 Partial sums of A001372.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A129834 (k-1)/2 where k runs over odd terms of A001372.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A124128 Numbers k such that A001372(k) is prime.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A124933 Number of prime divisors (counted with multiplicity) of number of endofunctions on n points (A001372).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A000312 a(n) = n^n; number of labeled mappings from n points to themselves (endofunctions).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

PARI

PARI

PARI

Python

Formula

A181162 Number of commuting functions: the number of ordered pairs (f,g) of functions from {1..n} to itself such that fg=gf (i.e., f(g(i))=g(f(i)) for all i).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A056665 Number of equivalence classes of n-valued Post functions of 1 variable under action of complementing group C(1,n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Sage