A219530 Number of functions f:{1,2,...,n}->{1,2,...,n} such that each component of f is a function on an interval of {1,2,...,n}.

1, 1, 4, 24, 195, 2046, 26752, 422546, 7849611, 167781117, 4054557471, 109246333917, 3245641491658, 105366022410057, 3709933487122164, 140791348680766521, 5728108758307500165, 248696925989154108462, 11476424805495560002162, 560894026563924188981599, 28941826672247857117927894

Offset

0,3

Comments

Here, a component of f is a weakly connected component of its functional digraph.

Links

Table of n, a(n) for n=0..20.

Formula

G.f.: 1/ (1 - A(x)) where A(x) is the o.g.f. for A001865.

Example

a(3)=24 because there are 27 functions f:{1,2,3}->{1,2,3} but three of these are not counted: 1->3 2->2 3->3; 1->3 2->2 3->1; 1->1 2->2 3->1.

Mathematica

nn=20; t= Sum[n^(n-1)x^n/n!, {n, 1, nn}]; a=Range[0, nn]! CoefficientList[Series[Log[1/(1-t)], {x, 0, nn}], x]; b=Sum[a[[i]]x^(i-1), {i, 1, nn+1}]; CoefficientList[Series[1/(1-b), {x, 0, nn}], x]

Crossrefs

Sequence in context: A007145 A241000 A305988 * A291819 A101370 A201338

Adjacent sequences: A219527 A219528 A219529 * A219531 A219532 A219533

Keyword

nonn

Author

Geoffrey Critzer, Nov 21 2012

Status

approved