cp's OEIS Frontend

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

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)

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)

f and g are in the same class if function g(i) = f(n+1-i) for all i.

Decomposition by class size

.

n 1 2

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

1 1 0

2 2 1

3 9 9

4 16 120

5 125 1500

6 216 23220

7 2401 410571

.

Demonstration for the formula: the classes are either of size 1 or 2.

The classes of size 1 is for functions invariant by reversal. They are specified by half their values, including one more if n is odd. Their number is n^(ceiling(n/2)).

So the number of classes under this symmetry is half (the number of functions + the number of classes of size 1).

a(n) is the number of unoriented length n strings with a maximum of n colors. - Andrew Howroyd, Sep 13 2019

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

Equivalent to the definition: number of classes of endofunctions of [n] under rotation and translation mod n.

Classes can be of size between n and n^2 depending on divisibility properties of n.

n n 2n 3n ... n^2

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

1 1

2 2

3 3 2

4 4 2 14

5 5 0 124

6 6 6 22 1282

7 7 0 16806

For prime n, the only possible class sizes are n and n^2, the classes of size n are the n arithmetical progression modulo n so #(c-n)=n, #(c-n^2)=(n^n - n*n)/n^2 = n^(n-2)-1 and a(n) = n^(n-2)+n-1.

(End)

Classes can be of size 1,2,4, n, 2n or 4n.

.

n 1 2 4 n 2n 4n

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

1 1

2 0 2

3 1 1 4

4 0 4 4 0 17 6

5 1 2 0 0 72 120

6 0 6 6 30 410 1730

7 1 3 0 0 1368 28728

.

For n odd, the constant function (n+1)/2 is the only stable by rotation, complement and reversal. So #c1=1.

For n even, there is no stable function, so #c1=0, but constant functions are grouped two by two making n/2 classes of size 2. Functions alternating a value and its complement are also grouped two by two, making another n/2 classes. This gives #c2=n.

Possible classes size are 1,2,4

n 1 2 4

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

1 1 0 0

2 0 2 0

3 1 5 4

4 0 16 56

5 1 74 744

6 0 216 11556

7 1 1371 205200.

Classes of size 2 can be further decomposed by whether the function is stable by reversal or stable by (reversal and complement).

n 2 2-r 2-rc

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

1 0 0 0

2 2 1 1

3 5 4 1

4 16 8 8

5 74 62 12

6 216 108 108

7 1371 1200 171.

There are two size of classes, n or 2n.

n c:n c:2n (c:n)/n (c:2n)/n

0 1

1 1

2 2

3 3 3 1 1

4 8 28 2 7

5 25 300 5 60

6 72 3852 12 642

7 343 58653 49 8379

There are two size of classes, n or 2n.

.

n c:n c:2n (c:2n)/4

0 1

1 1

2 2

3 1 4 1

4 8 28 7

5 1 312 78

6 32 3872 968

7 1 58824 14706

For n odd, only the set of n constant functions can have a member of their class equal to their complement, so c:n size is 1.

For n even, the c:n class is populated by binary words using k for 0 and n+1-k for 1. There are (2^n)/2 such words as the complement operation identifies them by pairs.

For n odd, c:2n(n) = (n^n - 1*n)/(2*n)

For n even, c:2n(n) = (n^n - 2^(n-1)*n)/(2*n)

There are three size of classes : n, 2n, 4n.

n c:n c:2n c:4n

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

0 1

1 1

2 2

3 1 2 1

4 4 10 10

5 1 24 144

6 8 148 1868

7 1 342 29241

For n odd, only the set of n constant functions can have a member of their class equal to their complement, so c:n size is 1.

For n even, we have 2^(n/2) binary words which have mirror-symmetry

There are three types of classes of size of 2n (stable by reversal, stable by complement, stable by rc as in A275550).