cp's OEIS Frontend

This is the sequence that started it all: the first sequence in the database!

The height h(V) of a node V in a rooted tree is its distance from the root. a(n) = Sum_{all nodes V in all n^(n-1) rooted trees on n nodes} h(V)/n.

In the trees which have [0, n-1] = (0, 1, ..., n-1) as their ordered set of nodes, the number of nodes at distance i from node 0 is f(n,i) = (n-1)...(n-i)(i+1)n^(j-1), 0 <= i < n-1, i+j = n-1 (and f(n,n-1) = (n-1)!): (n-1)...(n-i) counts the words coding the paths of length i from any node to 0, n^(j-1) counts the Pruefer codes of the rest, words build by iterated deletion of the greater node of degree 1 ... except the last one, (i+1), necessary pointing at the path. If g(n,i) = (n-1)...(n-i)n^j, i+j = n-1, f(n,i) = g(n,i) - g(n,i+1), g(n,i) = Sum_{k>=i} f(n,k), the sequence is Sum_{i=1..n-1} g(n,i). - Claude Lenormand (claude.lenormand(AT)free.fr), Jan 26 2001

If one randomly selects one ball from an urn containing n different balls, with replacement, until exactly one ball has been selected twice, the probability that this ball was also the second ball to be selected once is a(n)/n^n. See also A001865. - Matthew Vandermast, Jun 15 2004

a(n) is the number of connected endofunctions with no fixed points. - Geoffrey Critzer, Dec 13 2011

a(n) is the number of weakly connected simple digraphs on n labeled nodes where every node has out-degree 1. A digraph where all out-degrees are 1 can be called a functional digraph due to the correspondence with endofunctions. - Andrew Howroyd, Feb 06 2024

a(n-2) is the number of trees with n+1 unlabeled vertices and n labeled edges for n > 1. - Christian G. Bower, 12/99 [corrected by Jonathan Vos Post, Sep 22 2012]

a(n) is the number of nonequivalent primitive meromorphic functions with one pole of order n+3 on a Riemann surface of genus 0. - Noam Katz (noamkj(AT)hotmail.com), Mar 30 2001

Pikhurko writes: "Cameron demonstrated that the total number of edge-labeled trees with n >= 2 edges is (n+1)^(n-2) by showing that the number of vertex-labeled trees of size n is n+1 times larger than the number of edge-labeled ones." - Jonathan Vos Post, Sep 22 2012

With offset 1, a(n) is the number of ways to build a rooted labeled forest with some (possibly all or none) of the nodes from {1,2,...,n} and then build another forest with the remaining nodes. - Geoffrey Critzer, May 10 2013

a(n) = |non-injective functions [n]->[n]| = |non-surjective functions [n]->[n]|.

Fit a polynomial f of degree n-1 to the first n n-th powers of nonnegative integers. Then a(n) = f(n). - Franklin T. Adams-Watters, Dec 28 2006

n^n > n! for n >= 3. [Mitrinovic]

a(n) is the number of functions from {1,2,...,n} into {1,2,...,n} that have no fixed points.

The probability that a random function from {1,2,...,n} into {1,2,...,n} has no fixed point is equal to a(n)/n^n; it tends to 1/e when n tends to infinity. - Robert FERREOL, Mar 29 2017

Second column (unsigned) 2, 3, 8, 30, 144, ... is A001048.

Diagonal 1, 2, 9, 64, 625, 7776, ... is A000169.

From Mathew Englander, Jul 07 2020: (Start)

All a(n) are odd and for n even, a(n) == 3 (mod 4); for n odd and n != 1, a(n) == 1 (mod 4).

The correspondence between n and a(n) when considered mod 6 is as follows: for n == 0, 1, 2, or 3, a(n) == 5; for n == 4, a(n) == 3; for n == 5, a(n) == 1.

For all n, a(n)+1 is a multiple of n^2.

For n odd and n >= 3, a(n)-1 is a multiple of (n+1)^2.

For n even and n >= 0, a(n)+1 is a multiple of (n+1)^2.

For proofs of the above, see the Englander link. (End)

T(n,n), T given in A081720.

From Olivier Gérard, Aug 01 2016: (Start)

Number of classes of functions of [n] to [n] under rotation and reversal.

.

Classes can be of size between 1 and 2n

depending on divisibility properties of n.

.

n 1 2 3 4 5 n 2n

----------------------------------------

1 1

2 2 1

3 3 0 6 1

4 4 6 0 30 15

5 5 0 0 120 252

6 6 15 30 725 3515

7 7 0 0 2394 57627

.

(End)

First differs from A343658 at A(4,2) = 5, A343658(4,2) = 6.

As a triangle, T(n,k) = number of divisors of k^(n-k).