A000619 -id:A000619 - cp's OEIS frontend

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

From Fabián Riquelme, Jun 01 2012: (Start)
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)

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).

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.

Cf. A000619.

a(n) = Sum_{k=0..n} A000619(k). - Alastair D. King, Oct 26 2023.

A003184 Number of NP-equivalence classes of self-dual threshold functions of exactly n variables.

Original entry on oeis.org

1, 0, 1, 1, 4, 14, 114, 2335, 172958, 52805196

Offset: 1

N. J. A. Sloane

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.
S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 24. (Cases n>7.)
J. von Neumann and O. Morgenstern, Theory of games and economic behavior, Princeton University Press, New Jersey, 1944. Cases n=1 to 5.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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.
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]
Index entries for sequences related to Boolean functions

Cf. A000619, A001532, A002077-A002080.

a(n) = A001532(n) - A001532(n-1), for n > 1. - Evgeny Luttsev, Sep 09 2014

a(9) from Evgeny Luttsev, Sep 09 2014

Better description and new offset from Alastair King, Mar 17 2023

A176692 Partial sums of A000617.

Original entry on oeis.org

2, 5, 10, 20, 47, 166, 1279, 30654, 2760820

Offset: 0

Jonathan Vos Post, Apr 24 2010

nonn

Partial sums of number of NP-equivalence classes of threshold functions of n or fewer variables. The subsequence of primes in this sequence begins: 2, 5, 47, 1279.

			a(6) = 2 + 3 + 5 + 10 + 27 + 119 + 1113 = 1279 is prime.

Cf. A000617, A000619.

a(n) = SUM[i=0..n] A000617(i) = SUM[i=0..n] SUM[j=0..i] A000619(j).

cp's OEIS Frontend

A000617 Number of NP-equivalence classes of threshold functions of n or fewer variables.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A003184 Number of NP-equivalence classes of self-dual threshold functions of exactly n variables.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A176692 Partial sums of A000617.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula