login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000653 Invertible Boolean functions of n variables.
(Formerly M1821 N0723)
8
2, 7, 1172, 36325278240, 18272974787063551687986348306336, 244766458691906180755079840538506099505695351680436638205950721844523539763881615360 (list; graph; refs; listen; history; text; internal format)
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, M. ZivkovicTable of n, a(n) for n = 1..8

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

Marko Caric, 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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 12 05:33 EDT 2020. Contains 336438 sequences. (Running on oeis4.)