cp's OEIS Frontend

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.

%I A351118 #32 Aug 25 2023 18:00:07
%S A351118 1,2,21,52,905,2436,58513,165096,5053329,14690260,546376721,
%T A351118 1621207512,70973853145,213746971816,10765350278145,32788134075856,
%U A351118 1867372988701217,5737757882873652,364586039726904145,1128184012390456440,79120980149003612841
%N 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.
%C A351118 For a random map, f:N->N, |N|=n, the probability of having a preimage of cardinality greater than n/2 is
%C A351118 a(n)/A000312(n) = n*Sum_{k=0..floor((n-1)/2)} binomial(n,k)*(1-1/n)^k*(1/n)^(n-k).
%C A351118 The number of maps g:V->C, |V|=v, |C|=c such that there exists x in C, |g^-1(x)| > v/2, is
%C A351118 b(c,v) = c * Sum_{k=0..floor((v-1)/2)} binomial(v,k)*(c-1)^k;
%C A351118 b(n,n) = a(n), b(2,n) = A202736(n), b(c,1) = b(c,2) = c.
%H A351118 Alois P. Heinz, <a href="/A351118/b351118.txt">Table of n, a(n) for n = 1..592</a>
%F A351118 a(n) = n * Sum_{k=0..floor((n-1)/2)} binomial(n,k)*(n-1)^k.
%t A351118 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 *)
%o A351118 (PARI) a(n) = n*sum(k=0,floor((n-1)/2), binomial(n,k)*(n-1)^k)
%Y A351118 Cf. A000312 (endofunctions).
%K A351118 nonn
%O A351118 1,2
%A A351118 _Aaron O. Schweiger_, Jan 31 2022