PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 97(111) (2015), 69–87 DOI: 10.2298/PIM140406001K

ENUMERATION OF CERTAIN CLASSES OF ANTICHAINS

Goran Kilibarda

Abstract. An antichain is here regarded as a hypergraph that satisfies the following property: neither of every two different edges is a subset of the other one. The paper is devoted to the enumeration of antichains given on an n-set and having one or more of the following properties: being labeled or unlabeled; being ordered or unordered; being a cover (or a proper cover); and finally, being a T_{0}-, T_{1}- or T_{2}-hypergraph. The problem of enumeration of these classes comprises, in fact, different modifications of Dedekind’s problem. Here a theorem is proved, with the help of which a greater part of these classes can be enumerated. The use of the formula from the theorem is illustrated by enumeration of labeled antichains, labeled T_{0}-antichains, ordered unlabeled antichains, and ordered unlabeled T_{0}-antichains. Also a list of classes that can be enumerated in a similar way is given. Finally, we perform some concrete counting, and give a table of digraphs that we used in the counting process.

1. Introduction

By a hypergraph we mean a finite nonempty set together with a finite multiset of its subsets. The elements of this set are called vertices and the subsets are called edges of the hypergraph. Quite naturally, we introduce the notion of the hypergraph with and without multiple edges. If a linear order is given on the multiset of edges of a hypergraph, we get an ordered hypergraph. An antichain is a hypergraph without multiple edges that satisfies the following property: neither of every two different edges is a subset of the other one. A hypergraph is a T_{0}-hypergraph if for every two different vertices there exists an edge that contains exactly one of them.

By a relative equivalence 𝔭 on a set X we mean a subset X′ of the given set together with a relation of equivalence ∼ on this subset X′; so we have that 𝔭 = (X′, ∼).

Let us fix an n-set V, and denote by ℌ the set of all hypergraphs on V, i.e., of all hypergraphs that have V as their set of vertices. Then on ℌ we take a relative equivalence 𝔭 = (ℌ_{𝔭}, ∼_{𝔭}). Antichains belonging to the set ℌ_{𝔭} are called

2010 Mathematics Subject Classification: 05C30; 05C65. Key words and phrases: Exact enumeration, monotone Boolean function, hypergraph, an-

tichain, cover, bipartite graph, digraph, coloring of a digraph.

Communicated by Žarko Mijajlović.

𝔭-antichains. Supposing that 𝔭 satisfies some natural conditions we get that every class of the equivalence ∼_{𝔭} is either a subset of or disjoint from the set of all 𝔭antichains. We do not differentiate 𝔭-antichains that belong to the same class of equivalence ∼_{𝔭}, and our goal is to count the number of all classes of 𝔭-antichains.

We derive a formula (Theorem 3.3) for counting classes of 𝔭-antichains in the labeled case. A new class of digraphs, a class of all hedgehogs, is introduced, and the formula “goes” over the digraphs of this class. As an illustration of the use of the formula, examples of the enumeration of labeled antichains, labeled T_{0}- antichains, ordered unlabeled antichains, and ordered unlabeled T_{0}-antichains with a fixed number of edges are given.

The first of these examples, i.e., the case of labeled antichains, has connection with the well-known problem of Dedekind [1], a brief history of which can be found in [2, 3]. Though the problem has been considered in many papers, it remains open till now.

2. Basic notions and designations

Let X be a set. Denote by |X| the cardinality of the set X, by 𝔅(X) the power set of X. If |X| = n, then we say that X is an n-set.

For all integers m_{1}, m_{2} ∈ Z, m_{1} ⩽ m_{2}, by \overline{m_{1}, m_{2}} denote the integer interval \{m_{1}, m_{1} + 1, …, m_{2}\}. Also, by \overline{n} denote the set \{1, …, n\} for every n ∈ N, and let N_{0} = N ∪ {0}.

Following [4], by a multiset on a set S we mean an ordered pair consisting of S and a mapping f: S → N_{0}. Let a = (S, f) be a multiset; the value f(s) is called multiplicity of s ∈ S in a. If it is clear from the context which function f is meant, we use the notation ∥s∥ instead of f(s). For some s ∈ S we write s ∈ a if ∥s∥ > 0. If ∥s∥ = 0 for every s ∈ S, then the multiset a is called the empty multiset. By the cardinality of the multiset a we mean the number |a| = ∑ _{s∈S} ∥s∥, and it is called an m-multiset if |a| = m. Let b = (S, g) be another multiset. We write a ⊆ b if f(s) ⩽ g(s) for every s ∈ S.

Let us introduce some notions from the graph theory which we are going to use in the paper. By unordered hypergraph or simply hypergraph we mean an ordered pair H = (V, E), where V is a finite nonempty set and E a finite multiset on 𝔅(V). Let us call elements of the set V vertices, and members of the multiset E edges of the given hypergraph H. In what follows the set of vertices of a hypergraph H will be also denoted by V H, and the multiset of its edges by EH. If |E| = m and |V | = n, then we call hypergraph H an (m, n)-hypergraph. We say that a hypergraph H is a hypergraph without multiple edges if ∥e∥ = 1 for every e ∈ EH.

If in the above given definition instead of a multiset E we take an m-tuple (e_{1}, …, e_{m}), where e_{i} ⊆ V (i ∈ \overline{m}), then we have an ordered hypergraph, that is, if |V | = n, we have an ordered (m, n)-hypergraph. The sets e_{i}, i ∈ \overline{m}, are its edges.

Let e be an edge of a hypergraph H (ordered or unordered). We say that e is an empty edge if e = ∅, and e is a unit edge if e = V H.

Note that a graph may be regarded as a special case of a hypergraph. In what follows, we shall often denote by V G the set of vertices V, and by EG the set of edges E of the graph G = (V, E). The same notation is used for a digraph D = (V, E): by V D we mean set of vertices V, and by ED the set of edges E.

Let H = (V, E) be a hypergraph or an ordered hypergraph. We say that a vertex v ∈ V of H is incident to an edge e ∈ E of H (or e is incident to v) if v ∈ e. A vertex v is called an isolated vertex in H if there is no edge in H which is incident to v. A set V′ ⊆ V is a set of adjacent vertices in H if there exists an edge e ∈ E such that V′ ⊆ e.

Denote by H(V) [H⃗(V)] the set of all hypergraphs [ordered hypergraphs] that have a set V as their set of vertices. Let H_{1} and H_{2} be two hypergraphs from H(V). These hypergraphs are equal, H_{1} ≡ H_{2}, if EH_{1} = EH_{2}. They are isomorphic, H_{1} ≃ H_{2}, if there is a bijection ι : V → V such that e ∈ EH_{1} iff ι(e) ∈ EH_{2} for every e ∈ 𝔅(V), and ∥e∥ = ∥ι(e)∥ for every e ∈ EH_{1}. These two relations are equivalence relations on H(V). By labeled [unlabeled] hypergraph (on V) we mean a class of equivalence ≡ [≃]. Isomorphic [equal] hypergraphs have the same number of edges, and because of that we can speak about an unlabeled [labeled] (m, n)- hypergraph. Analogously, we can introduce the notion of an unlabeled [labeled] ordered (m, n)-hypergraph.

Let H be a hypergraph [an ordered hypergraph]. It is called an antichain if it is a hypergraph [an ordered hypergraph] without multiple edges and if e_{1} ⊈ e_{2} for every e_{1}, e_{2} ∈ EH, e_{1} ≠ e_{2}. It is called a cover if there is no isolated vertex in H. If a cover does not contain the unit edge, we say that it is a proper cover.

By analogy with the notions of T_{0}-, T_{1}- and T_{2}-spaces from general topology let us introduce similar notions for hypergraphs. A hypergraph (an ordered hypergraph) H is:

a) a T_{0}-hypergraph iff for every two different vertices u, v ∈ V there exists an edge e from H such that (u ∈ e ∧ v ∉ e) ∨ (u ∉ e ∧ v ∈ e),

b) a T_{1}-hypergraph iff for every pair (u, v) ∈ V^{2} of different vertices there is an edge e from H, such that (u ∈ e ∧ v ∉ e),

c) a T_{2}-hypergraph iff for every pair (u, v) ∈ V^{2} of different vertices there exist edges e_{1}, e_{2} from H, such that (u ∈ e_{1} ∧ v ∈ e_{2} ∧ e_{1} ∩ e_{2} = ∅).

It is clear that if a hypergraph belongs to one of the above classes, then an isomorphic hypergraph is also from the same class. Thus we may say that an unlabeled hypergraph is an antichain, cover and so on.

Let us fix an infinite set V_{∞} = {v_{1}, v_{2}, …}. Put V_{i} = {v_{1}, …, v_{i}} for every i ∈ N . Introduce classes of labeled [unlabeled] (m, n)-hypergraphs T_{a_{1} a_{2} a_{3} a_{4} a_{5}} (m, n) (0 ⩽ a_{1}, a_{2}, a_{3} ⩽ 1; 0 ⩽ a_{4} ⩽ 2; 0 ⩽ a_{5} ⩽ 3) on V_{n} in the following way. The parameters a_{i}, 1 ⩽ i ⩽ 5, have the following meaning:

