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

%I #36 Jan 24 2022 17:08:08

%S 0,0,2,24,324,5120,93750,1959552,46118408,1207959552,34867844010,

%T 1100000000000,37661140520652,1390911669927936,55123269399790046,

%U 2333521433367183360,105094533691406250000,5017514388048998039552,253135520137219049838162,13456471561751415850795008

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

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

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

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

%C 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

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

%e From _Joerg Arndt_, Jun 10 2013: (Start)

%e There are a(4-1)=a(3)=24 length-4 words of 3 letters (0,1,2) where adjacent letters are distinct:

%e 01: [ 0 1 0 1 ]

%e 02: [ 0 1 0 2 ]

%e 03: [ 0 1 2 0 ]

%e 04: [ 0 1 2 1 ]

%e 05: [ 0 2 0 1 ]

%e 06: [ 0 2 0 2 ]

%e 07: [ 0 2 1 0 ]

%e 08: [ 0 2 1 2 ]

%e 09: [ 1 0 1 0 ]

%e 10: [ 1 0 1 2 ]

%e 11: [ 1 0 2 0 ]

%e 12: [ 1 0 2 1 ]

%e 13: [ 1 2 0 1 ]

%e 14: [ 1 2 0 2 ]

%e 15: [ 1 2 1 0 ]

%e 16: [ 1 2 1 2 ]

%e 17: [ 2 0 1 0 ]

%e 18: [ 2 0 1 2 ]

%e 19: [ 2 0 2 0 ]

%e 20: [ 2 0 2 1 ]

%e 21: [ 2 1 0 1 ]

%e 22: [ 2 1 0 2 ]

%e 23: [ 2 1 2 0 ]

%e 24: [ 2 1 2 1 ]

%e (End)

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

%o (PARI) a(n) = n*(n-1)^n; \\ _Michel Marcus_, Aug 22 2017

%Y Cf. A219859.

%K nonn,easy

%O 0,3

%A _Geoffrey Critzer_, Jan 16 2013