A332840 Number of fixed-point free involutions in a fixed Sylow 2-subgroup of the symmetric group of degree 2n.

1, 1, 3, 3, 17, 17, 51, 51, 417, 417, 1251, 1251, 7089, 7089, 21267, 21267, 206657, 206657, 619971, 619971, 3513169, 3513169, 10539507, 10539507, 86175969, 86175969, 258527907, 258527907, 1464991473, 1464991473, 4394974419, 4394974419, 44854599297, 44854599297, 134563797891

Offset

0,3

Comments

As a Sylow 2-subgroup of S_(4n+2) is isomorphic to a Sylow 2-subgroup of S_(4n) direct product C_2, the terms of this sequence come in equal pairs.

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

Links

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

Formula

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

a(n) = big-Theta(C^n) for C = 2.1522868238..., 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).

a(n) = A332869(floor(n/2)). - Andrew Howroyd, Feb 27 2020

Example

For n=2, the a(2)=3 fixed-point free involutions in a fixed Sylow 2-subgroup of S_4 (which subgroup is isomorphic to the dihedral group of degree 4) are (12)(34), (13)(24), and (14)(23).

Maple

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

Mathematica

A332758[n_] := A332758[n] = If[n == 0, 0, A332758[n-1]^2 + 2^(2^(n-1)-1)];
a[n_] := Product[A332758[k], {k, Flatten@ Position[ Reverse@ IntegerDigits[ n, 2], 1]}];
a /@ Range[0, 34] (* Jean-François Alcover, Apr 10 2020 *)

Prog

(PARI) a(n)={my(v=vector(logint(max(1, n), 2)+1)); v[1]=1; for(n=2, #v, v[n]=v[n-1]^2 + 2^(2^(n-1)-1)); prod(k=1, #v, if(bittest(n, k-1), v[k], 1))} \\ Andrew Howroyd, Feb 27 2020

Crossrefs

Cf. A123023, A001147, A332758, A332869.

Sequence in context: A278627 A231908 A226610 * A279172 A268339 A224750

Adjacent sequences: A332837 A332838 A332839 * A332841 A332842 A332843

Keyword

nonn

Author

Nick Krempel, Feb 26 2020

Extensions

Terms a(18) and beyond from Andrew Howroyd, Feb 27 2020

Status

approved