cp's OEIS Frontend

A219706 Total number of nonrecurrent elements in all functions f:{1,2,...,n}->{1,2,...,n}.

%I A219706 #29 Nov 01 2024 04:44:14
%S A219706 0,0,2,30,456,7780,150480,3279234,79775360,2146962024,63397843200,
%T A219706 2039301671110,71007167075328,2661561062560140,106874954684266496,
%U A219706 4577827118698118250,208369657238965616640,10044458122057793060176,511225397403604416921600
%N A219706 Total number of nonrecurrent elements in all functions f:{1,2,...,n}->{1,2,...,n}.
%C A219706 x in {1,2,...,n} is a recurrent element if there is some k such that f^k(x) = x where f^k(x) denotes iterated functional composition. In other words, a recurrent element is in a cycle of the functional digraph. An element that is not recurrent is a nonrecurrent element.
%H A219706 Alois P. Heinz, <a href="/A219706/b219706.txt">Table of n, a(n) for n = 0..385</a>
%F A219706 E.g.f.: T(x)^2/(1-T(x))^3 where T(x) is the e.g.f. for A000169.
%F A219706 a(n) = Sum_{k=1..n-1} A219694(n,k)*k.
%F A219706 a(n) = n^(n+1) - A063169(n).
%p A219706 b:= proc(n) option remember; `if`(n=0, [1, 0], add((p->p+
%p A219706       [0, p[1]*j])((j-1)!*b(n-j)*binomial(n-1, j-1)), j=1..n))
%p A219706     end:
%p A219706 a:= n-> (p-> n*p[1]-p[2])(add(b(j)*n^(n-j)
%p A219706          *binomial(n-1, j-1), j=0..n)):
%p A219706 seq(a(n), n=0..25);  # _Alois P. Heinz_, May 22 2016
%t A219706 nn=20; f[list_] := Select[list,#>0&]; t=Sum[n^(n-1)x^n y^n/n!, {n,1,nn}]; Range[0,nn]! CoefficientList[Series[D[1/(1-x Exp[t]), y]/.y->1, {x,0,nn}], x]
%o A219706 (Python)
%o A219706 from math import comb
%o A219706 def A219706(n): return (n-1)*n**n-(sum(comb(n,k)*(n-k)**(n-k)*k**k for k in range(1,(n+1>>1)))<<1) - (0 if n&1 else comb(n,m:=n>>1)*m**n) if n else 0 # _Chai Wah Wu_, Apr 26 2023
%Y A219706 Cf. A000169, A063169, A219694.
%K A219706 nonn
%O A219706 0,3
%A A219706 _Geoffrey Critzer_, Nov 25 2012