login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000653 Invertible Boolean functions of n variables.
(Formerly M1821 N0723)
8

%I M1821 N0723 #55 Feb 13 2023 03:04:16

%S 2,7,1172,36325278240,18272974787063551687986348306336,

%T 244766458691906180755079840538506099505695351680436638205950721844523539763881615360

%N Invertible Boolean functions of n variables.

%C 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H M. Caric and M. Zivkovic, <a href="/A000653/b000653.txt">Table of n, a(n) for n = 1..8</a>

%H M. Caric, <a href="/A000653/a000653.txt">Table of n, a(n) for n = 1..14</a>

%H 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 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 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 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 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 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 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>

%t n = 20; (* the value of n is chosen here *)

%t e = Table[2, {n}];(*the sequence e*)

%t Do[

%t DD = Divisors[k];

%t e[[k]] = (2^k - Sum[DD[[j]] e[[DD[[j]]]], {j, 1, Length[DD] - 1}])/

%t k, {k, 2, n}]

%t PP = IntegerPartitions[n]; npp =

%t Length[PP];(*the list of partitions of n*)

%t (*the maximum length of a cycle in sigma'*)

%t mlcm = Apply[Max, Table[Apply[LCM, PP[[p]]], {p, npp}]];

%t (*decompositions of n corresponding to partitions*)

%t P = Table[0, {i, npp}, {j, n}];

%t Do[Do[P[[ipp, PP[[ipp, i]]]]++, {i, Length[PP[[ipp]]]}], {ipp, npp}]

%t EmptyList = Table[0, {j, mlcm}];(*used to initialize spec(sigma')*)

%t Vn = 0; Do[(*the main loop through all partitions of n*)

%t PPP = PP[[p]]; np = Length[PPP];(*current partition*)

%t Spec = EmptyList;(*initialization of spec(sigma')*)

%t divsets = {};

%t nd = 1;

%t Do[(*k is the index of the current Partition element*)

%t DD = Divisors[PPP[[k]]];

%t AppendTo[divsets, DD];

%t nd *= Length[DD], {k, 1, np}];

%t (*divsets is the list of the sets of divisors of cycle lengths in \

%t sigma*)

%t Descartes = Tuples[divsets]; (* nd is the length of Descartes *)

%t Do[ (*loop through Descartes product *)

%t product = Descartes[[id]];

%t npr = Length[product];

%t lcm = 1; prx = 1; pry = 1;

%t (* Theorem 2 *)

%t Do[

%t lcm = LCM[lcm, product[[ipr]]];

%t prx *= product[[ipr]];

%t pry *= e[[product[[ipr]]]], {ipr, npr}];

%t Spec[[lcm]] += prx*pry/lcm, {id, nd}];

%t (* Theorem 1 *)

%t numerator = Product[i^Spec[[i]] Spec[[i]]!, {i, Length[Spec]}];

%t denominatorr = Product[i^P[[p, i]] P[[p, i]]!, {i, n}];

%t sum = numerator/denominatorr^2;

%t Vn += sum, {p, npp}]

%t Print[{"V_n = ", Vn}] (* _Marko Caric_, Jan 30 2016 *)

%K nonn

%O 1,1

%A _N. J. A. Sloane_

%E a(6) from _Sean A. Irvine_, Mar 15 2011

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 00:26 EDT 2024. Contains 371264 sequences. (Running on oeis4.)