A001691 Number of two-element generating sets in the symmetric group S_n.

0, 1, 9, 108, 3420, 114480, 7786800, 497266560, 42616445760, 4320959126400, 534444478444800, 77699101730342400, 13282131639801024000

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• more

References

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

Links

• J. Denes, Some combinatorial properties of transformations and their connections with the theory of graphs, J. Combin. Theory, 9 (1970), 108-116.

Crossrefs

Cf. A071605, A086373.

Programs

GAP

a := function(n)
  local tom, mu, lens, orders, num, k;
  tom := TableOfMarks(Concatenation("S",String(n)));
  if tom = fail then tom := TableOfMarks(SymmetricGroup(n)); fi;
  mu :=  MoebiusTom(tom).mu;
  lens := LengthsTom(tom);
  orders := OrdersTom(tom);
  num := 0;
  for k in [1 .. Length(lens)] do
    if IsBound(mu[k]) then
      num := num + mu[k] * lens[k] * Binomial(orders[k],2);
    fi;
  od;
  return num;
end; # Stephen A. Silver, Feb 20 2013

Formula

a(n) = A071605(n)/2 for n > 2.

Extensions

a(8)-a(9) (derived from A071605) added by Stephen A. Silver, Feb 17 2013

a(10)-a(13) added by Stephen A. Silver, Feb 20 2013