|
|
A000617
|
|
Number of NP-equivalence classes of threshold functions of n or fewer variables.
(Formerly M0727 N0272)
|
|
5
|
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
NP-equivalence classes of threshold functions are equivalent to weighted games, in simple game theory.
The number for n=9 was first documented in Tautenhahn's thesis. (End)
|
|
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
|
|
|
FORMULA
|
a(n) = Sum_{k=0..n} A000619(k). - Alastair D. King, Oct 26, 2023.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|