A001532 Number of NP-equivalence classes of self-dual threshold functions of n or fewer variables ; number of majority (i.e., decisive and weighted) games with n players.
1, 1, 2, 3, 7, 21, 135, 2470, 175428, 52980624
Offset: 1
References
- H. M. Gurk and J. R. Isbell. 1959. Simple Solutions. In A. W. Tucker and R. D. Luce (eds.) Contributions to the Theory of Games, Volume 4. Princeton, NJ: Princeton University Press, pp. 247-265. (Case n=6.)
- D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
- S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 23. (Cases until n=9.)
- 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).
- J. von Neumann and O. Morgenstern, Theory of games and economic behavior, Princeton University Press, New Jersey, 1944. (Cases n=1 to 5.)
Links
- J.-C. Hausmann, Counting polygon spaces, Boolean functions and majority games, arXiv preprint arXiv:1501.07553 [math.CO], 2015.
- J.-C. Hausmann and E. Rodriguez, The space of clouds in Euclidean space, Experiment. Math. 13 (2004), 31-47.
- J.-C. Hausmann and E. Rodriguez. The space of clouds in Euclidean space, Corrections and additional material.
- J. R. Isbell, On the enumeration of majority games, MTAC, v.13, 1959, pp. 21-28. (Case n=7).
- Alastair D. King, Comments on A002080 and related sequences based on threshold functions, Mar 17 2023.
- 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.
- S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971 [Annotated scans of a few pages]
- S. Muroga, T. Tsuboi and C. R. Baugh, Enumeration of threshold functions of eight variables, IEEE Trans. Computers, 19 (1970), 818-825.
- S. Muroga, T. Tsuboi and C. R. Baugh, Enumeration of threshold functions of eight variables, IEEE Trans. Computers, 19 (1970), 818-825. [Annotated scanned copy]
- Erik Ordentlich, Ron M. Roth and Gadiel Seroussi, On q-ary Antipodal Matchings and Applications, 2012.
- Index entries for sequences related to Boolean functions
Formula
a(n) = Sum_{k=1..n} A003184(k). - Alastair D. King, Oct 26 2023
Extensions
a(10) added by W. Lan (wl(AT)fjrtvu.edu.cn), Jun 27 2010
Better description from Alastair King, Mar 17 2023.
Comments