A109456 Number of Boolean functions of n variables that are self-dual and regular.

0, 1, 1, 2, 3, 7, 21, 135, 2470, 319124, 1214554343, 1706241214185942

Offset: 0

Author

Don Knuth, Aug 17 2005

Keywords

• nonn
• hard
• more

Comments

Or, number of self-dual 2-monotonic Boolean functions of n or fewer variables.

Agrees with A001532 for n <= 8 but then diverges.

The value for n=10 was calculated with BDD techniques; all solutions are characterized by a binary decision diagram with 30011986 nodes.

The value for n=11 was calculated by Minfeng Wang in May 2012 (see [Hausmann & Rodriguez]). The news was published by J.-C. Hausmann (2015). - Fabián Riquelme, Mar 19 2018

For n from 1 to 9, a(n) agrees with the number of directed zero-sum games with n players in Table 1 of Krohn and Sudhölter. - Peter Bala, Dec 16 2021

References

• D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.1 (in preparation).

Links

• Jean-Claude Hausmann, Counting polygon spaces, Boolean functions and majority games, arXiv preprint arXiv:1501.07553 [math.CO], 2015.
• Jean-Claude Hausmann and Eugenio Rodriguez, The space of clouds in an Euclidean space, Corrections and additional material, 2014.
• I. Krohn and P. Sudhölter, Directed and weighted majority games, Mathematical Methods of Operation Research, 42, 2 (1995), 189-216. See Table 1, row 4, p. 213; also on ResearchGate.
• S. Muroga, T. Tsuboi and C. R. Baugh, Enumeration of threshold functions of eight variables, IEEE Trans. Computers, 19 (1970), 818-825.

Extensions

a(10) from Don Knuth, Feb 06 2008

a(11) from Fabián Riquelme, Mar 27 2018