A000617 -id:A000617 - cp's OEIS frontend

A176692 Partial sums of A000617.

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

A000619 NP-equivalence classes of threshold functions of exactly n variables.

Original entry on oeis.org

2, 1, 2, 5, 17, 92, 994, 28262, 2700791, 990331318

Offset: 0

N. J. A. Sloane

S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 15.
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).

Eiichi Goto and Hidetosi Takahasi, Some Theorems Useful in Threshold Logic for Enumerating Boolean Functions, in Proceedings International Federation for Information Processing (IFIP) Congress, 1962, pp. 747-752. [Annotated scans of certain pages]
Vadim M. Kartak, Artem V. Ripatti, Guntram Scheithauer, and Sascha Kurz, Minimal proper non-IRUP instances of the one-dimensional cutting stock problem, Discrete Applied Mathematics 2015, 187, 120-129. (has the last known term as of 2021, a(9)=990331318)
S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971 [Annotated scans of a few pages]
Saburo Muroga, Iwao Toda, and Satoru Takasu, Theory of majority decision elements, Journal of the Franklin Institute 271.5 (1961): 376-418. [Annotated scans of pages 413 and 414 only]
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]

Cf. A000617.

a(n) = A000617(n) - A000617(n-1). - Alastair D. King, Oct 26 2023.

a(9) added by Xavier Molinero, Oct 06 2021

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.

Original entry on oeis.org

1, 1, 2, 3, 7, 21, 135, 2470, 175428, 52980624

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

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

Cf. A000617, A002077-A002080, A003184, A109456, A132183, A189359.

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

a(10) added by W. Lan (wl(AT)fjrtvu.edu.cn), Jun 27 2010

Better description from Alastair King, Mar 17 2023.

A189359 Number of homogeneous games for n players.

Original entry on oeis.org

0, 1, 3, 8, 23, 76, 293, 1307, 6642, 37882

Offset: 0

Fabián Riquelme, Apr 20 2011

I. Krohn and P. Sudhölter, Directed and weighted majority games, Mathematical Methods of Operation Research, 42, 2 (1995), 189-216. See Table 1, p. 213; also on ResearchGate.
P. Sudhölter, Homogeneous games as anti step functions, International Journal of Game Theory Vol. 18, (1989), 433-469.

Subclass of A000617. Cf. A001532, A022493, A109456, A132183.

Conjecture: g.f.: Q(0)*x/(1-x), where Q(k) = 1 + (1-(1-x)^(2*k+2))/(1- (1-(1-x)^(2*k+3))/(1-(1-x)^(2*k+3) + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 13 2013

Note that a(n) - a(n-1) = A022493(n) for 1 <= n <= 9. Does this equality hold for n > 9? If so, then we have the g.f. 1/(1 - x)*( Sum_{n >= 1} Product_{k = 1..n} (1 - (1 - x)^k) ). - Peter Bala, Dec 13 2021

A109455 Number of equivalence classes of threshold functions under permutations of the variables.

Original entry on oeis.org

2, 4, 10, 34, 178, 1720, 590440

Offset: 0

Don Knuth, Aug 17 2005

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. [Background]

Cf. A002078, A000617, A001529.

cp's OEIS Frontend

A176692 Partial sums of A000617.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A000619 NP-equivalence classes of threshold functions of exactly n variables.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A189359 Number of homogeneous games for n players.

Views

Author

Keywords

Links

Crossrefs

Formula

A109455 Number of equivalence classes of threshold functions under permutations of the variables.

Views

Author

Keywords

References

Crossrefs