A000617 Number of NP-equivalence classes of threshold functions of n or fewer variables.
2, 3, 5, 10, 27, 119, 1113, 29375, 2730166, 989913346
Offset: 0
References
- S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 14.
- S. Muroga, T. Tsuboi, and C. R. Baugh, Enumeration of threshold functions of eight variables, IEEE Trans. Computers, 19 (1970), 818-825.
- 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).
- N. Tautenhahn, Enumeration einfacher Spiele mit Anwendungen in der Stimmgewichtsverteilung, 2008. Master's thesis, University of Bayreuth, 269 pages (in German).
Links
- S. Bolus, A QOBDD-based Approach to Simple Games, Dissertation, Doktor der Ingenieurwissenschaften der Technischen Fakultaet der Christian-Albrechts-Universitaet zu Kiel, 2012. - From _N. J. A. Sloane_, Dec 22 2012
- I. Krohn and P. Sudhölter, Directed and weighted majority games, Math. Methods Operat. Res. 42 (2) (1995) 189-216, Table 1.
- S. Kurz, On minimum sum representations for weighted voting games, arXiv:1103.1445 [math.CO], 2011-2018.
- 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. [Annotated scanned copy]
- Eda Uyanık, Olivier Sobrie, Vincent Mousseau, and Marc Pirlot, Enumerating and categorizing positive Boolean functions separable by a k-additive capacity, Discrete Applied Mathematics, Vol. 229, 1 October 2017, p. 17-30. See Table 3.
Crossrefs
Cf. A000619.
Formula
a(n) = Sum_{k=0..n} A000619(k). - Alastair D. King, Oct 26 2023.
Comments