A209290 Number of elements whose preimage is the empty set summed over all functions f:{1,2,...,n}->{1,2,...,n}.

0, 0, 2, 24, 324, 5120, 93750, 1959552, 46118408, 1207959552, 34867844010, 1100000000000, 37661140520652, 1390911669927936, 55123269399790046, 2333521433367183360, 105094533691406250000, 5017514388048998039552, 253135520137219049838162, 13456471561751415850795008

Offset

0,3

Comments

a(n)/n^n is the expected value of the number of such elements which approaches n/e as n gets large.

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

a(n) = 2 * A109391(n-1) = 2 * A000217(n-1) * A000312(n-1) for n>0.

a(n-1) is the number of length-n words of n-1 letters where adjacent letters are distinct, see example. - Joerg Arndt, Jun 10 2013

Links

Table of n, a(n) for n=0..19.

Formula

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

Example

From Joerg Arndt, Jun 10 2013: (Start)
There are a(4-1)=a(3)=24 length-4 words of 3 letters (0,1,2) where adjacent letters are distinct:
01:  [ 0 1 0 1 ]
02:  [ 0 1 0 2 ]
03:  [ 0 1 2 0 ]
04:  [ 0 1 2 1 ]
05:  [ 0 2 0 1 ]
06:  [ 0 2 0 2 ]
07:  [ 0 2 1 0 ]
08:  [ 0 2 1 2 ]
09:  [ 1 0 1 0 ]
10:  [ 1 0 1 2 ]
11:  [ 1 0 2 0 ]
12:  [ 1 0 2 1 ]
13:  [ 1 2 0 1 ]
14:  [ 1 2 0 2 ]
15:  [ 1 2 1 0 ]
16:  [ 1 2 1 2 ]
17:  [ 2 0 1 0 ]
18:  [ 2 0 1 2 ]
19:  [ 2 0 2 0 ]
20:  [ 2 0 2 1 ]
21:  [ 2 1 0 1 ]
22:  [ 2 1 0 2 ]
23:  [ 2 1 2 0 ]
24:  [ 2 1 2 1 ]
(End)

Mathematica

Table[n (n-1)^n, {n, 0, 20}]

Prog

(PARI) a(n) = n*(n-1)^n; \\ Michel Marcus, Aug 22 2017

Crossrefs

Cf. A219859.

Sequence in context: A001864 A099045 A181174 * A333715 A081065 A043699

Adjacent sequences: A209287 A209288 A209289 * A209291 A209292 A209293

Keyword

nonn,easy

Author

Geoffrey Critzer, Jan 16 2013

Status

approved