a_{1}  a_{2}  a_{3}  a_{4}  a_{5}
0 labeled  ordered antichain proper-cover T_{2}
1 unlabeled unordered  ∅  cover  T_{1}
2  —  —  —  ∅  T_{0}
3  —  —  —  —  ∅

In the table the symbol ∅ means that the corresponding property is not taken into account. The introduced classes are in fact the constituents of the previously defined classes of hypergraphs. For example, the class T_{00022} (m, n) consists of all labeled ordered T_{0}-hypergraphs on V_{n} with m edges which are antichains. Class T_{10213} (m, n) consists of all unlabeled ordered (m, n)-hypergraphs on V_{n} which are covers.

Some of introduced parameters are not completely independent. For example, if a hypergraph is a T_{1}- or T_{2}-hypergraph, and n > 1, then it is also a cover; if it is an antichain, and m > 1, then it is also a proper cover.

We consider, basically, classes A_{i_{1} i_{2} i_{3}} (m, n) = T_{0i_{1} 0i_{2} i_{3}} (m, n) (0 ⩽ i_{1} ⩽ 1, 0 ⩽ i_{2} ⩽ 2, 1 ⩽ i_{3} ⩽ 3), and our aim is to find their cardinality. Let us put t_{a_{1} a_{2} a_{3} a_{4} a_{5}} (m, n) = |T_{a_{1} a_{2} a_{3} a_{4} a_{5}} (m, n)| and α_{i_{1} i_{2} i_{3}} (m, n) = |A_{i_{1} i_{2} i_{3}} (m, n)|.

If it is clear from the context which set is taken as a set of vertices for a hypergraph H = (V, E), we use the notation E instead of (V, E). Denote by H(m, n) the set of all ordered hypergraphs with m edges and with the set of vertices V_{n}. Let us put ℌ(n) = ∪_{m=1}^{∞} H(m, n).

Let H = (e_{1}, …, e_{m}) be a labeled ordered hypergraph from the set H(m, n). Let us define the incidence matrix M_{H} = [a_{ij} ]_{m×n} of H as a matrix for which a_{ij} = 1 if v_{j} ∈ e_{i}, and a_{ij} = 0, otherwise. Let c_{j} (1 ⩽ j ⩽ n) be the j-th column of M_{H}. Then we sometimes represent matrix M_{H} by n-tuple (c_{1}, c_{2}, …, c_{n}).

For every labeled ordered hypergraph H ∈ H(m, n) with incidence matrix M_{H} a dual labeled ordered hypergraph H^{T} is defined as the hypergraph from the set H(n, m) whose incidence matrix is M_{H}^{T}, where M_{H}^{T} is transpose of M_{H}.

Denote by D_{m} the class of all labeled digraphs with the set V_{m} as their set of vertices. Every digraph with m vertices that we are going to consider further is an element of the set D_{m}. The unique digraph without edges which belongs to D_{m} is denoted by ∅_{m}.

Let D ∈ D_{m}, and let H = (e_{1}, …, e_{m}) ∈ H(m, n). We say that D correlates with H if for every i, j ∈ \overline{m}, i ≠ j, from (v_{i}, v_{j}) ∈ ED follows that e_{i} ⊆ e_{j}. By f_{H} denote the function f_{H} : V_{m} → 𝔅(V_{n}) such that f_{H} (v_{i}) = e_{i} for every i ∈ \overline{m}. Denote by H(D, n) the set of all hypergraphs H′ from the set H(m, n) such that D correlates with H′. It is clear that H(m, n) = H(∅_{m}, n). Denote by Ĥ(D, n) the set of all hypergraphs without multiple edges from H(D, n).

Let H = (e_{1}, …, e_{m}) ∈ H(m, n). Denote by \overline{H} a hypergraph (e_{k_{1}} , …, e_{k_{m′}} ), 1 = k_{1} < k_{2} < ⋯< k_{m′}, such that e_{k_{i}} ≠ e_{k_{j}} for every i, j ∈ \overline{m′}, i ≠ j, and for every i ∈ \overline{m} there exists j ∈ \overline{m′} such that k_{j} ⩽ i and e_{i} = e_{k_{j}} . It is obvious that for every H the hypergraph \overline{H} is unique.

By a relative equivalence on a set A we mean a pair 𝔭 = (A_{𝔭}, ∼_{𝔭}), where A_{𝔭} ⊆ A and ∼_{𝔭} is equivalence on A_{𝔭}. Let B be a subset of A. We say that B is 𝔭-subset of A if the set A_{𝔭} ∩ B ∩ a is equal to a or ∅ for every class a ⊆ A_{𝔭} of equivalence ∼_{𝔭}. Let us put B_{𝔭} = B ∩ A_{𝔭}, B/𝔭 = {a ∈ A_{𝔭}/∼_{𝔭} | B ∩ a ≠ ∅}, and α_{𝔭}(B) = |B/𝔭|. If we write x ∼_{𝔭} y for some x, y ∈ A, then it means that there exists an a ∈ A_{𝔭}/∼_{𝔭} such that x, y ∈ a.

Let 𝔭 be a relative equivalence on ℌ(n). We say that 𝔭 is regular on ℌ(n), if 1) the sets H(D, n) and Ĥ(D, n) are 𝔭-subsets of ℌ(n) for every m ∈ N and

D ∈ D_{m};

2) H ∼_{𝔭} H′ then \overline{H} ∼_{𝔭} \overline{H′} for every H, H′ ∈ H(m, n). Let 𝔭 be regular relative equivalence on ℌ(n). Then we take that

H_{𝔭}(D, n) = (H(D, n))_{𝔭}, Ĥ_{𝔭}(D, n) = (Ĥ(D, n))_{𝔭}, ℌ_{𝔭}(D, n) = H(D, n)/𝔭

and ℌ̂_{𝔭}(D, n) = Ĥ(D, n)/𝔭. Also denote λ_{𝔭}(D, n) = α_{𝔭}[H(D, n)] and λ̂_{𝔭}(D, n) = α_{𝔭}[Ĥ(D, n)].

Denote by H^{(i)} (D, n), i ∈ \overline{|V D|}, the set of all hypergraphs from H(D, n) that have exactly i different edges. We say that a regular relative equivalence 𝔭 = (ℌ_{𝔭}(n), ∼_{𝔭}) on ℌ(n) is strong, if

1) H^{(i)} (D, n) is 𝔭-subset of ℌ(n) for every D ∈ D_{m} and every i ∈ \overline{m},

2) for every H′, H′′ ∈ H_{𝔭}^{(i)} (D, n) = (H^{(i)} (D, n))_{𝔭}, H′ ∼_{𝔭} H′′, and every

v′, v′′∈ V_{m}, f_{H′} (v′) ⊆ f_{H′} (v′′) iff f_{H′′}(v′) ⊆ f_{H′′}(v′′).

3. On the number of 𝔭-antichains

Let 𝔭 = (ℌ_{𝔭}(n), ∼_{𝔭}) be a relative equivalence on ℌ(n). By 𝔭-antichain we mean every antichain belonging to ℌ_{𝔭}(n). Denote by A_{𝔭}(m, n) the set of all 𝔭-antichains that belong to the class H_{𝔭}(m, n) = H_{𝔭}(∅_{m}, n). Let α_{𝔭}(m, n) = α_{𝔭}(A_{𝔭}(m, n)).

Theorem 3.1. Let 𝔭 be a regular relative equivalence on ℌ(n). Then the set A_{𝔭}(m, n) is 𝔭-subset of ℌ(n) and it holds that

α_{𝔭}(m, n) = ∑_{D∈D_{m}} (−1)^{|ED|} λ_{𝔭}(D, n) = ∑_{D∈D_{m}} (−1)^{|ED|} λ̂_{𝔭}(D, n).

Proof. We say that a H = (e_{1}, …, e_{m}) ∈ H(m, n) possesses the property p_{ij} (i, j ∈ \overline{m}, i ≠ j) if e_{i} ⊆ e_{j}. Let H ∈ H_{𝔭}(m, n). Then H ∈ A_{𝔭}(m, n) iff H does not possess any of the properties p_{ij} , i, j ∈ \overline{m}, i ≠ j. Note that A_{𝔭}(m, n) ⊆ Ĥ_{𝔭}(m, n).

Now observe arbitrary r of such properties p_{i_{1} j_{1}} , …, p_{i_{r} j_{r}} . Let D be a digraph from D_{m} such that ED = {(v_{i_{1}} , v_{j_{1}} ), …, (v_{i_{r}} , v_{j_{r}} )}. It is clear that the set of all hypergraphs H ∈ H(m, n) which possess the properties p_{i_{1} j_{1}} , …, p_{i_{r} j_{r}} is actually the set H(D, n). Now, it is clear that

