A332759 Number of involutions (plus identity) in a fixed Sylow 2-subgroup of the symmetric group of degree n.

1, 1, 2, 2, 6, 6, 12, 12, 44, 44, 88, 88, 264, 264, 528, 528, 2064, 2064, 4128, 4128, 12384, 12384, 24768, 24768, 90816, 90816, 181632, 181632, 544896, 544896, 1089792, 1089792, 4292864, 4292864, 8585728, 8585728, 25757184, 25757184, 51514368, 51514368

Offset

0,3

Comments

As the Sylow 2-subgroups of S_(2n) are isomorphic to those of S_(2n+1), the terms of this sequence come in pairs.

Also the number of involutory automorphisms (including identity) of the full binary tree with n leaves (hence 2n-1 vertices) in which all left children are complete (perfect) binary trees.

Links

Table of n, a(n) for n=0..39.

Formula

a(n) = Product(A332757(k)) where k ranges over the positions of 1 bits in the binary expansion of n.

a(n) = big-Theta(C^n) for C = 1.6116626399..., i.e., A*C^n < a(n) < B*C^n for constants A, B (but it's not the case that a(n) ~ C^n as lim inf a(n)/C^n and lim sup a(n)/C^n differ).

Conjecture: B=1 and A=0.409091077245262341747187571213565366725933766222357989... - Vaclav Kotesovec, Feb 26 2020

Example

For n=4, the a(4)=6 elements satisfying x^2=1 in a fixed Sylow 2-subgroup of S_4 (which subgroup is isomorphic to the dihedral group of degree 4) are the identity and (13), (24), (12)(34), (13)(24), (14)(23).

Maple

b:= proc(n) b(n):=`if`(n=0, 1, b(n-1)^2+2^(2^(n-1)-1)) end:
a:= n-> (l-> mul(`if`(l[i]=1, b(i-1), 1), i=1..nops(l)))(Bits[Split](n)):
seq(a(n), n=0..50);  # Alois P. Heinz, Feb 27 2020

Mathematica

Join[{1}, Block[{nn = 33, s}, s = Nest[Append[#1, #1[[-1]]^2 + 2^(2^(#2 - 1) - 1)] & @@ {#, Length@ #} &, {1}, Ceiling@ Log2@ nn]; Array[Times @@ s[[Position[Reverse@ IntegerDigits[#, 2], 1][[All, 1]] ]] &, nn]]] (* Michael De Vlieger, Feb 25 2020 *)

Crossrefs

Cf. A000085.

Sequence in context: A179478 A051548 A110660 * A139550 A337735 A060549

Adjacent sequences: A332756 A332757 A332758 * A332760 A332761 A332762

Keyword

nonn

Author

Nick Krempel, Feb 22 2020

Extensions

More terms from Alois P. Heinz, Feb 27 2020

Status

approved