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

1, 1, 4, 26, 236, 2780, 40642, 715836, 14873174, 358866952, 9934283924, 312461402424

Offset: 0

Author

Joerg Arndt, Jul 25 2014

Keywords

• nonn
• hard
• more

Examples

			The a(3) = 26 pairs of such maps are (dots for zeros in the maps):
01:  [ . . . ]  [ . . . ]
02:  [ . . . ]  [ . . 1 ]
03:  [ . . . ]  [ . . 2 ]
04:  [ . . . ]  [ . 1 . ]
05:  [ . . . ]  [ . 1 1 ]
06:  [ . . . ]  [ . 1 2 ]
07:  [ . . 1 ]  [ . . . ]
08:  [ . . 1 ]  [ . . 1 ]
09:  [ . . 1 ]  [ . 1 2 ]
10:  [ . . 2 ]  [ . . . ]
11:  [ . . 2 ]  [ . . 2 ]
12:  [ . . 2 ]  [ . 1 . ]
13:  [ . . 2 ]  [ . 1 2 ]
14:  [ . 1 . ]  [ . . . ]
15:  [ . 1 . ]  [ . . 2 ]
16:  [ . 1 . ]  [ . 1 . ]
17:  [ . 1 . ]  [ . 1 2 ]
18:  [ . 1 1 ]  [ . . . ]
19:  [ . 1 1 ]  [ . 1 1 ]
20:  [ . 1 1 ]  [ . 1 2 ]
21:  [ . 1 2 ]  [ . . . ]
22:  [ . 1 2 ]  [ . . 1 ]
23:  [ . 1 2 ]  [ . . 2 ]
24:  [ . 1 2 ]  [ . 1 . ]
25:  [ . 1 2 ]  [ . 1 1 ]
26:  [ . 1 2 ]  [ . 1 2 ]
		

Crossrefs

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

Cf. A053529 (commuting permutations).

Programs

Maple

s:= proc(n) option remember; `if`(n=0, [[]],
       map(x-> seq([x[], i], i=1..n), s(n-1)))
    end:
a:= n-> (l-> add(add(`if`([seq(evalb(f[g[i]]=g[f[i]])
    , i=1..n)]=[true$n], 1, 0), g=l), f=l))(s(n)):
seq(a(n), n=0..6);  # Alois P. Heinz, Jul 30 2014

Extensions

All terms corrected (error pointed out by Alois P. Heinz), Joerg Arndt, Jul 30 2014

a(10)-a(11) from Alois P. Heinz, Jul 30 2014