A_{𝔭}(m, n) = H_{𝔭}(m, n) ∖ ⋃_{D∈D_{m} ∖∅_{m}} H(D, n) = H_{𝔭}(m, n) ∖ ⋃_{D∈D_{m} ∖∅_{m}} H_{𝔭}(D, n)

= Ĥ_{𝔭}(m, n) ∖ ⋃_{D∈D_{m} ∖∅_{m}} (H_{𝔭}(D, n) ∩ Ĥ_{𝔭}(m, n)) = Ĥ_{𝔭}(m, n) ∖ ⋃_{D∈D_{m} ∖∅_{m}} Ĥ_{𝔭}(D, n).

The first part of the theorem follows from this relation, and, also, from the relation, using the inclusion-exclusion principle, we can get now the second part of the theorem. □

Denote by D′_{m} the set of all acyclic digraphs from D_{m}, and by D′′_{m} the set of all digraphs from D′_{m} in which there is a path of the length ⩾ 2. Let us call the elements of the set J_{m} = D′_{m} ∖ D′′_{m} hedgehogs. Note that a connected hedgehog J is an oriented bipartite graph with distinguished blocks V_{1}(J) and V_{2}(J) such that for every edge (u, v) ∈ E(J) it holds that u ∈ V_{1}(J) and v ∈ V_{2}(J). Note also that the notion of the hedgehog is close to the notion of 2-graduate posets [5]. Now let us give an improvement of the formula from Theorem 3.1.

Theorem 3.2. α_{𝔭}(m, n) = ∑_{D∈J_{m}} (−1)^{|ED|} λ̂_{𝔭}(D, n).

Proof. Let D be a digraph from D_{m} ∖D′_{m}. As D is from D_{m} ∖D′_{m}, then D has at least one simple cycle. Let v_{i_{1}} v_{i_{2}} …v_{i_{k}} , where v_{i_{1}} = v_{i_{k}} and (v_{i_{j}} , v_{i_{j+1}} ) ∈ ED for every j ∈ \overline{k − 1} , be one of these cycles. Now if H = (e_{1}, …, e_{m}) ∈ H_{𝔭}(D, n), then e_{i_{1}} ⊆ e_{i_{2}} ⊆ ⋯⊆ e_{i_{k}} ⊆ e_{i_{1}} , so it follows that e_{i_{1}} = e_{i_{2}} = ⋯= e_{i_{k}} . Thus H ∉ Ĥ_{𝔭}(D, n), and we have that Ĥ_{𝔭}(D, n) = ∅. Thus we have equation

∑_{D∈D_{m} ∖D′_{m}} (−1)^{|ED|} λ̂_{𝔭}(D, n) = 0. (3.1)

Let us consider the class of digraphs D′′_{m}. Order all the ordered pairs of different vertices from V_{m}^{2} in a sequence: (u′_{1}, u′′_{1}), (u′_{2}, u′′_{2}), …, (u′_{a_{0}} , u′′_{a_{0}}), a_{0} = m(m − 1). Break the set D′′_{m} into disjoint classes (D′′_{m})_{i}, i ∈ \overline{a_{0}}, so that the digraph D ∈ D′′_{m} will belong to class (D′′_{m})_{i} iff the following condition is satisfied: D does not belong to the set ∪_{l=1}^{i−1} (D′′_{m})_{l} and in D there is a directed path of the length ⩾ 2 with the beginning in u′_{i} and with the end in the vertex u′′_{i}.

It is clear that for every i ∈ \overline{a_{0}} we can break the class (D′′_{m})_{i} into 2-sets, such that the digraphs from such a 2-set differ only in the fact that one contains the edge (u′_{i}, u′′_{i}) and the other does not. Also, it is clear that for every such 2-set {D′, D′′} the equation Ĥ_{𝔭}(D′, n) = Ĥ_{𝔭}(D′′, n) is fulfilled, and consequently we have that λ̂_{𝔭}(D′, n) = λ̂_{𝔭}(D′′, n). Then it is clear that the respective summands in the sum from the statement differ only in the sign, so they are annuled in the sum, i.e., holds the equation

∑_{D∈D′′_{m}} (−1)^{|ED|} λ̂_{𝔭}(D, n) = ∑_{i=1}^{a_{0}} ∑_{D∈(D′′_{m})_{i}} (−1)^{|ED|} λ̂_{𝔭}(D, n) = 0. (3.2)

The statement of the theorem now follows from (3.1), (3.2) and Theorem 3.1, and the fact that the sets J_{m}, D′′_{m} and D_{m} ∖ D′_{m} form a partition of the set D_{m}. □

Note that every subgraph of a hedgehog is a hedgehog. Let D be a hedgehog. Then denote by Ex(D) the set of all vertices from which at least one edge goes out, by En(D) the set of all vertices in which at least one edge goes in, and by Is(D) the set of all isolated vertices of D. It is clear that Out(D) = Ex(D) ∪ Is(D) ≠ ∅ and In(D) = En(D) ∪ Is(D) ≠ ∅.

Lemma 3.1. ∑_{D∈J_{m}} (−1)^{|ED|} = (−1)^{m−1} .

Proof. The statement will be proved by mathematical induction on number m. It is easy to verify that the formula holds for m = 1 and for m = 2. Let us assume that it holds for every natural number ⩽ m and let us show that then it holds for m + 1. Break J_{m+1} into two parts J′_{m+1} = {D ∈ J_{m+1} | v_{m+1} ∈ In(D)} and J′′_{m+1} = {D ∈ J_{m+1} | v_{m+1} ∈ Ex(D)}.

Let us consider the class J′_{m+1} and break it into subclasses [J′_{m+1} ]_{i}, i ∈ \overline{a_{1}}, so that any two digraphs D, D′ ∈ J′_{m+1} belong to the same class [J′_{m+1} ]_{i_{0}} for some i_{0} ∈ \overline{a_{1}} iff (V_{m}, ED ∖ (V_{m} × \{v_{m+1} \})) = (V_{m}, ED′∖ (V_{m} × \{v_{m+1} \})) = D′_{i_{0}} . Then

σ_{1} = ∑_{D∈J′_{m+1}} (−1)^{|ED|} = ∑_{i=1}^{a_{1}} ∑_{D∈[J′_{m+1} ]_{i}} (−1)^{|ED|}

= ∑_{i=1}^{a_{1}} (−1)^{|ED′_{i}|} ∑_{E′⊆Out (D′_{i})×{v_{m+1} }} (−1)^{|E′|} .

As Out(D′_{i}) ≠ ∅ for every i ∈ \overline{a_{1}}, then

∑_{E′⊆Out (D′_{i})×\{v_{1} \}} (−1)^{|E′|} = 0, for every i ∈ \overline{a_{1}},

i.e., σ_{1} = 0.

Now consider the class J′′_{m+1} and break it into subclasses [J′′_{m+1} ]_{i}, i ∈ \overline{a_{2}}, so that any two digraphs D, D′ ∈ J′′_{m+1} belong to the same class [J′′_{m+1} ]_{i_{0}} for some i_{0} ∈ \overline{a_{2}} iff (V_{m}, ED ∖ (\{v_{m+1} \} × V_{m})) = (V_{m}, ED′∖ (\{v_{m+1} \} × V_{m})) = D′′_{i_{0}}. Note that the set of all D′′_{i}, i ∈ \overline{a_{2}}, is the set J_{m}. Let E′′_{i}= \{v_{m+1} \} × In(D′′_{i}) for every i ∈ \overline{a_{2}}. By the induction hypothesis we have

σ_{2} = ∑_{D∈J′′_{m+1}} (−1)^{|ED|} = ∑_{i=1}^{a_{2}} ∑_{D∈[J′′_{m+1} ]_{i}} (−1)^{|ED|} = ∑_{i=1}^{a_{2}} (−1)^{|ED′′_{i}|}

× ∑_{E′⊆E′′_{i}, E′≠∅} (−1)^{|E′|} = ∑_{i=1}^{a_{2}} (−1)^{|ED′′_{i}|} [ − 1 + ∑_{E′⊆E′′_{i}} (−1)^{|E′|} ]

= (−1) ∑_{i=1}^{a_{2}} (−1)^{|ED′′_{i}|} = (−1) ∑_{D∈J_{m}} (−1)^{|ED|} = (−1)(−1)^{m−1} = (−1)^{m}.

Finally we can write ∑_{D∈J_{m+1}} (−1)^{|ED|} = σ_{1} + σ_{2} = 0 + (−1)^{m} = (−1)^{m}. □

Let X be a set. An ordered m-tuple (Y_{1}, …, Y_{m}), where Y_{i}, i ∈ \overline{m}, are all the blocks of a partition of the set X, is called an ordered partition of the set X.

