cp's OEIS Frontend

A000654 Invertible Boolean functions of n variables.

%I A000654 M2173 N0868 #45 Jun 11 2025 17:51:46
%S A000654 1,2,52,142090700,17844701940501123640681816160,
%T A000654 59757436204078657410908164193971330396709572693816353610758085074676243846093824
%N A000654 Invertible Boolean functions of n variables.
%C A000654 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
%D A000654 M. A. Harrison, The number of classes of invertible Boolean functions, J. ACM 10 (1963), 25-28.
%D A000654 C. S. Lorens, Invertible Boolean functions, IEEE Trans. Electron. Computers, EC-13 (1964), 529-541.
%D A000654 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000654 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000654 Adam P. Goucher, <a href="/A000654/b000654.txt">Table of n, a(n) for n = 1..7</a>
%H A000654 M. A. Harrison, <a href="/A000653/a000653.pdf">The number of classes of invertible Boolean functions</a>, J. ACM 10 (1963), 25-28. [Annotated scan of page 27 only]
%H A000654 M. A. Harrison, <a href="/A000370/a000370.pdf">The number of equivalence classes of Boolean functions under groups containing negation</a>, IEEE Trans. Electron. Comput. 12 (1963), 559-561. [Annotated scanned copy]
%H A000654 C. S. Lorens, <a href="http://dx.doi.org/10.1109/PGEC.1964.263724">Invertible Boolean functions</a>, IEEE Trans. Electron. Computers, EC-13 (1964), 529-541.
%H A000654 C. S. Lorens, <a href="/A000722/a000722.pdf">Invertible Boolean functions</a>, IEEE Trans. Electron. Computers, EC-13 (1964), 529-541. [Annotated scan of page 530 only]
%H A000654 Qing-bin Luo, Jin-zhao Wu, and Chen Lin, <a href="https://doi.org/10.1007/s10773-020-04508-y">Computing the Number of the Equivalence Classes for Reversible Logic Functions</a>, Int'l J. of Theor. Phys. (2020) Vol. 59, 2384-2396.
%H A000654 Ludovic Schwob, <a href="https://arxiv.org/abs/2506.04007">On the enumeration of double cosets and self-inverse double cosets</a>, arXiv:2506.04007 [math.CO], 2025. See p. 10.
%H A000654 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%t A000654 cyclify =
%t A000654   Function[{x},
%t A000654    Sort@Tally[Length /@ PermutationCycles[x + 1, Identity]]];
%t A000654 totalweight =
%t A000654   Function[{c}, Product[(x[[1]]^x[[2]]) ( x[[2]]!), {x, c}]];
%t A000654 perms = Function[{n},
%t A000654    Flatten[Table[
%t A000654      FromDigits[Permute[IntegerDigits[BitXor[x, a], 2, n], sigma],
%t A000654       2], {sigma, Permutations[Range[n]]}, {a, 0, 2^n - 1}, {x, 0,
%t A000654       2^n - 1}], 1]];
%t A000654 countit =
%t A000654   Function[{n},
%t A000654    Sum[totalweight[x[[1]]] (x[[2]]^2), {x,
%t A000654       Tally[cyclify /@ perms[n]]}]/((2^n) (n!))^2];
%t A000654 Table[countit[n], {n, 1, 5}] (*  _Adam P. Goucher_, Feb 12 2021 *)
%K A000654 nonn
%O A000654 1,2
%A A000654 _N. J. A. Sloane_
%E A000654 More terms from _Sean A. Irvine_, Mar 15 2011