A000653 Invertible Boolean functions of n variables.
2, 7, 1172, 36325278240, 18272974787063551687986348306336, 244766458691906180755079840538506099505695351680436638205950721844523539763881615360
Offset: 1
Keywords
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
Programs
-
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 *)
Extensions
a(6) from Sean A. Irvine, Mar 15 2011
Comments