Let ⩽ be a linear ordering of the set X, and let π be a partition of the set X into m blocks. Denote by Y_{1} the partition block that contains the minimal element of the set X. Let us assume that blocks Y_{1}, …, Y_{k}, 1 ⩽ k < m, of the partition π are taken. Then by Y_{k+1} denote the partition block that contains the minimal element of the set X ∖ ⋃ _{j=1}^{k} Y_{j}. The ordered partition π⃗ = (Y_{1}, …, Y_{m}) is called the ordering of the partition π in respect to the linear ordering ⩽.

Take a hypergraph H ∈ H^{(i)} (D, n). It defines a partition of the set V_{m} into i blocks in such a way that two elements v′, v′′ ∈ V_{m} belong to the same block iff f_{H} (v′) = f_{H} (v′′); denote this partition by π(H, D). Denote by π⃗(H, D) = (V_{m}^{(1)}(H), …, V_{m}^{(i)} (H)) the corresponding ordering of the partition π(H, D) in respect to the linear ordering ⩽_{m} (v_{i} ⩽_{m} v_{j} iff i ⩽ j).

Let H = (e_{1}, …, e_{m}) be an ordered hypergraph. Denote by ⊆_{H} the partial ordering on the set ⟨EH⟩ = {e_{j} | 1 ⩽ j ⩽ m} defined by the relation ⊆. Let 𝔭 = (ℌ_{𝔭}(n), ∼_{𝔭}) be a strong relative equivalence on ℌ(n). Also, let H′ and H′′be two hypergraphs from H_{𝔭}^{(i)} (D, n) for some D ∈ D_{m} such that H′ ∼_{𝔭} H′′. Then, it is easy to show that π⃗(H′, D) = π⃗(H′′, D), and that ⊆_{H′} and ⊆_{H′′} are isomorphic. The latter fact implies correctness of the following notions. Let H be a hypergraph from the set H_{𝔭}^{(i)} (D, n) for some D ∈ D_{m}. Consider the set [H] ∈ ℌ_{𝔭}(n)/∼_{𝔭} where by [H] we mean the class of the equivalence ∼_{𝔭} on ℌ_{𝔭}(n) containing H. If ⊆_{H} is nonempty, we call the class [H] a complex class, in the opposite case we call it a simple class. The set of all complex classes is denoted by ℌ_{1}^{(i)} (𝔭, n) and the set of all simple classes by ℌ_{0}^{(i)} (𝔭, n).

Let 𝔥 be a complex class, and take some H ∈ 𝔥. Let c be a chain of the length ⩾ 1 in (⟨EH⟩, ⊆_{H}). The minimal and maximal element of the chain c are denoted, respectively, by e_{min} (c) and e_{max} (c). It is clear that for each D ∈ J_{m} such that H ∈ H^{(i)} (D, n), it holds that f_{H}^{−1} [e_{min} (c)] ∖ En(D) ≠ ∅ and f_{H}^{−1} [e_{max} (c)] ∖ Ex(D) ≠ ∅ ; otherwise e_{min} (c) and e_{max} (c) could not be, respectively, minimal and maximal element of the chain c. Let f_{H}^{−1} [e_{min} (c)] and f_{H}^{−1} [e_{max} (c)] be, respectively, the i_{c}-th and the j_{c}-th block of the ordered partition π⃗(H, D), and take that

C(H) = { (i_{c}, j_{c}) | c is a chain in (⟨EH⟩, ⊆_{H}) of the length ⩾ 1}.

Let (i_{H} , j_{H}) be the minimal element of the set C(H) in respect to the lexicographic ordering of this set. It is easy to see that for every H′ ∈ 𝔥 holds that (i_{H′} , j_{H′}) = (i_{H} , j_{H}). Because of that by (i_{𝔥}, j_{𝔥}) we mean (i_{H} , j_{H}) for an arbitrary H ∈ 𝔥. Now it is easy to prove the following assertion.

Lemma 3.2. Let 𝔥 ∈ ℌ_{1}^{(i)} (𝔭). Then for every H_{1}, H_{2} ∈ 𝔥 we have

V_{m}^{(i_{H_{1}} )} (H_{1}) = V_{m}^{(i_{H_{2}} )} (H_{2}) = V̂_{1}(𝔥) and V_{m}^{(j_{H_{1}} )} (H_{1}) = V_{m}^{(j_{H_{2}} )} (H_{2}) = V̂_{2}(𝔥).

Lemma 3.3. If 𝔭 is a strong relative equivalence on ℌ(n), then

∑_{D∈J_{m}} (−1)^{|ED|} λ_{𝔭}^{(i)} (D, n) = (−1)^{m−i} · S(m, i) · α_{𝔭}(i, n),

where λ_{𝔭}^{(i)} (D, n) = α_{𝔭}(H^{(i)} (D, n)), and S(n, k) are Stirling numbers of the second kind.

Proof. For a given ordered hypergraph H, EH = i, let us denote by J_{m}(H) the set of all D ∈ J_{m} satisfying the condition H ∈ H^{(i)} (D, n). It is obvious that from H′ ∼_{𝔭} H′′ (H′, H′′ ∈ H^{(i)} (m, n) = H^{(i)} (∅_{m}, n)) it follows that J_{m}(H′) = J_{m}(H′′). By J_{m}(𝔥) (𝔥 ∈ H^{(i)} (m, n)/𝔭) we mean the set J_{m}(H) where H is a hypergraph from 𝔥. Now we have

∑_{D∈J_{m}} (−1)^{|ED|} λ_{𝔭}^{(i)} (D, n) = ∑_{𝔥∈H^{(i)} (m,n)/𝔭} ∑_{𝔥∈H_{m}^{(i)} /𝔭 D∈J_{m} (𝔥)} (−1)^{|ED|}

= ∑_{𝔥∈ℌ_{1}^{(i)} (𝔭)} ∑_{𝔥∈ℌ_{1}^{(i)} (𝔭) D∈J_{m} (𝔥)} (−1)^{|ED|} + ∑_{𝔥∈ℌ_{0}^{(i)} (𝔭)} ∑_{𝔥∈ℌ_{0}^{(i)} (𝔭) D∈J_{m} (𝔥)} (−1)^{|ED|} .

In the above expression denote the first sum after the last sign = by ω_{1}, and the second one by ω_{2}.

Let 𝔥 ∈ ℌ_{1}^{(i)} (𝔭). Let us break the set J_{m}(𝔥) into disjoint classes in the following way: D′ and D′′belong to the same class 𝔡 iff

V̂_{1}(𝔥) ∖ En(D′) = V̂_{1}(𝔥) ∖ En(D′′) = U_{1}(𝔡),
V̂_{2}(𝔥) ∖ Ex(D′) = V̂_{2}(𝔥) ∖ Ex(D′′) = U_{2}(𝔡)

and ED′∖ E_{𝔡} = ED′′∖ E_{𝔡}, where E_{𝔡} = U_{1}(𝔡) × U_{2}(𝔡); denote the corresponding relation of equivalence on J_{m}(𝔥) by ρ. Then

ω_{1} = ∑_{𝔥∈ℌ_{1}^{(i)} (𝔭)} ∑_{𝔥∈ℌ_{1}^{(i)} (𝔭) 𝔡∈J_{m} (𝔥)/ρ} ∑_{𝔥∈ℌ_{1}^{(i)} (𝔭) D∈𝔡} (−1)^{|ED|}

= ∑_{𝔥∈ℌ_{1}^{(i)} (𝔭)} ∑_{𝔥∈ℌ_{1}^{(i)} (𝔭) 𝔡∈J_{m} (𝔥)/ρ} (−1)^{|E_{𝔡}|} ∑_{𝔥∈ℌ_{1}^{(i)} (𝔭) E′⊆E_{𝔡}} (−1)^{|E′|} = 0.

Since 𝔭 is a regular relative equivalence, then exactly one class 𝔞_{𝔥} from the set A_{𝔭}(i, n)/𝔭 corresponds to every simple class 𝔥. Now it is clear that the simple class 𝔥 is completely determined by the class 𝔞_{𝔥} and by the partition π(𝔥) of the set V_{m} into i blocks. There are α_{𝔭}(i, n) such classes and there are S(m, i) such partitions. Denote blocks of the partition π(𝔥) by V_{j} (𝔥), j ∈ \overline{i}. Then it is clear that in every digraph D ∈ J_{m}(𝔥) there does not exist an edge that connects a vertex from the set V_{k}(𝔥) with a vertex from the set V_{l}(𝔥), k, l ∈ \overline{i}, k ≠ l, that is to say, ED ∩ (V_{k}(𝔥) × V_{l}(𝔥)) = ∅ for every k, l ∈ \overline{i}, k ≠ l. Put D′_{k} = (V_{k}(𝔥), ED ∩ V_{k}^{2}(𝔥)) and m_{k} = |V_{k}(𝔥)|; k ∈ \overline{i}. By D_{k}, k ∈ \overline{i}, denote the digraph from J_{m_{k}} that is isomorphic to D′_{k}. It is clear that when D passes the set J_{m}, then the digraph D_{k} passes the whole set J_{m_{k}} for every k ∈ \overline{i}. Using Lemma 3.1 we have

∑_{D∈J_{m} (𝔥)} (−1)^{|ED|} = ∑_{D_{1} ∈J_{m_{1}}} ⋯ ∑_{D_{i} ∈J_{m_{i}}} (−1)^{|ED_{1} |} ⋯ (−1)^{|ED_{i} |}

= ∑_{D_{1} ∈J_{m_{1}}} ⋯ ∑_{D_{i−1} ∈J_{m_{i−1}}} (−1)^{|ED_{1} |} ⋯ (−1)^{|ED_{i−1} |} ∑_{D_{i} ∈J_{m_{i}}} (−1)^{|ED_{i} |}

= (−1)^{m_{i} −1} ∑_{D_{1} ∈J_{m_{1}}} ⋯ ∑_{D_{i−1} ∈J_{m_{i−1}}} (−1)^{|ED_{1} |} ⋯ (−1)^{|ED_{i−1} |} = ⋯

= (−1)^{m_{1} −1} ⋯ (−1)^{m_{i} −1} = (−1)^{m−i} .

Now it is clear that

ω = ω_{2} = ∑_{𝔞_{𝔥}∈A_{𝔭}(i,n)/𝔭} ∑_{π(𝔥)} ∑_{D∈J_{m} (𝔥)} (−1)^{|ED|} = (−1)^{m−i} S(m, i)α_{𝔭}(i, n).  □

Theorem 3.3. If 𝔭 is a strong relative equivalence on ℌ(n), then

α_{𝔭}(m, n) = ∑_{i=1}^{m} |s(m, i)| ∑_{D∈J_{i}} (−1)^{|ED|} λ_{𝔭}(D, n),

where s(n, k) are Stirling numbers of the first kind.

Proof. Let β_{𝔭}(m, n) = ∑ _{D∈J_{m}} (−1)^{|ED|} λ_{𝔭}(D, n). Then from Lemma 3.3 and the equality λ_{𝔭}(D, n) = ∑ _{i=1}^{m} λ_{𝔭}^{(i)} (D, n) it follows that

β_{𝔭}(m, n) = ∑_{i=1}^{m} ∑_{D∈J_{m}} (−1)^{|ED|} λ_{𝔭}^{(i)} (D, n) = ∑_{i=1}^{m} (−1)^{m−i} · S(m, i) · α_{𝔭}(i, n).

Applying the Stirling inversion [4] to the previous formula we get the required equation

α_{𝔭}(m, n) = ∑_{i=1}^{m} |s(m, i)| · β_{𝔭}(i, n) = ∑_{i=1}^{m} |s(m, i)| ∑_{D∈J_{i}} (−1)^{|ED|} λ_{𝔭}(D, n).  □

Denote by Ã_{𝔭}(m, n) the set of all unordered antichains that correspond to ordered antichains from the set A_{𝔭}(m, n). As in an antichain there are no multiple edges, then it is obvious that

(3.3)  α̃_{𝔭}(m, n) = (1/m!) α_{𝔭}(m, n),

where α̃_{𝔭}(m, n) = |Ã_{𝔭}(m, n)|, and from Theorem 3.3 we have the following statement.

Theorem 3.4. If 𝔭 is a strong relative equivalence on ℌ(n), then

α̃_{𝔭}(m, n) = \frac{1}{m!} ∑_{i=1}^{m} |s(m, i)| ∑_{D∈J_{i}} (−1)^{|ED|} λ_{𝔭}(D, n).

For every k_{1}, …, k_{m} ∈ N_{0}, let (jk_{j})\overline{m} = 1k_{1} + 2k_{2} + ⋯+ mk_{m}. Denote by

Y_{n}(x_{1}, x_{2}, …, x_{n}) = ∑_{(jk_{j} )\overline{n} =n} B(k_{1}, …, k_{n}) x_{1}^{k_{1}} x_{2}^{k_{2}} …x_{n}^{k_{n}}

Bell polynomial [6]. Let 𝔭 be a strong relative equivalence on ℌ(n). We say that 𝔭 allows partitioning if λ_{𝔭}(D, n) = λ_{𝔭}(D_{1}, n) λ_{𝔭}(D_{2}, n) …λ_{𝔭}(D_{k}, n), whenever D = D_{1} ∪ D_{2} ∪ ⋯∪ D_{k}. Denote by J_{i}^{c} the set of all connected hedgehogs with i vertices. Then, in the case of a strong relative equivalence which allows partitioning, Theorem 3.3 can be reformulated in the following statement:

Theorem 3.5. If 𝔭 is a strong relative equivalence on ℌ(n) which allows partitioning, then

α̃_{𝔭}(m, n) = \frac{1}{m!} ∑_{i=1}^{m} |s(m, i)| Z(i, n) = \frac{1}{m!} ∑_{i=1}^{m} |s(m, i)| Y_{i}(β(1, n), β(2, n), …, β(i, n))

where β(j, n) = ∑_{D∈J_{j}^{c}} (−1)^{|ED|} λ_{𝔭}(D, n) for every j ∈ \overline{i}.

Proof. Let π be a partition of the set V_{i} of the type 1^{k_{1}} …i^{k_{i}} ; by P_{i}(k_{1}, …, k_{i}) denote the set of all such partitions, and let |π| = k_{1}+⋯ +k_{i}. Define a function f_{π} : \overline{|π|} → \overline{i} in the following way: the value f_{π}(r) (r ∈ \overline{|π|}) is equal to the ordinal number of the first nonpositive number in the sequence r−k_{1}, r−k_{1}−k_{2}, …, r−k_{1}−⋯ −k_{i}. Then we get

∑_{D∈J_{i}} (−1)^{|ED|} λ_{𝔭}(D, n) = ∑_{(jk_{j} )\overline{i} =i} ∑_{π∈P_{i} (k_{1} ,...,k_{i} )}

∑_{D_{i} ∈J_{fπ (i)}^{c} , i∈\overline{|π|}} (−1)^{|E(D_{1} ∪···∪D_{|π|} )|} λ_{𝔭}(D_{1} ∪ ⋯∪ D_{|π|} , n).

But as

∑_{D_{i} ∈J_{fπ (i)}^{c} , i∈\overline{|π|}} (−1)^{|E(D_{1} ∪···∪D_{|π|} )|} λ_{𝔭}(D_{1} ∪ ⋯∪ D_{|π|} , n)

= ∑_{D_{i} ∈J_{fπ (i)}^{c} , i∈\overline{|π|}} (−1)^{|ED_{1} |} λ_{𝔭}(D_{1}, n) ⋯ (−1)^{|ED_{|π|} |} λ_{𝔭}(D_{|π|} , n)

= ∑_{D_{1} ∈J_{fπ (1)}^{c}} (−1)^{|ED_{1} |} λ_{𝔭}(D_{1}, n) ⋯ ∑_{D_{|π|} ∈J_{fπ (|π|)}^{c}} (−1)^{|ED_{|π|} |} λ_{𝔭}(D_{|π|} , n)

= [ ∑_{D∈J_{1}^{c}} (−1)^{|ED|} λ_{𝔭}(D, n)]^{k_{1}} ⋯ [ ∑_{D∈J_{i}^{c}} (−1)^{|ED|} λ_{𝔭}(D, n)]^{k_{i}}

= [β(1, n)]^{k_{1}} ⋯ [β(i, n)]^{k_{i}} ,

we have, finally, that

∑_{D∈J_{i}} (−1)^{|ED|} λ_{𝔭}(D, n) = ∑_{(jk_{j} )\overline{i} =i} ∑_{π∈P_{i} (k_{1} ,...,k_{i} )} [β(1, n)]^{k_{1}} ⋯ [β(i, n)]^{k_{i}}

= ∑_{(jk_{j} )\overline{i} =i} B(k_{1}, k_{2}, …, k_{i}) [β(1, n)]^{k_{1}} ⋯ [β(i, n)]^{k_{i}} = Y (β(1, n), …, β(i, n)). □

For application of the formula from Theorem 3.3 it would be very useful to have some simple necessary conditions for a relative equivalence to be a strong relative equivalence. Let us give one of such conditions. For a given hypergraph H by 𝔐_{H} denote the set of columns of the matrix M_{H}.

Theorem 3.6. Let 𝔭 be a relative equivalence. If 𝔐_{H′} = 𝔐_{H′′} for every H′, H′′∈ ℌ_{𝔭}(n), H′ ∼_{𝔭} H′′, then 𝔭 is a strong relative equivalence.

4. Enumeration of some classes of antichains

