login
A239750
Number of ordered pairs of endofunctions (f,g) on a set of n elements satisfying g(f(x)) = f(f(f(x))).
3
1, 1, 6, 87, 2200, 84245, 4492656, 315937195, 28186856832, 3099006365769, 410478164588800, 64323095036300111, 11748771067445148672, 2470422069374379054493, 591735532838657160296448, 160004357420756572368889875, 48458574881000820765562863616
OFFSET
0,3
COMMENTS
As observed by Yuval Filmus, this also counts pairs (f,g) that satisfy g(f(x)) = f^{k}(x) for k >= 1. - Chad Brewbaker, Mar 27 2014
FORMULA
a(n) = Sum_{k=0..n} C(n,k) * k^n * (n-1)^(n-k) = Sum_{k=0..n} C(n,k) * A048993(n,k) * k! * n^(n-k). - Alois P. Heinz, Jul 23 2014
MAPLE
a:= n-> add(binomial(n, k)*k^n*(n-1)^(n-k), k=0..n):
seq(a(n), n=0..20); # Alois P. Heinz, Jul 23 2014
MATHEMATICA
a[n_] := If[n<2, 1, Sum[Binomial[n, k]*k^n*(n-1)^(n-k), {k, 0, n}]];
a /@ Range[0, 20] (* Jean-François Alcover, Oct 03 2019, after Alois P. Heinz *)
CROSSREFS
Column k=1 of A245980.
Sequence in context: A277337 A138216 A294491 * A245984 A245982 A294045
KEYWORD
nonn
AUTHOR
Chad Brewbaker, Mar 26 2014
EXTENSIONS
a(6)-a(7) from Giovanni Resta, Mar 26 2014
a(8)-a(16) from Alois P. Heinz, Jul 17 2014
STATUS
approved