cp's OEIS Frontend

A000653 Invertible Boolean functions of n variables.

%I A000653 M1821 N0723 #55 Feb 13 2023 03:04:16
%S A000653 2,7,1172,36325278240,18272974787063551687986348306336,
%T A000653 244766458691906180755079840538506099505695351680436638205950721844523539763881615360
%N A000653 Invertible Boolean functions of n variables.
%C A000653 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
%D A000653 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000653 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000653 M. Caric and M. Zivkovic, <a href="/A000653/b000653.txt">Table of n, a(n) for n = 1..8</a>
%H A000653 M. Caric, <a href="/A000653/a000653.txt">Table of n, a(n) for n = 1..14</a>
%H A000653 Marko Caric and Miodrag Živkovic, <a href="http://arxiv.org/abs/1603.04386">On the number of equivalence classes of invertible Boolean functions under action of permutation of variables on domain and range</a>, arXiv:1603.04386 [math.CO], 2016.
%H A000653 M. A. Harrison, <a href="http://hdl.handle.net/2027.42/5402">The number of classes of invertible Boolean functions</a>, University of Michigan, Technical Note, 1962.
%H A000653 M. A. Harrison, <a href="http://dx.doi.org/10.1145/321150.321152">The number of classes of invertible Boolean functions</a>, J. ACM 10 (1963), 25-28.
%H A000653 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 A000653 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 A000653 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 A000653 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%t A000653 n = 20; (* the value of n is chosen here *)
%t A000653 e = Table[2, {n}];(*the sequence e*)
%t A000653 Do[
%t A000653 DD = Divisors[k];
%t A000653 e[[k]] = (2^k - Sum[DD[[j]] e[[DD[[j]]]], {j, 1, Length[DD] - 1}])/
%t A000653    k, {k, 2, n}]
%t A000653 PP = IntegerPartitions[n]; npp =
%t A000653 Length[PP];(*the list of partitions of n*)
%t A000653 (*the maximum length of a cycle in sigma'*)
%t A000653 mlcm = Apply[Max, Table[Apply[LCM, PP[[p]]], {p, npp}]];
%t A000653 (*decompositions of n corresponding to partitions*)
%t A000653 P = Table[0, {i, npp}, {j, n}];
%t A000653 Do[Do[P[[ipp, PP[[ipp, i]]]]++, {i, Length[PP[[ipp]]]}], {ipp, npp}]
%t A000653 EmptyList = Table[0, {j, mlcm}];(*used to initialize spec(sigma')*)
%t A000653 Vn = 0; Do[(*the main loop through all partitions of n*)
%t A000653 PPP = PP[[p]]; np = Length[PPP];(*current partition*)
%t A000653 Spec = EmptyList;(*initialization of spec(sigma')*)
%t A000653 divsets = {};
%t A000653 nd = 1;
%t A000653 Do[(*k is the index of the current Partition element*)
%t A000653   DD = Divisors[PPP[[k]]];
%t A000653   AppendTo[divsets, DD];
%t A000653   nd *= Length[DD], {k, 1, np}];
%t A000653 (*divsets is the list of the sets of divisors of cycle lengths in \
%t A000653 sigma*)
%t A000653 Descartes = Tuples[divsets]; (* nd is the length of Descartes *)
%t A000653 Do[ (*loop through Descartes product *)
%t A000653   product = Descartes[[id]];
%t A000653   npr = Length[product];
%t A000653   lcm = 1; prx = 1; pry = 1;
%t A000653   (* Theorem 2 *)
%t A000653   Do[
%t A000653    lcm = LCM[lcm, product[[ipr]]];
%t A000653    prx *= product[[ipr]];
%t A000653    pry *= e[[product[[ipr]]]], {ipr, npr}];
%t A000653   Spec[[lcm]] += prx*pry/lcm, {id, nd}];
%t A000653 (* Theorem 1 *)
%t A000653 numerator = Product[i^Spec[[i]] Spec[[i]]!, {i, Length[Spec]}];
%t A000653 denominatorr = Product[i^P[[p, i]] P[[p, i]]!, {i, n}];
%t A000653 sum = numerator/denominatorr^2;
%t A000653 Vn += sum, {p, npp}]
%t A000653 Print[{"V_n = ", Vn}] (* _Marko Caric_, Jan 30 2016 *)
%K A000653 nonn
%O A000653 1,1
%A A000653 _N. J. A. Sloane_
%E A000653 a(6) from _Sean A. Irvine_, Mar 15 2011