login
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
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,8
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.
LINKS
Steven Finch, Rounds, Color, Parity, Squares, arXiv:2111.14487 [math.CO], 2021.
EXAMPLE
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;
...
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 *)
CROSSREFS
Columns k=0-1 give: A000007, A005359(n-1).
Row sums give A003483.
T(n+2,n) gives A000914.
Sequence in context: A111593 A111594 A322549 * A237996 A203951 A323591
KEYWORD
nonn,tabl
AUTHOR
Steven Finch, Nov 23 2021
STATUS
approved