A005388 Number of degree-n permutations of order a power of 2. (Formerly M1293)

1, 1, 2, 4, 16, 56, 256, 1072, 11264, 78976, 672256, 4653056, 49810432, 433429504, 4448608256, 39221579776, 1914926104576, 29475151020032, 501759779405824, 6238907914387456, 120652091860975616, 1751735807564578816, 29062253310781161472, 398033706586943258624

Offset

0,3

Comments

Differs from A053503 first at n=32. - Alois P. Heinz, Feb 14 2013

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.10.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

J. M. Møller, Euler characteristics of equivariant subcategories, arXiv preprint arXiv:1502.01317, 2015. See page 20.

L. Moser and M. Wyman, On solutions of x^d = 1 in symmetric groups, Canad. J. Math., 7 (1955), 159-168.

A. Recski, Enumerating partitional matroids, Preprint.

A. Recski & N. J. A. Sloane, Correspondence, 1975

Formula

E.g.f.: exp(Sum_{m>=0} x^(2^m)/2^m).

E.g.f.: 1/Product_{k>=1} (1 - x^(2*k-1))^(mu(2*k-1)/(2*k-1)), where mu() is the Moebius function. - Seiichi Manyama, Jul 06 2024

Maple

a:= proc(n) option remember; `if`(n<0, 0, `if`(n=0, 1,
       add(mul(n-i, i=1..2^j-1)*a(n-2^j), j=0..ilog2(n))))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Feb 14 2013

Mathematica

max = 23; CoefficientList[ Series[ Exp[ Sum[x^2^m/2^m, {m, 0, max}]], {x, 0, max}], x]*Range[0, max]! (* Jean-François Alcover, Sep 10 2013 *)

Prog

(Magma)
R<x>:=PowerSeriesRing(Rationals(), 40);
f:= func< x | Exp( (&+[x^(2^j)/2^j: j in [0..14]]) ) >;
Coefficients(R!(Laplace( f(x) ))); // G. C. Greubel, Nov 17 2022
(SageMath)
def f(x): return exp(sum(x^(2^j)/2^j for j in range(15)))
def A005388_list(prec):
    P.<x> = PowerSeriesRing(QQ, prec)
    return P( f(x) ).egf_to_ogf().list()
A005388_list(40) # G. C. Greubel, Nov 17 2022

Crossrefs

Cf. A000085, A001470, A001472, A053495, A053496, A053497, A053498, A053499.

Cf. A053500, A053501, A053502, A053503, A053504, A053505.

Sequence in context: A306519 A001472 A053498 * A053503 A308381 A153957

Adjacent sequences: A005385 A005386 A005387 * A005389 A005390 A005391

Keyword

nonn,nice,easy

Author

N. J. A. Sloane and J. H. Conway

Status

approved