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
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 and M. Zivkovic, Table of n, a(n) for n = 1..8
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]
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
KEYWORD
nonn
AUTHOR
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 17 08:54 EDT 2024. Contains 371763 sequences. (Running on oeis4.)