A349645 Triangular array read by rows: T(n,k) is the number of square n-permutations possessing exactly k cycles; n >= 0, 0 <= k <= n.

1, 0, 1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 11, 0, 1, 0, 24, 0, 35, 0, 1, 0, 0, 184, 0, 85, 0, 1, 0, 720, 0, 994, 0, 175, 0, 1, 0, 0, 9708, 0, 4249, 0, 322, 0, 1, 0, 40320, 0, 72764, 0, 14889, 0, 546, 0, 1, 0, 0, 648576, 0, 402380, 0, 44373, 0, 870, 0, 1

Offset: 0

Author

Steven Finch, Nov 23 2021

Keywords

• nonn
• tabl

Comments

A permutation p in S_n is a square if there exists q in S_n with q^2=p.

For such a p, the number of cycles of any even length in its disjoint cycle decomposition must be even.

Examples

			The three square 3-permutations are (1, 2, 3) with three cycles (fixed points) and (3, 1, 2) & (2, 3, 1), each with one cycle.
Among the twelve square 4-permutations are {1, 4, 2, 3} & {1, 3, 4, 2} and {3, 4, 1, 2} & {4, 3, 2, 1}, all with two cycles but differing types.
Triangle begins:
[0]   1;
[1]   0,   1;
[2]   0,   0,    1;
[3]   0,   2,    0,   1;
[4]   0,   0,   11,   0,    1;
[5]   0,  24,    0,  35,    0,   1;
[6]   0,   0,  184,   0,   85,   0,   1;
[7]   0, 720,    0, 994,    0, 175,   0,   1;
[8]   0,   0, 9708,   0, 4249,   0, 322,   0,   1;
...
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened
• Steven Finch, Rounds, Color, Parity, Squares, arXiv:2111.14487 [math.CO], 2021.

Crossrefs

Columns k=0-1 give: A000007, A005359(n-1).

Row sums give A003483.

T(n+2,n) gives A000914.

Cf. A214851, A246945.

Programs

Maple

with(combinat):
b:= proc(n, i) option remember; expand(`if`(n=0, 1, `if`(i<1, 0,
      add(`if`(irem(i, 2)=0 and irem(j, 2)=1, 0, (i-1)!^j*
      multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1))*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Nov 23 2021

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = Expand[If[n == 0, 1, If[i < 1, 0,
     Sum[If[Mod[i, 2] == 0 && Mod[j, 2] == 1, 0, (i-1)!^j*multinomial[n,
     Join[{n-i*j}, Table[i, {j}]]]/j!*b[n-i*j, i-1]]*x^j, {j, 0, n/i}]]]];
T[n_] := With[{p = b[n, n]}, Table[Coefficient[p, x, i], {i, 0, n}]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 28 2021, after Alois P. Heinz *)