A214851 -id:A214851 - cp's OEIS frontend

A214854 Number of n-permutations that have exactly two square roots.

0, 0, 1, 0, 3, 35, 0, 714, 2835, 35307, 236880, 3342350, 28879158, 461911086, 4916519608, 87798024300, 1112716544355, 21957112744083, 322944848419392, 6986165252185782, 116941654550250258, 2754405555107729418, 51688464405692879688

Offset: 0

Geoffrey Critzer, Mar 08 2013

nonn

These permutations are of two types: They are composed of exactly one pair of equal even size cycles with at most one fixed point and any number of odd (>=3) size cycles; OR they are any number of odd (>=3) size cycles with exactly two fixed points.

			a(5) = 35 because we have 20 5-permutations of the type (1,2,3)(4)(5) and 15 of the type (1,2)(3,4)(5). These have 2 square roots:(1,3,2)(4)(5),(1,3,2)(4,5) and (1,3,2,4)(5),(3,1,4,2)(5) respectively.

Cf. A214849, A214851, A003483.

nn=22; a=Sum[Binomial[2n,n]/2x^(2n)/(2n)!, {n,2,nn,2}]; Range[0,nn]! CoefficientList[Series[(a(1+x)+x^2/2) ((1+x)/(1-x))^(1/2) Exp[-x], {x,0,nn}], x]

E.g.f.: (A(x)*(1+x)+x^2/2)*((1+x)/(1-x))^(1/2)*exp(-x) where A(x) = Sum_{n=2,4,6,8,...} Binomial(2n,n)/2 * x^(2n)/(2n)!

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.

Original entry on oeis.org

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

Steven Finch, Nov 23 2021

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.

			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;
...

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

Columns k=0-1 give: A000007, A005359(n-1).
Row sums give A003483.
T(n+2,n) gives A000914.
Cf. A214851, A246945.

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

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 *)

cp's OEIS Frontend

A214854 Number of n-permutations that have exactly two square roots.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula