login
Number of pairs (f,g) of commuting maps {0,..,n-1}->{0,..,n-1} with 0 <= f(k), g(k) <= k.
0

%I #18 Dec 26 2023 03:28:53

%S 1,1,4,26,236,2780,40642,715836,14873174,358866952,9934283924,

%T 312461402424

%N Number of pairs (f,g) of commuting maps {0,..,n-1}->{0,..,n-1} with 0 <= f(k), g(k) <= k.

%e The a(3) = 26 pairs of such maps are (dots for zeros in the maps):

%e 01: [ . . . ] [ . . . ]

%e 02: [ . . . ] [ . . 1 ]

%e 03: [ . . . ] [ . . 2 ]

%e 04: [ . . . ] [ . 1 . ]

%e 05: [ . . . ] [ . 1 1 ]

%e 06: [ . . . ] [ . 1 2 ]

%e 07: [ . . 1 ] [ . . . ]

%e 08: [ . . 1 ] [ . . 1 ]

%e 09: [ . . 1 ] [ . 1 2 ]

%e 10: [ . . 2 ] [ . . . ]

%e 11: [ . . 2 ] [ . . 2 ]

%e 12: [ . . 2 ] [ . 1 . ]

%e 13: [ . . 2 ] [ . 1 2 ]

%e 14: [ . 1 . ] [ . . . ]

%e 15: [ . 1 . ] [ . . 2 ]

%e 16: [ . 1 . ] [ . 1 . ]

%e 17: [ . 1 . ] [ . 1 2 ]

%e 18: [ . 1 1 ] [ . . . ]

%e 19: [ . 1 1 ] [ . 1 1 ]

%e 20: [ . 1 1 ] [ . 1 2 ]

%e 21: [ . 1 2 ] [ . . . ]

%e 22: [ . 1 2 ] [ . . 1 ]

%e 23: [ . 1 2 ] [ . . 2 ]

%e 24: [ . 1 2 ] [ . 1 . ]

%e 25: [ . 1 2 ] [ . 1 1 ]

%e 26: [ . 1 2 ] [ . 1 2 ]

%p s:= proc(n) option remember; `if`(n=0, [[]],

%p map(x-> seq([x[], i], i=1..n), s(n-1)))

%p end:

%p a:= n-> (l-> add(add(`if`([seq(evalb(f[g[i]]=g[f[i]])

%p , i=1..n)]=[true$n], 1, 0), g=l), f=l))(s(n)):

%p seq(a(n), n=0..6); # _Alois P. Heinz_, Jul 30 2014

%Y Cf. A181162 (commuting maps {{1,..,n}->{1,..,n} without restrictions).

%Y Cf. A053529 (commuting permutations).

%K nonn,hard,more

%O 0,3

%A _Joerg Arndt_, Jul 25 2014

%E All terms corrected (error pointed out by _Alois P. Heinz_), _Joerg Arndt_, Jul 30 2014

%E a(10)-a(11) from _Alois P. Heinz_, Jul 30 2014