A000654 Invertible Boolean functions of n variables.

1, 2, 52, 142090700, 17844701940501123640681816160, 59757436204078657410908164193971330396709572693816353610758085074676243846093824

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Equivalence classes of invertible maps from {0,1}^n to {0,1}^n, under action of permutation and complementation of variables on domain and range. - Sean A. Irvine, Mar 16 2011

References

• M. A. Harrison, The number of classes of invertible Boolean functions, J. ACM 10 (1963), 25-28.
• C. S. Lorens, Invertible Boolean functions, IEEE Trans. Electron. Computers, EC-13 (1964), 529-541.
• 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

• Adam P. Goucher, Table of n, a(n) for n = 1..7
• M. A. Harrison, The number of classes of invertible Boolean functions, J. ACM 10 (1963), 25-28. [Annotated scan of page 27 only]
• M. A. Harrison, The number of equivalence classes of Boolean functions under groups containing negation, IEEE Trans. Electron. Comput. 12 (1963), 559-561. [Annotated scanned copy]
• C. S. Lorens, Invertible Boolean functions, IEEE Trans. Electron. Computers, EC-13 (1964), 529-541.
• C. S. Lorens, Invertible Boolean functions, IEEE Trans. Electron. Computers, EC-13 (1964), 529-541. [Annotated scan of page 530 only]
• Qing-bin Luo, Jin-zhao Wu, and Chen Lin, Computing the Number of the Equivalence Classes for Reversible Logic Functions, Int'l J. of Theor. Phys. (2020) Vol. 59, 2384-2396.
• Ludovic Schwob, On the enumeration of double cosets and self-inverse double cosets, arXiv:2506.04007 [math.CO], 2025. See p. 10.
• Index entries for sequences related to Boolean functions

Programs

Mathematica

cyclify =
  Function[{x},
   Sort@Tally[Length /@ PermutationCycles[x + 1, Identity]]];
totalweight =
  Function[{c}, Product[(x[[1]]^x[[2]]) ( x[[2]]!), {x, c}]];
perms = Function[{n},
   Flatten[Table[
     FromDigits[Permute[IntegerDigits[BitXor[x, a], 2, n], sigma],
      2], {sigma, Permutations[Range[n]]}, {a, 0, 2^n - 1}, {x, 0,
      2^n - 1}], 1]];
countit =
  Function[{n},
   Sum[totalweight[x[[1]]] (x[[2]]^2), {x,
      Tally[cyclify /@ perms[n]]}]/((2^n) (n!))^2];
Table[countit[n], {n, 1, 5}] (*  Adam P. Goucher, Feb 12 2021 *)

Extensions

More terms from Sean A. Irvine, Mar 15 2011