In this section we are going to show how to calculate some of the numbers α_{i_{1} i_{2} i_{3}} (m, n) using the above obtained formulas. First of all, let us introduce some notions and give some results that we use in what follows.

Let us introduce two vertex colorings of graphs or digraphs with two colors, red and green. By ↑-coloring of a graph or a digraph we mean a coloring of its vertices with red and green such that adjacent vertices cannot be colored red (here ↑ denotes Sheffer’s stroke or alternative denial), and by ⇒-coloring of a digraph we mean a coloring of this digraph with red and green color such that there is not a vertex colored red from which an edge goes to a vertex colored green. The reason for such naming of these colorings can be easily seen if the red color is replaced by 1 (logically true) and the green by 0 (logically false). For the same reason, a “regular” coloring of a graph with two colors, such that two adjacent vertices are not colored with the same color, could be called a \underline{∨}-coloring, where \underline{∨} is the operation of exclusive disjunction.

Let D be a digraph. Denote by η_{⇒} (D) [η_{↑}(D)] the number of all ⇒-colorings [↑-colorings] of the digraph. Let G be a graph. Denote by η_{↑}(G) the number of all ↑-colorings of G. For given digraph D by \overline{D} denote the graph obtained from D by canceling orientation of its edges. It is easy to prove the following statement.

Proposition 4.1. For an arbitrary hedgehog D ∈ J_{m} the equation η_{⇒} (D) = η_{↑}(D) = η_{↑}(\overline{D}) holds.

It is easy to see that the set of red colored vertices in an η_{↑}-coloring of a digraph (graph) is an independent set of its vertices. Let us also note that the notion of hedgehog is very close to the notion of bipartite graph. Namely, graph \overline{D} is a bipartite graph for every connected hedgehog D. Thus Proposition 4.1 allows to cancel orientations of edges in hedgehogs, and practically to pass from hedgehogs to bipartite graphs, and to consider ↑-colorings instead of ⇒-colorings. Turning to a new type of coloring is not purely formal, but it also seems convenient for the following reasons. The number of all ↑-colorings of a graph G can be calculated in the following way. Denote by G_{v}^{1} the graph that is obtained from G when the point v and all its incident edges are rejected, and by G_{v}^{2} the graph that is obtained from G when v and all its adjacent vertices are rejected, and all the edges incident to some of the rejected vertices are discarded, too. Introduce, formally, a graph without edges and vertices, denote it by ∅_{0}, and take that η_{↑}(∅_{0}) = 1. It is easy to prove the following statements [2].

Proposition 4.2 (Decomposition lemma). η_{↑}(G) = η_{↑}(G_{v}^{1}) + η_{↑}(G_{v}^{2}).

Using the above statement it is easy to calculate numbers η_{↑}(G) for special cases of graph G.

Figure 1. An illustration of Decomposition lemma

Example 4.1. Let K_{n} and K_{m,n} be respectively a complete graph with n vertices and a complete bipartite graph with partition classes consisting of m and n elements. Then η_{↑}(K_{n}) = n + 1 and η_{↑}(K_{m,n} ) = 2^{m} + 2^{n} − 1. If P_{n} is a path with n vertices, then we get Fibonacci sequence η_{↑}(P_{n}) = η_{↑}(P_{n−1} ) + η_{↑}(P_{n−2} ), n = 2, 3, …, η_{↑}(P_{0}) = η_{↑}(∅_{0}) = 1, η_{↑}(P_{1}) = 2. If Z_{n} is an n-cycle, then we get that η_{↑}(Z_{n}) = η_{↑}(P_{n−1} ) + η_{↑}(P_{n−3} ), n ⩾ 3, and, consequently, that η_{↑}(Z_{n+2} ) = η_{↑}(Z_{n+1} ) + η_{↑}(Z_{n}), where η_{↑}(Z_{3}) = 4 i η_{↑}(Z_{4}) = 7.

The proof of the following statement is trivial.

Proposition 4.3. If C_{1}, C_{2}, …, C_{s} are all components (maximal connected subgraphs) of the graph G, then η_{↑}(G) = η_{↑}(C_{1})η_{↑}(C_{2}) …η_{↑}(C_{s}).

Now, let us return to our main problem of finding numbers α_{i_{1} i_{2} i_{3}} (m, n). As (3.3) implies that α_{1i_{2} i_{3}} (m, n) = (1/m!)α_{0i_{2} i_{3}} (m, n), the finding of the numbers α_{1i_{2} i_{3}} (m, n) (i_{2} ∈ \overline{0, 2}, i_{3} ∈ \overline{0, 3}) can be reduced to the calculation of the numbers α_{0i_{2} i_{3}} (m, n). Let us show how to calculate some of the numbers α_{0i_{2} i_{3}} (m, n) using appropriate strong relative equivalence 𝔭_{i_{2} i_{3}} . Denote by λ_{i_{2} i_{3}} (D, n) the number λ_{𝔭_{i_{2} i_{3}}} (D, n). So as not to overload the text with unnecessary details, we will adduce formulas only for the numbers λ_{i_{2} i_{3}} (D, n), as the numbers α_{0i_{2} i_{3}} (m, n) can be calculated by the use of the main formula from Theorem 3.4.

It is easy to note that if H ∈ H(D, n), then every column of the matrix M_{H} defines a ⇒-coloring of the digraph D. Also, it is clear that every n-tuple of ⇒- colorings defines a hypergraph from H(D, n). So, |H(D, n)| = η\underrightarrow{n} (D). Now from Proposition 4.1 it follows that if D is a hedgehog, then every column of the matrix M_{H} defines a ↑-coloring for every H ∈ H(D, n). Corollaries 4.1–4.4 follow easily from this observation.

Corollary 4.1. If 𝔭_{23} = (ℌ(n), =), then λ_{23}(D, n) = η\underrightarrow{n} (D) = η_{↑}^{n}(D) for

every D ∈ J_{m}.

Class A_{023} is closely connected with the Post class M of all monotone Boolean functions. Let us explain this connection.

For every two binary n-tuples (a_{1}, …, a_{n}), and (b_{1}, …, b_{n}), we write

(a_{1}, …, a_{n}) ⩽ (b_{1}, …, b_{n}) if a_{i} ⩽ b_{i} for every i = 1, …, n.

If (a_{1}, …, a_{n}) ⩽ (b_{1}, …, b_{n}) and there is some i_{0}, 0 ⩽ i_{0} ⩽ n, such that a_{i_{0}} < b_{i_{0}} , then we write that (a_{1}, …, a_{n}) < (b_{1}, …, b_{n}). A Boolean function f of n variables is monotone if for every two binary n-tuples, (a_{1}, …, a_{n}) and (b_{1}, …, b_{n}), from (a_{1}, …, a_{n}) ⩽ (b_{1}, …, b_{n}) it follows that f(a_{1}, …, a_{n}) ⩽ f(b_{1}, …, b_{n}); denote by M(n) the class of all such functions. Then M = ∪_{n=1}^{∞} M(n).

The problem of counting the number of elements of the classes M(n) has a long history and is known as the Dedekind’s problem. It was formulated by Dedekind in [1] as far back as in 1897 as the problem of determining the number of elements in a free distributive lattice F D(n) on n generators (see also, [5]). In terms of the set theory the problem is equivalent to the problem of determining the number of all antichains on an n-set. The solution of the problem can be attempted in the following way.

Let f be an arbitrary monotone Boolean function of n variables. A binary n-tuple (a_{1}, a_{2}, …, a_{n}) is a lower unit for f if f(a_{1}, a_{2}, …, a_{n}) = 1 and for every (b_{1}, b_{2}, …, b_{n}) < (a_{1}, a_{2}, …, a_{n}) it holds that f(b_{1}, b_{2}, …, b_{n}) = 0. It is easy to note that the function f is uniquely defined by the set U(f) of its lower units.

Denote by M(m, n) the set of all monotone Boolean functions of n variables with exactly m lower units (“mincuts”). Let α(m, n) = |M(m, n)|. As it is known from famous Sperner’s lemma [4], m takes values from 0 to \binom{n}{⌊n/2⌋}, so

|M(n)| = \begin{matrix}( & {n \atop ⌊n/2⌋} & ) \\ ∑ \\ m=0 \end{matrix}|M(m, n)|.

Therefore, we can enumerate the class M(n) in such a way as to enumerate classes M(m, n). A brief history of the problem of enumeration of the classes M(m, n) can be found in [2, 3]. Let us deduce the main result from [3]. Let a = (a_{1}, …, a_{n}) be a binary n-tuple. By V (a) denote the subset of the set V_{n} such that v_{i} ∈ V (a) iff a_{i} = 1.

Let f be a monotone Boolean function from the set M(m, n). Denote by H_{f} hypergraf (V_{n}, E(f)), where E(f) = {V (a) | a ∈ U(f)}. Note that H_{f} is an unordered labeled (m, n)-antichain (an (m, n)-hypergraph that is an antichain). Now, it is easy to see that the correspondence f_{H} → H defines a bijection between M(m, n) and the set A_{123}. Using Corollary 4.1 and Theorem 3.4 we have the following statement.

