×

Binary relations on the power set of an \(n\)-element set. (English) Zbl 1211.05009

Summary: We define six binary relations on the power set of an \(n\)-element set and describe their basic structure and interrelationships. An auxiliary relation is noted that will assist in determining the cardinalities of each. We also indicate an eighth relation that may be of interest. We conclude the first section by computing several quantities related to walks in the graph of the sixth relation. In the second section we turn our attention to the basic structure and cardinalities of the auxiliary relation noted in section one and several additional relations. We also compute seven sums associated with these relations and indicate connections four relations have with Wieder’s \(conjoint\) and \(disjoint k-combinations\).

MSC:

05A05 Permutations, words, matrices
05A18 Partitions of sets
11B73 Bell and Stirling numbers

Software:

OEIS
PDFBibTeX XMLCite
Full Text: EuDML EMIS

Online Encyclopedia of Integer Sequences:

a(n) = 2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)
Powers of 3: a(n) = 3^n.
Stirling numbers of second kind S(n,3).
a(n) = 2^n - 2.
a(n) = 3^n - 2^n.
a(n) = 3^n - 3*2^n + 3.
a(n) = n*4^(n-1).
a(n) = n*2^(2*n-1).
a(n) = (3^n - 1)/2.
a(n) = 3^n + 2^n - 1.
a(n) = 2^(n-1)*(2^n - 1), n >= 0.
a(n) = (3^n + 1)/2.
a(n) = 2^(n-1)*(1+2^n).
Expansion of e.g.f.: exp(2*x)/(1-x).
Number of monotone Boolean functions of n variables with 2 mincuts. Also number of Sperner systems with 2 blocks.
a(n) = 4^n - 2^n.
a(n) = 3^n - 1.
a(n) = (n-1)*3^(n-2), n > 0.
a(n) = 2*(3^n) - 2^n.
a(n) = 3^(n-1) - 2*2^(n-1) + 1 (essentially Stirling numbers of second kind).
Number of ways to partition n labeled elements into 4 pie slices allowing the pie to be turned over; number of 2-element proper antichains of an n-element set.
a(n) = 3*2^n - 2.
Number of 2-element intersecting families of an n-element set; number of 2-way interactions when 2 subsets of power set on {1..n} are chosen at random.
a(n) = n*2^n.
Triangle whose (i,j)-th entry is binomial(i,j)*2^(i-j).
k=2 column of A038719.
Number of 2-element intersecting families (with not necessarily distinct sets) of an n-element set.
Number of 2-element intersecting families (with not necessarily distinct sets) whose union is an n-element set.
First differences of A003063.
Expansion of x^2/((1-3*x)*(1-2*x)^2).
Expansion of e.g.f. x*exp(3*x)*cosh(x).
a(n) = 3^n - 2^n + 1.
Number of 2-multiantichains of an n-set.
Triangle read by rows: a(n,k) = number of k-length walks in the Hasse diagram of a Boolean algebra of order n.
Matrix defined by a(n,k) = 3^n*Fibonacci(k) - 2^n*Fibonacci(k-2), read by antidiagonals.
Number of ordered 2-multiantichains on an n-set.
Number of connected 2-element antichains on a labeled n-set.
a(n) = (3^n-1)/2 + 2^n.
a(n) = 3*3^n - 3*2^n + 1.
Let P(A) be the power set of an n-element set A and let B be the Cartesian product of P(A) with itself. Remove (y,x) from B when (x,y) is in B and x <> y and let R35 denote the reduced set B. Then a(n) = the sum of the sizes of the union of x and y for every (x,y) in R35.
Let P(A) denote the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, 1) x and y are disjoint and for which either x is a subset of y or y is a subset of x, or 2) x and y intersect but for which x is not a subset of y and y is not a subset of x.
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x.
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 1) x = y.
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 2) x = y.
a(n) = binomial(2^n-1,2).
a(n) = (1/2)*(3^n - 2^(n+1) + 3).
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 1) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x, or 2) x = y.
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 2) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 3) x = y.
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 2) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x, or 3) x = y.
a(n) = 2^(n-1)*(2^n - 1) + 1.
a(n) = 4^n - 3^n + 1.
Main transitions in systems of n particles with spin 3/2.
Array defined by a(n,k) = floor((k+2)/2)*3^n - floor((k+1)/2)*2^n, read by antidiagonals.