A239750 Number of ordered pairs of endofunctions (f,g) on a set of n elements satisfying g(f(x)) = f(f(f(x))).

1, 1, 6, 87, 2200, 84245, 4492656, 315937195, 28186856832, 3099006365769, 410478164588800, 64323095036300111, 11748771067445148672, 2470422069374379054493, 591735532838657160296448, 160004357420756572368889875, 48458574881000820765562863616

Offset: 0

Author

Chad Brewbaker, Mar 26 2014

Keywords

• nonn

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..200
• Yuval Filmus, Answer to 'A curious Wilf equivalence class of function compositions', Mar 27 2014

Crossrefs

Cf. A000248, A000949, A048993, A181162, A241015.

Column k=1 of A245980.

Programs

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 *)

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

Extensions

a(6)-a(7) from Giovanni Resta, Mar 26 2014

a(8)-a(16) from Alois P. Heinz, Jul 17 2014