Theorem 4.1. α_{123}(m, n) = \frac{1}{m!} ∑_{i=1}^{m} |s(m, i)| ∑_{D∈J_{m}} (−1)^{|ED|} η_{↑}^{n}(D).

If for a labeled ordered (m, n)-antichain H we observe a corresponding dual labeled ordered hypergraph H^{T}, then it is easy to see that it is a labeled ordered T_{1}-hypergraph with m vertices and n hyperedges, and, consequently, it is also a cover. Thus, t_{00111} (m, n) = α_{023}(n, m).

Let us consider the class A_{022}(m, n) of all ordered (m, n)-T_{0}-antichains.

Corollary 4.2. If 𝔭_{22} = (ℌ′(n)), =), where ℌ′(n) is the set of all hypergraphs H ∈ ℌ(n) such that in M_{H} all columns are different, then

λ_{22}(D, n) = [η_{↑}(D)]_{n} = η_{↑}(D)(η_{↑}(D) − 1) …(η_{↑}(D) − n + 1)

for every D ∈ J_{m}.

Now consider the class T_{10023} (m, n) of all ordered unlabeled (m, n)-antichains. Then we have the following statement.

Corollary 4.3. If 𝔭 = (ℌ(n), ∼), where H_{1} ∼ H_{2} iff the multisets defined by the columns of the matrices of the hypergraphs H_{1} and H_{2} are equal, then

λ_{𝔭}(D, n) = \binom{η_{↑}(D) + n − 1}{n} for every D ∈ J_{m}.

For the class T_{10022} (m, n) of all ordered unlabeled (m, n)-T_{0}-antichains we have

Corollary 4.4. If 𝔭 = (ℌ′(n), ∼), where H_{1} ∼ H_{2} iff 𝔐_{H_{1}} = 𝔐_{H_{2}} , then

λ_{𝔭}(D, n) = \binom{η_{↑}(D)}{n} for every D ∈ J_{m}.

Let us note that we get the formulas for the corresponding “cover” cases if in the above formulas we replace η_{↑}(D) by η_{↑}(D) − 1 because the incidence matrix of a cover does not contain zero column. Thus we solve the cases of the classes A_{023}(m, n), A_{022}(m, n), T_{10023} (m, n), T_{10022} (m, n), A_{013}(m, n), A_{012}(m, n), T_{10013} (m, n) and T_{10012} (m, n). Using (3.3) we also get the corresponding formulas for the classes A_{123}(m, n), A_{122}(m, n), A_{113}(m, n), and A_{112}(m, n).

5. Calculations, examples and data

It is easy to see that the following proposition holds.

Proposition 5.1. For every hedgehog D, η_{↑}(D) = η_{↑}(D^{−1} ).

Let J_{s,t}^{c} be a set of all connected hedgehogs D such that |Ex(D)| = s and |En(D)| = t. If we consider the case of strong relative equivalence on ℌ(n) from Corollary 4.1 by using Theorem 3.3 and Theorem 3.5 we get the following proposition:

Proposition 5.2. It holds that

α_{123}(m, n) = \frac{1}{m!} ∑_{i=1}^{m} |s(m, i)| Z(i, n), (5.1)

where

Z(i, n) = Y_{i}(β(1, n), β(2, n), …, β(i, n)),
β(1, n) = 2^{n}, β(j, n) = ∑_{k=1}^{j−1} \binom{j}{k} b(k, j − k), 2 ⩽ j ⩽ i,
b(s, t)= ∑_{D∈J_{s,t}^{c}} (−1)^{|ED|} η_{↑}^{n}(D), s, t ⩾ 1.

Let k_{1}, …, k_{i} ∈ N_{0} be nonnegative numbers such that (jk_{j})\overline{i} = i. Denote by J (k_{1}, …, k_{i}) the set of all hedgehogs D_{1} ∪ ⋯∪ D_{k_{1} +···+k_{i}} such that D_{i} ∈ J_{f_{π} (i)} for every i ∈ \overline{k_{1} + ⋯+ k_{i}} , where f_{π} is the function defined in the proof of Theorem 3.5 for the partition type 1^{k_{1}} 2^{k_{2}} … i^{k_{i}} . By J (k_{1}, …, k_{i}; l) denote the set of all hedgehogs D from J (k_{1}, …, k_{i}) such that η_{↑}(D) = l. Let j(k_{1}, …, k_{i}; l) = |J (k_{1}, …, k_{i}; l)|. It is clear that the following proposition holds.

Proposition 5.3. If 𝔭 is a strong relative equivalence on ℌ(n), satisfying λ_{𝔭}(D, n) = g(η_{↑}(D)) for every D ∈ J, then the number α_{123}(m, n) is equal to

\frac{1}{m!} ∑_{i=1}^{m} ∑_{(jk_{j} )\overline{i} =i} ∑_{l=1}^{2^{i}} |s(m, i)|B(k_{1}, …, k_{i}) j(k_{1}, …, k_{i}; l)g(l).

Example 5.1. Using Example 4.1 we get

b(1, t) = ∑_{J∈J_{1,t}^{c}} (−1)^{|EJ|} η_{↑}^{n}(J) = (−1)^{|EK_{1,t} |} η_{↑}^{n}(K_{1,t}) = (−1)^{t}(2^{t} + 1)^{n},

and consequently we have that b(1, 1) = −3^{n}, b(1, 2) = 5^{n}, b(1, 3) = −9^{n}, b(1, 4) = 17^{n}, b(1, 5) = −33^{n}, and b(1, 6) = 65^{n}.

It is clear that b(s, t) = b(t, s). So, in order to calculate α_{123}(m, n), 1 ⩽ m ⩽ 7, it is sufficient to consider classes J_{2,2}^{c}, J_{2,3}^{c}, J_{2,4}^{c}, J_{3,3}^{c}, J_{2,5}^{c} and J_{3,4}^{c}. In the given table beside each graph there are two numbers, the upper one gives the number of its isomorphic graphs, and the lower one gives the corresponding number η_{↑}, which is easily calculated with the help of Decomposition Lemma; the graphs are classified by the degree of the vertices of their lower parts (they are given below the graphs in the form of the corresponding tuples). Define the operation | in the following way: for every a, b ∈ N, let a|b = a · b^{n} (here n is fixed). Now using formula (5.1) and the table (Fig. 2), we get

b(1, 1) = −1|3;  b(1, 2) = 1|5;  b(1, 3) = −1|9,  b(2, 2) = −4|8 + 1|7;

b(1, 4) = 1|17, b(2, 3) = 6|14 + 6|13 − 6|12 + 1|11; b(1, 5) = −1|33, b(2, 4) = −24|23 − 8|26 + 12|21 + 12|22 − 8|20 + 1|19, b(3, 3) = −18|22 − 36|21 + 18|19 + 6|18 − 18|22 − 9|24 + 18|19 + 36|20−

18|17 − 9|18 − 9|18 + 9|16 − 1|15;

b(1, 6) = 1|65, b(2, 5) = 10|50 + 40|43 + 30|41 − 20|42 − 60|39 + 20|38 + 20|37 − 10|36 + 1|35, b(3, 4) = 144|36 + 36|40 + 72|34 + 72|37 − 72|31 − 72|33 − 72|34 − 72|31 + 24|31+

18|29 + 36|28 + 24|35 + 72|38 + 12|44 − 144|32 − 72|34 − 72|36 − 36|33+ 72|30 + 72|32 + 144|29 + 36|29 − 72|27 − 12|30 − 24|26 + 36|30 + 18|32− 36|27 − 72|28 + 36|25 + 18|26 + 12|26 − 12|24 + 1|23

and

β(1, n) = 1|2, β(2, n) = −2|3, β(3, n) = 6|5, β(4, n) = −8|9 − 24|8 + 6|7, β(5, n) = 10|17 + 120|14 + 120|13 − 120|12 + 20|11, β(6, n) = −12|33 − 240|26 − 180|24 − 720|23 − 360|22 − 360|21 + 480|20+

750|19 − 240|18 − 360|17 + 180|16 − 20|15,

β(7, n) = 14|65 + 420|50 + 840|44 + 1680|43 − 840|42 + 1260|41 + 2520|40− 2520|39 + 5880|38 + 5880|37 + 4620|36 + 1722|35 − 5040|34− 7560|33 − 3780|32 − 8400|31 + 6720|30 + 13860|29 − 2520|28− 7560|27 + 420|26 + 2520|25 − 840|24 + 70|23.

Replacing x_{i} with β(i, n) in Bell polynomials Y_{i}(x_{1}, …, x_{i}), i = 1, 2, …, 7,

Y_{1} = x_{1} ,  Y_{2} = x_{1}^{2} + x_{2} ,  Y_{3} = x_{1}^{3} + 3x_{1} x_{2} + x_{3} ,

