|
Search: id:A088322
|
|
|
| A088322 |
|
Number of monotone functions f: 2^X -> 2^X where 2^X is the power set of an n-set X. Here f is monotone means that if A is a subset of B then f(A) is a subset of f(B). |
|
+0
2
|
|
| 1, 3, 36, 8000, 796594176, 25039893834551321901, 230156231509903526722108570920314496786496, 47865176496200868983923053829656412802359862974841510357002550233808599919147992\ 2367872
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
Proof of formula by Robert Israel: If f is monotone, then for each x in X the set G(x) = {A in 2^X: x in f(A)} is an upset, i.e. if A is in G(x) and A \subset B then B is in G(x). Conversely, if for each x in X the set G(x) is an upset, then f is monotone. And the family {G(x): x in X} determines f, since f(A) = {x: A is in G(x)}. So the cardinality of the set of monotone set-functions is N(|X|)^|X| where N(|X|) is the cardinality of the set of upsets G of 2^X, or equivalently monotone Boolean functions. That is sequence A000372.
This sequence was motivated by a question by Federico Echenique on sci.math.research.
|
|
FORMULA
|
a(n) = A000372[n]^n.
|
|
CROSSREFS
|
Cf. A000372, A061301.
Sequence in context: A136393 A158093 A163966 this_sequence A080807 A006268 A073236
Adjacent sequences: A088319 A088320 A088321 this_sequence A088323 A088324 A088325
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
W. Edwin Clark (eclark(AT)math.usf.edu), Nov 06 2003
|
|
|
Search completed in 0.002 seconds
|
