A239777 Number of pairs of functions f, g on a size n set into itself satisfying f(g(g(x))) = f(x).

1, 1, 12, 249, 7744, 326745, 17773056, 1197261289, 97165842432, 9294416254161, 1030298497753600, 130527793649586201, 18685034341191917568, 2993332161753700720681, 532270629438646194561024, 104316725427708352041239625, 22394627939996943667912769536

Offset: 0

Author

Chad Brewbaker, Mar 26 2014

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..200

Crossrefs

Cf. A181162, A239769, A239773.

Column k=2 of A245910.

Programs

Maple

s:= proc(n, i) option remember; `if`(i=0, [[]],
       map(x-> seq([j, x[]], j=1..n), s(n, i-1)))
    end:
a:= proc(n) (l-> add(add(`if`([true$n]=[seq(evalb(
       f[g[g[i]]]=f[i]), i=1..n)], 1, 0), g=l), f=l))(s(n$2))
    end:
seq(a(n), n=0..5);  # Alois P. Heinz, Jul 16 2014
# second Maple program:
with(combinat):
b:= proc(n, i) option remember; `if`(n=0 or i=1, x^n,
      expand(add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!
       *x^((2-irem(i, 2))*j)*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> add((p-> add(n^i*binomial(n-1, k-1)*n^(n-k)*
    coeff(p, x, i), i=0..degree(p)))(b(k$2)), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 06 2014

Mathematica

c[n_] := c[n] =
    Sum[(n - 1)! n^(n - k)/(n - k)! t^(1 + Mod[k + 1, 2]), {k, 1, n}]
d[0] = 1
d[n_] := d[n] = Sum[Binomial[n - 1, k]*d[k]*c[n - k], {k, 0, n - 1}]
a[n_] := d[n] /. t -> n
Table[a[n], {n, 1, 10}] (* David Einstein, Nov 02 2016*)

Extensions

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

a(8)-a(16) from Alois P. Heinz, Aug 06 2014