Y_{4} = x_{1}^{4} + 6x_{1}^{2} x_{2} + 4x_{1} x_{3} + 3x_{2}^{2} + x_{4} , Y_{5} = x_{1}^{5} + 10x_{1}^{3} x_{2} + 10x_{1}^{2} x_{3} + 15x_{1} x_{2}^{2} + 5x_{1} x_{4} + 10x_{2} x_{3} + x_{5} , Y_{6} = x_{1}^{6} + 15x_{1}^{4} x_{2} + 45x_{1}^{2} x_{2}^{2} + 15x_{2}^{3} + 20x_{1}^{3} x_{3} + 60x_{1} x_{2} x_{3} + 10x_{3}^{2} + 15x_{1}^{2} x_{4} +

15x_{2} x_{4} + 6x_{1} x_{5} + x_{6} , Y_{7} = x_{1}^{7} + 21x_{1}^{5} x_{2} + 105x_{1}^{3} x_{2}^{2} + 105x_{1} x_{2}^{3} + 35x_{1}^{4} x_{3} + 210x_{1}^{2} x_{2} x_{3} + 105x_{2}^{2} x_{3} +

70x_{1} x_{3}^{2} + 35x_{1}^{3} x_{4} + 105x_{1} x_{2} x_{4} + 35x_{3} x_{4} + 21x_{1}^{2} x_{5} + 21x_{2} x_{5} + 7x_{1} x_{6} + x_{7} ,

we get respectively the values

Z(1, n) = 1|2,  Z(2, n) = 1|4 − 2|3,  Z(3, n) = 1|8 − 6|6 + 6|5,

Z(4, n) = 1|16 − 12|12 + 24|10 + 4|9 − 24|8 + 6|7, Z(5, n) = 1|32 − 20|24 + 60|20 + 20|18 + 10|17 − 120|16 − 120|15+

150|14 + 120|13 − 120|12 + 20|11,

Z(6, n) = 1|64 − 30|48 + 120|40 + 60|36 + 60|34 − 12|33 − 360|32 − 720|30+ 810|28 + 120|27 + 480|26 + 360|25 − 180|24 − 720|23 − 240|22− 540|21 + 480|20 + 750|19 − 240|18 − 360|17 + 180|16 − 20|15,

Z(7, n) = 1|128 − 42|96 + 210|80 + 140|72 + 210|68 − 84|66 + 14|65 − 840|64− 2520|60 + 2730|56 + 840|54 + 840|52 − 420|51 + 2940|50 + 1260|48− 5040|46 + 840|45 − 1260|44 + 1680|43 − 9660|42 + 1260|41 + 840|40− 7560|39 + 11130|38 + 5880|37 + 7980|36 + 2982|35 − 7560|34− 8400|33 − 2520|32 − 8400|31 + 6580|30 + 13860|29 − 2520|28− 7560|27 + 420|26 + 2520|25 − 840|24 + 70|23,

Figure 2. Nonisomorphic hedgehogs (having up to 7 vertices) with the corresponding number of isomorphic copies, and the number of their ↑-colorings and from this we finally calculate formulas α̂(m, n) = α_{123}(m, n) (1 ⩽ m ⩽ 7):

α̂(1, n) =  1|2,
α̂(2, n) =  (1|4 − 2|3 + 2)/2!,
α̂(3, n) =  (1|8 − 6|6 + 6|5 + 3|4 − 6|3 + 2|2)/3!,
α̂(4, n) =  (1|16 − 12|12 + 24|10 + 4|9 − 18|8 + 6|7 − 36|6+
36|5 + 11|4 − 22|3 + 6|2)/4!,
α̂(5, n) =  (1|32 − 20|24 + 60|20 + 20|18 + 10|17 − 110|16 − 120|15 + 150|14+
120|13 − 240|12 + 20|11 + 240|10 + 40|9 − 205|8 + 60|7 − 210|6+
210|5 + 50|4 − 100|3 + 24|2)/5!,
α̂(6, n) =  (1|64 − 30|48 + 120|40 + 60|36 + 60|34 − 12|33 − 345|32 − 720|30+
810|28 + 120|27 + 480|26 + 360|25 − 480|24 − 720|23 − 240|22−
540|21 + 1380|20 + 750|19 + 60|18 − 210|17 − 1535|16 − 1820|15+
2250|14 + 1800|13 − 2820|12 + 300|11 + 2040|10 + 340|9 − 1815|8+
510|7 − 1350|6 + 1350|5 + 274|4 − 548|3 + 120|2)/6!,
α̂(7, n) =  (1|128 − 42|96 + 210|80 + 140|72 + 210|68 − 84|66 + 14|65 − 819|64−
2520|60 + 2730|56 + 840|54 + 840|52 − 420|51 + 2940|50 + 630|48−
5040|46 + 840|45 − 1260|44 + 1680|43 − 9660|42 + 1260|41+
3360|40 − 7560|39 + 11130|38 + 5880|37 + 9240|36 + 2982|35−
6300|34 − 8652|33 − 9905|32 − 8400|31 − 8540|30 + 13860|29+
14490|28 − 5040|27 + 10500|26 + 10080|25 − 8120|24 − 15050|23−
5040|22 − 11340|21 + 20580|20 + 15750|19 − 1540|18 − 5810|17−
16485|16 − 21420|15 + 26250|14 + 21000|13 − 29820|12 + 3500|11+
17640|10 + 2940|9 − 16016|8 + 4410|7 − 9744|6 + 9744|5 + 1764|4−
3528|3 + 720|2)/7!.

Riviere [7] found the formulas for α̂(m, n), 1 ⩽ m ⩽ 3. Cvetković [8] calculated the number α̂(4, n) by using computer, in fact by using the method of exhaustive search. Arocha [9] gave explicit formulas for the numbers α̂(5, n) and α̂(6, n). The above formulas, as well as the corresponding formulas for α̂(m, n), 8 ⩽ m ⩽ 10, together with their values for small n are presented in [10]. Using formula (5.1) and data from [11] for bipartite graphs the formulas for α̂(m, n) could be generated by computer up to m = 15.

We obtained the above formulas using Proposition 5.2, but it is easy to see that the formulas have the form of the formula given in Theorem 3.5, so by changing the meaning of the operation | we can get the corresponding formulas for all other classes given in Section 4. For example, we can get the number of all labeled ordered T_{0}-(3, n)-antichains from α̂(3, n), if we put that a|b = a · [b]_{n}, and we obtain

α_{022}(3, n) = ([8]_{n} − 6[6]_{n} + 6[5]_{n} + 3[4]_{n} − 6[3]_{n} + 2[2]_{n})/3!.

We get the number of all unlabeled ordered (3, n)-antichains from α̂(3, n), if we put that a|b = a · C_{b+n−1}^{n} , and delete 3! in the denominator; so we obtain that

t_{10023} (3, n) = C_{n+7}^{n} − 6C_{n+5}^{n} + 6C_{n+4}^{n} + 3C_{n+3}^{n} − 6C_{n+2}^{n} + 2C_{n+1}^{n} .

We get the number of all unlabeled ordered (3, n)-T_{0}-antichains from α̂(3, n), if we put that a|b = a · C_{b}^{n}, and delete 3! in denominator. So we have that

t_{10022} (3, n) = C_{8}^{n} − 6C_{6}^{n} + 6C_{5}^{n} + 3C_{4}^{n} − 6C_{3}^{n} + 2C_{2}^{n}.

References

1. R. Dedekind, Ueber Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler; in: “Festschrift Hoch. Braunschweig u. ges. Werke” Vol. II, 1897, 103–148.

2. G. Kilibarda, V. Jovović, Antichains of multisets, J. Integer Sequences 7(1) (2004), Article 04.1.5.

3. �� ���������� �� �������� � ����� ���������� ������� ������� � ������������� ������ ������ ������� ���������������� ������� 7 (2003), 299–322.

4. M. Aigner, Combinatorial Theory, Springer-Verlag, New York, 1979.

5. G. Birkhoff, Lattice Theory, Providence, Rhode Island, 1967.

6. J. Riordan, Combinatorial Identities, Wiley, New York–London–Sydney, 1968.

7. N. M. Riviere, Recursive formulas on free distributive lattices, J. Combinatorial Theory 5 (1968), 229–234.

8. D. Cvetković, The number of antichains of finite power sets, Publ. Inst. Math., Nouv. Sér. 13(27) (1972), 5–9.

9. J. L. Arocha, ����� ��������� ����� � � �, VINITI 06.04.82. Reg. #1631-82 Dep., 1982.

10. N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/∼njas/sequences/index.html

11. G. Royle, Small Graphs, http://people.csse.uwa.edu.au/gordon/remote/graphs/

Department of Mathematics (Received 09 01 2014) ALFA University Belgrade Serbia

   gkilibar@gmail.com