A000653 Invertible Boolean functions of n variables. (Formerly M1821 N0723)

2, 7, 1172, 36325278240, 18272974787063551687986348306336, 244766458691906180755079840538506099505695351680436638205950721844523539763881615360

Offset

1,1

Comments

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

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

M. Caric and M. Zivkovic, Table of n, a(n) for n = 1..8

M. Caric, Table of n, a(n) for n = 1..14

Marko Caric and Miodrag Živkovic, On the number of equivalence classes of invertible Boolean functions under action of permutation of variables on domain and range, arXiv:1603.04386 [math.CO], 2016.

M. A. Harrison, The number of classes of invertible Boolean functions, University of Michigan, Technical Note, 1962.

M. A. Harrison, The number of classes of invertible Boolean functions, J. ACM 10 (1963), 25-28.

M. A. Harrison, The number of classes of invertible Boolean functions, J. ACM 10 (1963), 25-28. [Annotated scan of page 27 only]

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]

Index entries for sequences related to Boolean functions

Mathematica

n = 20; (* the value of n is chosen here *)
e = Table[2, {n}]; (*the sequence e*)
Do[
DD = Divisors[k];
e[[k]] = (2^k - Sum[DD[[j]] e[[DD[[j]]]], {j, 1, Length[DD] - 1}])/
   k, {k, 2, n}]
PP = IntegerPartitions[n]; npp =
Length[PP]; (*the list of partitions of n*)
(*the maximum length of a cycle in sigma'*)
mlcm = Apply[Max, Table[Apply[LCM, PP[[p]]], {p, npp}]];
(*decompositions of n corresponding to partitions*)
P = Table[0, {i, npp}, {j, n}];
Do[Do[P[[ipp, PP[[ipp, i]]]]++, {i, Length[PP[[ipp]]]}], {ipp, npp}]
EmptyList = Table[0, {j, mlcm}]; (*used to initialize spec(sigma')*)
Vn = 0; Do[(*the main loop through all partitions of n*)
PPP = PP[[p]]; np = Length[PPP]; (*current partition*)
Spec = EmptyList; (*initialization of spec(sigma')*)
divsets = {};
nd = 1;
Do[(*k is the index of the current Partition element*)
  DD = Divisors[PPP[[k]]];
  AppendTo[divsets, DD];
  nd *= Length[DD], {k, 1, np}];
(*divsets is the list of the sets of divisors of cycle lengths in \
sigma*)
Descartes = Tuples[divsets]; (* nd is the length of Descartes *)
Do[ (*loop through Descartes product *)
  product = Descartes[[id]];
  npr = Length[product];
  lcm = 1; prx = 1; pry = 1;
  (* Theorem 2 *)
  Do[
   lcm = LCM[lcm, product[[ipr]]];
   prx *= product[[ipr]];
   pry *= e[[product[[ipr]]]], {ipr, npr}];
  Spec[[lcm]] += prx*pry/lcm, {id, nd}];
(* Theorem 1 *)
numerator = Product[i^Spec[[i]] Spec[[i]]!, {i, Length[Spec]}];
denominatorr = Product[i^P[[p, i]] P[[p, i]]!, {i, n}];
sum = numerator/denominatorr^2;
Vn += sum, {p, npp}]
Print[{"V_n = ", Vn}] (* Marko Caric, Jan 30 2016 *)

Crossrefs

Sequence in context: A051249 A056165 A082891 * A128847 A123180 A138198

Adjacent sequences: A000650 A000651 A000652 * A000654 A000655 A000656

Keyword

nonn

Author

N. J. A. Sloane

Extensions

a(6) from Sean A. Irvine, Mar 15 2011

Status

approved