A351118 a(n) is the number of endofunctions on an n-set where there is an element with a preimage of cardinality greater than n/2.

1, 2, 21, 52, 905, 2436, 58513, 165096, 5053329, 14690260, 546376721, 1621207512, 70973853145, 213746971816, 10765350278145, 32788134075856, 1867372988701217, 5737757882873652, 364586039726904145, 1128184012390456440, 79120980149003612841

Offset

1,2

Comments

For a random map, f:N->N, |N|=n, the probability of having a preimage of cardinality greater than n/2 is

a(n)/A000312(n) = n*Sum_{k=0..floor((n-1)/2)} binomial(n,k)*(1-1/n)^k*(1/n)^(n-k).

The number of maps g:V->C, |V|=v, |C|=c such that there exists x in C, |g^-1(x)| > v/2, is

b(c,v) = c * Sum_{k=0..floor((v-1)/2)} binomial(v,k)*(c-1)^k;

b(n,n) = a(n), b(2,n) = A202736(n), b(c,1) = b(c,2) = c.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..592

Formula

a(n) = n * Sum_{k=0..floor((n-1)/2)} binomial(n,k)*(n-1)^k.

Mathematica

a[1] = 1; a[n_] := n * Sum[(n - 1)^k*Binomial[n, k], {k, 0, Floor[(n - 1)/2]}]; Array[a, 20] (* Amiram Eldar, Feb 01 2022 *)

Prog

(PARI) a(n) = n*sum(k=0, floor((n-1)/2), binomial(n, k)*(n-1)^k)

Crossrefs

Cf. A000312 (endofunctions).

Sequence in context: A245546 A074875 A231807 * A097718 A180232 A075681

Adjacent sequences: A351115 A351116 A351117 * A351119 A351120 A351121

Keyword

nonn

Author

Aaron O. Schweiger, Jan 31 2022

Status

approved