|
|
A219706
|
|
Total number of nonrecurrent elements in all functions f:{1,2,...,n}->{1,2,...,n}.
|
|
2
|
|
|
0, 0, 2, 30, 456, 7780, 150480, 3279234, 79775360, 2146962024, 63397843200, 2039301671110, 71007167075328, 2661561062560140, 106874954684266496, 4577827118698118250, 208369657238965616640, 10044458122057793060176, 511225397403604416921600
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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.
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: T(x)^2/(1-T(x))^3 where T(x) is the e.g.f. for A000169.
a(n) = Sum_{k=1..n-1} A219694{n,k)*k.
|
|
MAPLE
|
b:= proc(n) option remember; `if`(n=0, [1, 0], add((p->p+
[0, p[1]*j])((j-1)!*b(n-j)*binomial(n-1, j-1)), j=1..n))
end:
a:= n-> (p-> n*p[1]-p[2])(add(b(j)*n^(n-j)
*binomial(n-1, j-1), j=0..n)):
|
|
MATHEMATICA
|
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]
|
|
PROG
|
(Python)
from math import comb
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|