| Displaying 1-6 of 6 results found.
page
1
Number of N-equivalence classes of self-dual threshold functions of exactly n variables.
(Formerly M3683 N1503)
+10
18
1, 0, 1, 4, 46, 1322, 112519, 32267168, 34153652752
REFERENCES
S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 10.
S. Muroga and I. Toda, Lower bound on the number of threshold functions, IEEE Trans. Electron. Computers, 17 (1968), 805-806.
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).
FORMULA
A002080(n) = Sum_{k=1..n} a(k)*binomial(n,k). Also A000609(n-1) = Sum_{k=1..n} a(k)*binomial(n,k)*2^k. - Alastair D. King, Mar 17, 2023.
EXTENSIONS
Better description from Alastair King, Mar 17, 2023.
Number of threshold functions of n or fewer variables.
(Formerly M1285 N0492)
+10
11
2, 4, 14, 104, 1882, 94572, 15028134, 8378070864, 17561539552946, 144130531453121108
COMMENTS
a(n) is also equal to the number of self-dual threshold functions of n+1 or fewer variables. - Alastair D. King, Mar 17, 2023.
REFERENCES
Sze-Tsen Hu, Threshold Logic, University of California Press, 1965 see page 57.
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 3.
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).
C. Stenson, Weighted voting, threshold functions, and zonotopes, in The Mathematics of Decisions, Elections, and Games, Volume 625 of Contemporary Mathematics Editors Karl-Dieter Crisman, Michael A. Jones, American Mathematical Society, 2014, ISBN 0821898663, 9780821898666
LINKS
Muroga, Saburo, 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] Stephen Wolfram, A New Kind Of Science. page 1102.
FORMULA
a(n) = Sum_{k=0..n} A000615(k)*binomial(n,k) = Sum_{k=0..n} A002079(k)*binomial(n,k)*2^k. Also A002078(n) = (1/2^n)*Sum_{k=0..n} a(k)*binomial(n,k), a(n-1) = Sum_{k=1..n} A002077(k)*binomial(n,k)*2^k, and A002080(n) = (1/2^n)*Sum_{k=1..n} a(k)*binomial(n,k). - Alastair D. King, Mar 17, 2023.
Number of N-equivalence classes of self-dual threshold functions of n or fewer variables.
(Formerly M1266 N0485)
+10
8
1, 2, 4, 12, 81, 1684, 122921, 33207256, 34448225389
REFERENCES
S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.
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).
FORMULA
a(n) = Sum_{k=1..n} A002077(k)*binomial(n,k) = (1/2^n)*Sum_{k=1..n} A000609(k-1)*binomial(n,k). - Alastair D. King, Mar 17, 2023.
EXTENSIONS
Better description and corrected value of a(7) from Alastair King (see link) - N. J. A. Sloane, Oct 24 2023
Number of N-equivalence classes of threshold functions of exactly n variables.
(Formerly M0122 N0049)
+10
7
2, 1, 2, 9, 96, 2690, 226360, 64646855, 68339572672
REFERENCES
S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 8.
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).
LINKS
Muroga, Saburo, 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]
FORMULA
A002078(n) = Sum_{k=0..n} a(k)*binomial(n,k). A000609(n) = Sum_{k=0..n} a(k)*binomial(n,k)*2^k. - Alastair D. King, Mar 17, 2023.
EXTENSIONS
Better description from Alastair King, Mar 17, 2023.
NPN-equivalence classes of threshold functions of n or fewer variables.
(Formerly M0809 N0306)
+10
2
1, 2, 3, 6, 15, 63, 567, 14755, 1366318
REFERENCES
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 19.
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).
Number of equivalence classes of threshold functions under permutations of the variables.
+10
0
2, 4, 10, 34, 178, 1720, 590440
REFERENCES
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]
Search completed in 0.011 seconds
|