|
%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
| 