A362819 Number of ordered pairs of involutions on [n] that commute.

1, 1, 4, 10, 52, 196, 1216, 5944, 42400, 250912, 2008576, 13815616, 122074624, 950640640, 9158267392, 79258479616, 824644235776, 7823203807744, 87245790791680, 897748312609792, 10665239974537216, 118040852776093696, 1486172381689544704, 17572063073426206720, 233446797379437248512

Offset

0,3

Comments

Two involutions x,y on [n] commute if x*y = y*x (i.e. x(y(i)) = y(x(i)) for i in [n]).

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

Formula

a(n) = Sum_{k=0..floor(n/2)} A000085(n-2*k) * A000898(k) * binomial(n,2*k) * (2*k)! / (k!*2^k).

E.g.f.: exp(x + 3*x^2/2 + x^4/4).

Prog

(PARI) b(n, f) = {sum(k=0, n\2, f(k)*binomial(n, 2*k)*(2*k)!/(k!*2^k))}
a(n) = {b(n, k->b(n-2*k, j->1)*b(k, j->2^(k-j)))}
(PARI) seq(n)=Vec(serlaplace(exp(x + 3*x^2/2 + x^4/4 + O(x*x^n))))

Crossrefs

Column k=2 of A362824.

A053529 is the corresponding sequence for all permutations.

Cf. A000085, A000898, A181162, A362820, A362825.

Sequence in context: A208236 A032495 A109387 * A018844 A007027 A192444

Adjacent sequences: A362816 A362817 A362818 * A362820 A362821 A362822

Keyword

nonn

Author

Andrew Howroyd, May 05 2023

Status

approved