cp's OEIS Frontend

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.

%I A349645 #35 Dec 28 2021 14:51:15
%S A349645 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,
%T A349645 0,994,0,175,0,1,0,0,9708,0,4249,0,322,0,1,0,40320,0,72764,0,14889,0,
%U A349645 546,0,1,0,0,648576,0,402380,0,44373,0,870,0,1
%N 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.
%C A349645 A permutation p in S_n is a square if there exists q in S_n with q^2=p.
%C A349645 For such a p, the number of cycles of any even length in its disjoint cycle decomposition must be even.
%H A349645 Alois P. Heinz, <a href="/A349645/b349645.txt">Rows n = 0..200, flattened</a>
%H A349645 Steven Finch, <a href="https://arxiv.org/abs/2111.14487">Rounds, Color, Parity, Squares</a>, arXiv:2111.14487 [math.CO], 2021.
%e A349645 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.
%e A349645 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.
%e A349645 Triangle begins:
%e A349645 [0]   1;
%e A349645 [1]   0,   1;
%e A349645 [2]   0,   0,    1;
%e A349645 [3]   0,   2,    0,   1;
%e A349645 [4]   0,   0,   11,   0,    1;
%e A349645 [5]   0,  24,    0,  35,    0,   1;
%e A349645 [6]   0,   0,  184,   0,   85,   0,   1;
%e A349645 [7]   0, 720,    0, 994,    0, 175,   0,   1;
%e A349645 [8]   0,   0, 9708,   0, 4249,   0, 322,   0,   1;
%e A349645 ...
%p A349645 with(combinat):
%p A349645 b:= proc(n, i) option remember; expand(`if`(n=0, 1, `if`(i<1, 0,
%p A349645       add(`if`(irem(i, 2)=0 and irem(j, 2)=1, 0, (i-1)!^j*
%p A349645       multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1))*x^j, j=0..n/i))))
%p A349645     end:
%p A349645 T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2)):
%p A349645 seq(T(n), n=0..12);  # _Alois P. Heinz_, Nov 23 2021
%t A349645 multinomial[n_, k_List] := n!/Times @@ (k!);
%t A349645 b[n_, i_] := b[n, i] = Expand[If[n == 0, 1, If[i < 1, 0,
%t A349645      Sum[If[Mod[i, 2] == 0 && Mod[j, 2] == 1, 0, (i-1)!^j*multinomial[n,
%t A349645      Join[{n-i*j}, Table[i, {j}]]]/j!*b[n-i*j, i-1]]*x^j, {j, 0, n/i}]]]];
%t A349645 T[n_] := With[{p = b[n, n]}, Table[Coefficient[p, x, i], {i, 0, n}]];
%t A349645 Table[T[n], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Dec 28 2021, after _Alois P. Heinz_ *)
%Y A349645 Columns k=0-1 give: A000007, A005359(n-1).
%Y A349645 Row sums give A003483.
%Y A349645 T(n+2,n) gives A000914.
%Y A349645 Cf. A214851, A246945.
%K A349645 nonn,tabl
%O A349645 0,8
%A A349645 _Steven Finch_, Nov 23 2021