On the Number of Antichains and Antichain Covers of Labeled Sets

Paweł Marcin Kozyra Institute of Mathematics Pedagogical University of Krakow Podchora̧żych 2 30-084 Krakow Poland

                    pawelmkozyra@gmail.com

Abstract We present a formula for the number of antichains consisting of m subsets of a labeled n-element set, as well as a formula for the number of all m-antichain covers of a labeled n-element set. We also give a simple formula for the number of antichain covers that are composed of sets of the same cardinality.

1 Introduction and preliminaries

In 1897 Dedekind [7] formulated the following question: Question 1. What is the number of antichains in the power set P_{n} of an n-element set (ordered by inclusion)?

Dedekind’s problem and the related problem of determining the number of all antichain covers of a labeled n-element set remained unsolved for a long time [20]. These are very difficult—and still baffling—counting problems. Before we formulate these problems precisely, let us define some necessary and fundamental notions. Definition 2. [21, Def. 1.1.1, p. 2] An ordered set (or partially ordered set or poset) is an ordered pair (P, ≤) of a set P and a binary relation ≤ contained in P × P, called the order (or the partial order) on P, such that:

1. The relation ≤ is reflexive, i.e., ∀_{p∈P} (p ≤ p).

2. The relation ≤ is antisymmetric, that is,

∀_{p,q∈P} (((p ≤ q) ∧ (q ≤ p)) ⟹ p = q).

3. The relation ≤ is transitive, i.e.,

∀_{p,q,r∈P} (((p ≤ q) ∧ (q ≤ r)) ⟹ p ≤ r).

The power set P_{n} of an n-element set with the inclusion ⊆ relation is an example of an order set. Another key notion is an antichain defined as follows:

Definition 3. [21, Def. 2.5.1, p. 36] An ordered set P is called an antichain iff

∀_{p,q∈P} (p ≠ q) ⟹ (¬p ≤ q ∧ ¬q ≤ p).

Now we can define the n-th Dedekind number and related numbers.

Definition 4. [21, Def. 2.6.2, p. 39] Let n ∈ ℕ. We define

1. The n-th Dedekind number D_{n} to be the number of antichains in P_{n}.

2. T_{n} to be the number of antichain covers of a labeled n-element set, i.e., the number of antichains in P({1, …, n}) such that the union of these antichains is {1, …, n}.

Since the empty set is an antichain, we obtain straightforwardly: D_{0} = T_{0} = 1, D_{1} = 2, and T_{1} = 1. Hitherto only nine initial values of numbers D_{n} and T_{n} have been determined. They are listed in the On-Line Encyclopedia of Integer Sequences [22] as \underline{A000372} and \underline{A006126}, respectively. Dedekind’s problem, in turn, is equivalent to the problem of determining the number of elements in the free bounded distributive lattice on n generators which is the same as the number of monotone Boolean functions in n arguments. T_{n} is defined primarily in the On-Line Encyclopedia of Integer Sequences as the number of hierarchical models on n labeled factors or variables with linear terms forced. Kilibarda and Janovic [11] obtained the antichain cover interpretation of \underline{A006126}.

An approach to solving Dedekind’s problem and related problems is to break the problem into smaller subproblems. There is a simple relation between D_{n} and T_{n}.

Proposition 5. [21, Prop. 2.6.3, p. 40]

D_{n} = ∑_{k=0}^{n} \binom{n}{k}T_{k}.  (1)

Any antichain (cover) in P_{n} is a Sperner family. Therefore by Sperner’s theorem [23], for every antichain (cover) C = \{A_{1}, …, A_{m}\} in P_{n} we have m ≤ \binom{n}{⌊n/2⌋}, where ⌊x⌋ := max\{k ∈ ℤ: k ≤ x} for any real number x ∈ ℝ. It follows from the above considerations that if • D_{n}^{m} is the number of all m-element antichains in P_{n}

• T_{n}^{m} is the number of all m-element antichain covers (m-antichain covers) in P_{n}

then

D_{n} = \begin{matrix}( & {n \atop ⌊n/2⌋} & ) \\ ∑ \\ m=0 \end{matrix} D_{n}^{m} and T_{n} = \begin{matrix}( & {n \atop ⌊n/2⌋} & ) \\ ∑ \\ m=0 \end{matrix} T_{n}^{m}  (2)

for all n ∈ ℕ. The number T_{n}^{2} of all 2-antichain covers of a labeled n-element set coincides with Stirling numbers of second kind S(n, 3) as one can see in Tables 1, 3, and 4 as well as in the On-Line Encyclopedia of Integer Sequences [22] — the sequence \underline{A000392}. Then T_{n}^{2} can be easily determined by the following result.

Proposition 6. [21, Prop. 2.6.6, p. 40]

T_{n}^{2} = \frac{1}{2} ∑_{k=1}^{n−1} \binom{n}{k} (2^{k} − 1) , for all n ≥ 2.  (3)

Similarly, numbers of 3-antichain and 4-antichain covers of a labeled n-set are listed in the On-Line Encyclopedia of Integer Sequences [22] as the sequences \underline{A056046} and \underline{A056047}, respectively. Jovovic and Kilibarda [10] consider these sequences in detail. In particular, they provide simple formulas for these sequences.

In contrast to the problem of determining T_{n}, Nelsen and Schmidt [19] relatively easily enumerated the chains in the power set of X. Similarly, Macula [18] easily established the number of all (proper) covers of an n-element set as well as the number of all (proper) covers of length m of an n-element set, where 1 ≤ m ≤ 2^{n} − 1. Clarke [6] considered this problem more generally. In his approach, for a given n-element set X (n-set) and a positive integer k, a k-cover of X is a collection of k (not necessarily distinct) subsets of X, whose union is X. A k-cover is minimal if none of its proper subsets covers X. There are four cases to consider: the element of X may be taken to be identical (X is unlabeled) or distinguishable (X is labeled); the order of the sets comprising the k-cover of X may (cover is ordered) or may not be material (cover is disordered). Clarke quoted formulas derived by Hearne and Wagner [9, 24] for the number of (minimal) ordered k-covers of a labeled n-set, the number of ordered k-covers of an unlabeled n-set, and the number of (minimal) disordered k-covers of a labeled n-set. Moreover, Clarke [6] presented and proved a formula for the number of disordered k-covers of an unlabeled n-set.

Kisielewicz [14] proved that

D_{n} = ∑_{k=1}^{2^{2^{n}}} ∏_{0≤i<j≤2^{n}−1} (1 − b_{i}^{k} · b_{j}^{k} · f(i, j)),  (4)

where b_{i}^{n} = ⌊n/2^{i}⌋ − 2⌊n/2^{i+1}⌋ for any i, n ≥ 0, ⌊x⌋ := max{k ∈ ℤ: k ≤ x} for any real number x ∈ ℝ,

f(i, n) = \begin{cases}1, & if i ∈ S(n); \\ 0, & otherwise; \end{cases} = \begin{cases}1, & if i = 0; \\ ∏_{m=0}^{log_{2}(i)} (1 − b_{m}^{i} + b_{m}^{i}b_{m}^{n}), & for i ≥ 1; \end{cases}

and sets S(n) are defined recursively as follows:

S(0) = {0} and for n ≥ 0:
S(2n) = {2s: s ∈ S(n)}
S(2n + 1) = S(2n) ∪ {2s + 1: s ∈ S(n)}.

Church [4] computed the first six elements of the sequence \underline{A000372}, Ward [25] determined D_{6}, Church [5] calculated D_{7}, and Wiedemann [26] computed D_{8}. In recent years, Bakoev, Fidytek et al. [1, 8] tried to improve the computational time. Since obtaining the exact values of Dedekind numbers and related numbers is a very challenging task, many authors tried to determine upper bounds on the Dedekind numbers. In 1969 Kleitman [15] found an upper bound on the logarithm of the Dedekind number. His result was next improved by Kleitman and Markowsky [16] in 1975. In 1981, Korshunov [17] found more sophisticated and accurate estimates. Kahn [12] simplified proofs of these estimates using an ‘entropy’ approach.

Baumann and Strass [2] proved that the number of bipolar Boolean functions in n arguments is equal to

b(n) = ∑_{i=0}^{n} 2^{i} · \binom{n}{i} · T_{i}

and the number of all monotone Boolean functions in n arguments is equal to D_{n}. A similar result comes from [21, Prop. 2.6.7, p. 41].

Proposition 7. Let P be a finite ordered set. Then the number of antichains in P is equal to the number of order-preserving maps from P into the two-element chain.

De Causmaecker and De Wannemacker [3] generalized Dedekind’s problem to analysis of the number of antichains in intervals [α, β] = {χ ∈ A_{N}: α ≤ χ ≤ β} in a completely distributive lattice (A_{N}, ∧, ∨) for any α, β ∈ A_{N}, where A_{N} is the set of all antichains in N ⊆ ℕ. Moreover if N = {1, 2, …, n} then A_{N} is denoted by A_{n}. Antichains α, β ∈ A_{N} are partly ordered as

α ≤ β ⟺ ∀_{A∈α}∃_{B∈β}: A ⊆ B.

The operators ∧ and ∨ are called meet and join, respectively, and are defined in the following way:

α ∨ β = max(α ∪ β), α ∧ β = max({A ∩ B: A ∈ α, B ∈ β})

The max-operator on an arbitrary set of sets produces an antichain containing only the non dominated sets. For X ⊆ N, X^{−} = {X \ {x}: x ∈ X} and for antichain α denote α^{−} = ⋁_{X∈α} X^{−} and α^{+} = ⋁_{X∈2^{N} ,X^{−}≤α}{X}. For each interval [α, β] the underlying interval poset of [α, β] is defined as follows

P_{[α,β]} = ({X ⊆ N: α ∨ {X} ∈]α, β]}, ⊆).

Given an interval [α, β], with α < β so that P_{[α,β]} ≠ ∅, let l_{0} denote the size of the smallest sets in P_{[α,β]} and l_{i} = l_{0} + i. For any l ∈ ℕ let λ_{l} = {X ∈ P_{[α,β]} : |X| = l}. For χ ⊆ λ_{l} define χ^{+} = {X ∈ λ_{l+1} : X^{−} ∩ λ_{l} ⊆ χ} and for l > l_{0}, χ^{−} = {X^{−} ∩ λ_{l−1} : X ∈ χ}. De Causmaecker and De Wannemacker [3] proved that with the above notation, for α ≤ β ∈ A_{N}, the size of the interval [α, β] is given by

|[α, β]| = ∑_{χ_{0}⊆λ_{l_{0}}} ∑_{χ_{2}⊆χ_{0}^{++}} ∑_{χ_{4}⊆χ_{2}^{++}} ⋯ 2^{|χ_{0}^{+}|−|χ_{2}^{−}|+|χ_{2}^{+}|−|χ_{4}^{−}|...}  (5)

= ∑_{χ_{1}⊆λ_{l_{1}}} ∑_{χ_{3}⊆χ_{1}^{++}} ∑_{χ_{5}⊆χ_{3}^{++}} ⋯ 2^{|λ_{l_{0}}|−|χ_{1}^{−}|+|χ_{1}^{+}|−|χ_{3}^{−}|...}  (6)

Let B_{n} ⊆ A_{n} denote a basic interval of dimension n, i.e.,

B_{n} = [{{1}, {2}, …, {n}}, {{1, 2, …, n}}].

Then from the well-known decomposition for the Dedekind numbers D_{n} = |A_{n}| = ∑_{k=0}^{n} |B_{k}|

and from (1) it follows that T_{n} = |B_{n}| for all natural numbers n. Thus both T_{n} and D_{n} can be efficiently computed by (5) or (6) up to n = 6.

Kilibarda [13] presents another generalization of Dedekind’s problem. He defines an antichain as a hypergraph satisfying the following property: for every pair of distinct edges, neither one is a subset of the other. Kilibarda [13] enumerates antichains given on an nset having some 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 following part of this article is organized as follows. The second section is devoted to the derivation of the new elegant result — Theorem 11, concerning numbers D_{n}^{m} and T_{n}^{m} for all m, n ≥ 2 and m ≤ \binom{n}{⌊n/2⌋}. This theorem is preceded by Example 10, which allows easier comprehension of the intuition behind Theorem 11. Proof of Theorem 11 is divided into four Lemmas 14–17 that explicitly and accurately explain the computational process to obtain the formulae (39) and (40) from this theorem.

The third section concerns the number of covers of a labeled n-element set X with antichains consisting of m equinumerous subsets of X.

The last section contains Example 20 demonstrating the use of Theorem 11 for computing the number of all 2 and 3-antichain covers as well as the number of all 2 and 3 element antichains in the power set P_{n}. In this section, some numerical experiments are also shown. In particular, this section presents:

• values of \underline{A016269} — sequence of numbers of monotone Boolean functions of n − 2 variables with 2 mincuts, that is, sequence of numbers D_{n}^{2} for n ∈ {4, …, 15}; • values of sequences \underline{A047707} and \underline{A051112} of numbers of monotone Boolean functions

of n variables with 3 and 4 mincuts, respectively, that is, sequences of numbers D_{n}^{3} and D_{n}^{4} for n ∈ {4, …, 15};

• values of sequence \underline{A000392} of Stirling numbers of second kind S(n+1, 3), i.e., sequence of numbers T_{n}^{2} for n ∈ {4, …, 50};

• values of sequence \underline{A056046} of numbers T_{n}^{3} for n ∈ \{4, …, 50\};

• values of sequence \underline{A056047} of numbers T_{n}^{4} for n ∈ \{4, …, 15\};

• the numbers of covers of 7-set with antichains consisting of equinumerous sets.

2 Antichains and antichain covers consisting of m subsets of a labeled n-element set

Let ℤ_{n} denote the set {0, 1, …, n − 1}, and we let ℤ_{n}^{+} denote the set {1, 2, …, n}, for all n ∈ ℕ. Let us denote the cardinality of a set X by #X. Let A_{n}^{m} denote the set of all m-element antichains in the power set P_{n}, and we let AC_{n}^{m} denote the set of all m-element antichain covers in P_{n}.

The following lemma will be used later in this article. In particular, the lemma allows us to determine T_{n} from D_{0}, …, D_{n} using formula (1).

Lemma 8. Let ℕ_{0} = ℕ ∪ {0} and (a_{n})_{n∈ℕ_{0}}, (b_{n})_{n∈ℕ_{0}} ∈ ℝ^{ℕ_{0}} be sequences such that

b_{n} = ∑_{k=n_{0}}^{n} \binom{n}{k}a_{k}  (7)

for some n_{0} ∈ ℕ_{0} and for all n ≥ n_{0}. Then

a_{n} = ∑_{k=0}^{n−n_{0}} \binom{n}{n − k} · (−1)^{k} · b_{n−k}  (8)

for all natural numbers n ≥ n_{0}.

This lemma follows from the following more general result: let X be a finite set, and let f, g: 2^{X} → ℕ_{0} be two functions such that

∀_{A⊆X}: g(A) = ∑_{B⊆A} f(B).

Then

∀_{A⊆X}f(A) = ∑_{B⊆A}(−1)^{#A−#B}g(B).

We obtain Lemma 8 by putting

f(A) := \begin{cases}0, & if #A < n_{0}; \\ a_{n}, & if #A = n ≥ n_{0}; \end{cases}

g(A) := \begin{cases}0, & if #A < n_{0}; \\ b_{n}, & if #A = n ≥ n_{0}; \end{cases} ,

but we can also prove this lemma by an inductive procedure.

Proof. Equation (8) is satisfied for n = n_{0}, since by (7), b_{n_{0}} = a_{n_{0}}. Assume inductively that equation (8) holds for all natural numbers m such that n_{0} ≤ m ≤ n for some natural number n ≥ n_{0}. It will be shown that (8) is true for n + 1, i.e.,

a_{n+1} = b_{n+1} − ∑_{k=0}^{n−n_{0}} \binom{n + 1}{n − k} · (−1)^{k} · b_{n−k}  (9)

By (7), b_{n+1} = ∑_{k=n_{0}}^{n} \binom{n+1}{k}a_{k} + a_{n+1}, and hence by the induction hypothesis, we get

a_{n+1} = b_{n+1} − ∑_{k=n_{0}}^{n} \binom{n + 1}{k} ∑_{i=0}^{k−n_{0}} \binom{k}{k − i} · (−1)^{i} · b_{k−i}.

Hence after putting s := k − i we obtain

a_{n+1} = b_{n+1} − ∑_{k=n_{0}}^{n} \binom{n + 1}{k} ∑_{s=n_{0}}^{k} \binom{k}{s}(−1)^{k−s}b_{s}.

After changing the order of summation, we have

a_{n+1} = b_{n+1} − ∑_{s=n_{0}}^{n} ∑_{k=s}^{n} \binom{n + 1}{k}\binom{k}{s}(−1)^{k−s}b_{s}.

Thus, after putting t := n − s, we obtain

a_{n+1} = b_{n+1} − ∑_{t=0}^{n−n_{0}} ∑_{k=n−t}^{n} \binom{n + 1}{k}\binom{k}{n − t}(−1)^{k+t−n}b_{n−t}  (10)

We shall show that

∑_{k=n−t}^{n} \binom{n + 1}{k}\binom{k}{n − t}(−1)^{k−n} = \binom{n + 1}{n − t}, for all t ∈ \{0, …, n − n_{0}\}.  (11)

Note that

∑_{k=n−t}^{n} \binom{n + 1}{k}\binom{k}{n − t}(−1)^{k−n}

= ∑_{k=n−t}^{n} \frac{(n + 1)!}{k!(n + 1 − k)!} · \frac{k!}{(n − t)!(k + t − n)!}(−1)^{k−n}

= ∑_{k=n−t}^{n} \frac{(n + 1)!}{(n − t)!(t + 1)!} · \frac{(t + 1)!}{(n + 1 − k)!(k + t − n)!}(−1)^{k−n}

= ∑_{l=0}^{t} \binom{n + 1}{n − t}\binom{t + 1}{l + 1}(−1)^{l} (by setting l := n − k)

= \binom{n + 1}{n − t},

since 0 = (1 − 1)^{t+1} = ∑_{l=0}^{t+1} \binom{t+1}{l}(−1)^{l}. By (10) and (11), we obtain (9). So by induction,

(8) holds for all n ≥ n_{0}.

For small numbers n, formulae (1) and (4), as well as Lemma 8 can be used to compute T_{n}:

Corollary 9. We have

T_{n} = ∑_{k=0}^{n} \binom{n}{n − k}(−1)^{k} ∑_{l=1}^{2^{2^{n−k}}} ∏_{0≤i<j≤2^{n−k}−1} (1 − b_{i}^{l} · b_{j}^{l} · f(i, j)),

where b_{i}^{n} = ⌊n/2^{i}⌋ − 2⌊n/2^{i+1}⌋ for any i, n ≥ 0 and

f(i, n) = \begin{cases}1, & if i = 0; \\ ∏_{m=0}^{log_{2}(i)} (1 − b_{m}^{i} + b_{m}^{i}b_{m}^{n}), & for i ≥ 1. \end{cases}

The following theorem allows computing the number of all m-element antichains and antichain covers in the power set P_{n}. Before formulating this theorem the simple example below is presented. It allows us easier comprehension of the intuition behind Theorem 11.

Example 10. We now demonstrate the method for computing T_{n}^{m}, as well as D_{n}^{m} for m ∈ {2, 3} and for all natural numbers n ≥ 3. Theorem 11 is a generalization of this method for all natural numbers n ≥ 2 and 2 ≤ m ≤ \binom{n}{⌊n/2⌋}.

Firstly, we shall show that for all sets ∅ ≠ A^{1}, A^{2} ⊊ ℤ_{n}^{+} if

#A^{1} ≤ #A^{2},  (12)

then {A^{1}, A^{2}} ∈ A_{n}^{2}, if and only if A^{2} can be decomposed into two subsets A_{1}^{2} and A_{2}^{2} of ℤ_{n}^{+} satisfying the following conditions:

A^{2} = A_{1}^{2} ∪ A_{2}^{2}  (13)
A_{1}^{2} ⊊ A^{1}  (14)
A_{2}^{2} ⊆ ℤ_{n}^{+} \ A^{1}  (15)

Assume that {A^{1}, A^{2}} ∈ A_{n}^{2} and put A_{1}^{2} := A^{2} ∩ A^{1} and A_{2}^{2} := A^{2} ∩ (ℤ_{n}^{+} \ A^{1}). Then (13) and (15) are straightforwardly satisfied. Moreover, A_{1}^{2} ⊆ A^{1}. If A_{1}^{2} were equal to A^{1}, then A^{1} would be included in A^{2} and it would contradict the assumption {A^{1}, A^{2}} ∈ A_{n}^{2}. Thus (14) holds. For the proof of the converse implication assume that A^{1}, A^{2} satisfy conditions (13)–(15). It follows from (14), that there exists x ∈ A^{1} \ A_{1}^{2}. Then by (15), such x ∉ A_{2}^{2} and by (13), x ∉ A^{2}. So A^{1} ⊈ A^{2}. Similarly, A^{2} ⊈ A^{1}, since otherwise by (13) and (15), A_{2}^{2} would have to be equal to ∅, but then A^{2} = A_{1}^{2} and by (14), #A^{2} < #A^{1} — a contradiction to our primary assumption (12).

Analogously, for all sets ∅ ≠ A^{1}, A^{2} ⊊ ℤ_{n}^{+} if (12) is satisfied, then {A^{1}, A^{2}} ∈ AC_{n}^{2} if and only if A^{2} can be decomposed into two subsets A_{1}^{2} and A_{2}^{2} of ℤ_{n}^{+} satisfying conditions (13)–(14). However, instead of condition (15) A_{2}^{2} satisfies the condition:

A_{2}^{2} = ℤ_{n}^{+} \ A^{1}.  (16)

If ∅ ≠ A^{1}, A^{2} ⊊ ℤ_{n}^{+} and A^{1}, A^{2}, A_{1}^{2}, A_{2}^{2} satisfy conditions (12) as well as (13)–(15) and we denote #A^{1} by a^{1}, #A^{2} by a^{2}, and #A_{i}^{2} by a_{i}^{2} for i ∈ {1, 2}, then we obtain the following bounds:

\{ \begin{matrix}1 & ≤ & a^{1} & ≤ & a^{2} & ≤ & n − 1 \\ & & 0 & ≤ & a_{1}^{2} & ≤ & a^{1} − 1 \\ & & 0 & ≤ & a_{2}^{2} & ≤ & n − a^{1} (or a_{2}^{2} = n − a^{1} for AC_{n}^{2}) \end{matrix}  (17)

Then a_{1}^{2} ≥ a^{1} − a_{2}^{2} ≥ a^{1} − (n − a^{1}) = 2a^{1} − n and a_{2}^{2} ≥ a^{1} − a_{1}^{2} ≥ a^{1} − (a^{1} − 1) = 1.

If a^{1} < a^{2} then the number of all families of sets {A^{1}, A^{2}} ∈ A_{n}^{2}, such that A^{1}, A^{2}, A_{1}^{2}, A_{2}^{2} satisfy conditions (13)–(15) as well as a^{1} = #A^{1}, a^{2} = #A^{2}, a_{1}^{2} = #A_{1}^{2}, and a_{2}^{2} = #A_{2}^{2}, equals \binom{n}{a^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n−a^{1}}{a_{2}^{2}}. Otherwise, i.e., if a^{1} = a^{2} then the number of all such families of sets

\{A^{1}, A^{2}\} ∈ A_{n}^{2}, equals \binom{n}{a^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n−a^{1}}{a_{2}^{2}}/2, since \{A^{1}, A^{2}\} = \{A^{2}, A^{1}\}. However, if \{A^{1}, A^{2}\} ∈ AC_{n}^{2}, then a_{2}^{2} = n − a^{1}. Hence we obtain the following formulas:

D_{n}^{2} = ∑_{a^{1}=1}^{n−1} ∑_{a_{1}^{2}=max(0,2a^{1}−n)}^{a^{1}−1} ∑_{a_{2}^{2}=a^{1}−a_{1}^{2}}^{n−a^{1}} \frac{\binom{n}{a^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n−a^{1}}{a_{2}^{2}}}{r(a^{1}, a^{2})}  (18)

T_{n}^{2} = ∑_{a^{1}=1}^{n−1} ∑_{a_{1}^{2}=max(0,2a^{1}−n)}^{a^{1}−1} \frac{\binom{n}{a^{1}}\binom{a^{1}}{a_{1}^{2}}}{r(a^{1}, a^{2})},  (19)

where r(a, b) = \begin{cases}1, & if a < b; \\ 2, & otherwise. \end{cases} Similarly, we shall show that for all sets ∅ ≠ A^{1}, A^{2}, A^{3} ⊊ ℤ_{n}^{+} if

#A^{1} ≤ #A^{2} ≤ #A^{3},  (20)

then {A^{1}, A^{2}, A^{3}} ∈ A_{n}^{3}, if and only if A^{2} can be decomposed into two sets satisfying conditions (13)–(15) and A^{3} can be decomposed into four subsets A_{1}^{3}, A_{2}^{3}, A_{3}^{3}, A_{4}^{3} of ℤ_{n}^{+} satisfying the following conditions:

A^{3} = A_{1}^{3} ∪ A_{2}^{3} ∪ A_{3}^{3} ∪ A_{4}^{3}  (21)
A_{1}^{3} ⊆ A_{1}^{2}  (22)
A_{2}^{3} ⊆ A^{1} \ A_{1}^{2}  (23)
A_{3}^{3} ⊆ A_{2}^{2}  (24)
A_{4}^{3} ⊆ ℤ_{n}^{+} \ A^{1} \ A_{2}^{2}  (25)
A_{1}^{3} ∪ A_{2}^{3} ⊊ A^{1}  (26)
A_{1}^{3} ∪ A_{3}^{3} ⊊ A^{2}  (27)

Assume that {A^{1}, A^{2}, A^{3}} ∈ A_{n}^{3}. Then {A^{1}, A^{2}} ∈ A_{n}^{2}. From the previous reasoning it follows that A^{2} can be decomposed into two sets A_{1}^{2} and A_{2}^{2} satisfying conditions (13)–(15). Put A_{1}^{3} := A^{3} ∩ A_{1}^{2}, A_{2}^{3} := A^{3} ∩ (A^{1} \ A_{1}^{2}), A_{3}^{3} := A^{3} ∩ A_{2}^{2} and A_{4}^{3} := A^{3} ∩ (ℤ_{n}^{+} \ A^{1} \ A_{2}^{2}). Then straightforwardly conditions (22)–(25) are satisfied. Moreover, A_{1}^{3} ∪ A_{2}^{3} = A^{3} ∩ A^{1} and A_{3}^{3} ∪ A_{4}^{3} = A^{3} \ A^{1}. So condition (21) also holds and A_{1}^{3} ∪ A_{2}^{3} ⊆ A^{1}. Suppose that A_{1}^{3} ∪ A_{2}^{3} = A^{1}, then A^{3} ∩ A^{1} = A^{1}. Hence A^{1} ⊆ A^{3} — a contradiction to the assumption {A^{1}, A^{2}, A^{3}} ∈ A_{n}^{3}. Therefore (26) is true. By (13), A_{1}^{3}∪A_{3}^{3} = A^{3}∩A^{2}. Thus If A_{1}^{3}∪A_{3}^{3} = A^{2}, then A^{2} ⊆ A^{3} — a contradiction to the assumption {A^{1}, A^{2}, A^{3}} ∈ A_{n}^{3}. Therefore condition (27) is also satisfied.

Assume that A^{2} can be decomposed into two sets satisfying conditions (13)–(15) and A^{3} can be decomposed into four subsets satisfying conditions (21)–(27). We shall prove that {A^{1}, A^{2}, A^{3}} ∈ A_{n}^{3}. By the previous reasoning {A^{1}, A^{2}} ∈ A_{n}^{2}. By the assumption #A^{1} ≤ #A^{2} ≤ #A^{3} it suffices to show that A^{1} ⊈ A^{3} and A^{2} ⊈ A^{3}. By (15),(21), and (24)–(26), A^{3} ∩ A^{1} = A_{1}^{3} ∪ A_{2}^{3} ≠ A^{1}. So A^{1} ⊈ A^{3}. Similarly, by (13)–(15), (21)–(25), A^{3} ∩ A^{2} = A_{1}^{3} ∪ A_{3}^{3}. Hence by (27), A^{3} ∩ A^{2} ≠ A^{2}. So A^{2} ⊈ A^{3}.

Analogously, for all sets ∅ ≠ A^{1}, A^{2}, A^{3} ⊊ ℤ_{n}^{+} if condition (20) is satisfied, then

{A^{1}, A^{2}, A^{3}} ∈ AC_{n}^{3}

if and only if A^{2} can be decomposed into two sets satisfying conditions (13)–(15) as well as A^{3} can be decomposed into four subsets A_{1}^{3}, A_{2}^{3}, A_{3}^{3}, A_{4}^{3} of ℤ_{n}^{+} satisfying conditions (21)–(27). However, instead of condition (25) A_{4}^{3} satisfies the condition:

A_{4}^{3} = ℤ_{n}^{+} \ A^{1} \ A_{2}^{2}.  (28)

If A^{1}, A^{2}, A^{3}, A_{1}^{2}, A_{2}^{2}, A_{1}^{3}, A_{2}^{3}, A_{3}^{3}, A_{4}^{3} satisfy conditions (20), (13)–(15) and (21)–(27), we adopt the notation from the previous paragraph and we denote #A_{i}^{3} by a_{i}^{3} for i ∈ {1, 2, 3, 4}, then we obtain the following bounds for a^{3} and a_{i}^{3}:

\{ \begin{matrix}0 & ≤ & a_{1}^{3} & ≤ & a_{1}^{2} \\ 0 & ≤ & a_{2}^{3} & ≤ & a^{1} − a_{1}^{2} \\ 0 & ≤ & a_{3}^{3} & ≤ & a_{2}^{2} \\ 0 & ≤ & a_{4}^{3} & ≤ & n − a^{1} − a_{2}^{2} (or a_{4}^{3} = n − a^{1} − a_{2}^{2} for AC_{n}^{3}) \\ & & a_{1}^{3} + a_{2}^{3} & ≤ & a^{1} − 1 \\ & & a_{1}^{3} + a_{3}^{3} & ≤ & a^{2} − 1 \\ a^{2} & ≤ & a^{3} & ≤ & n − 1 \end{matrix}  (29)

If a^{1} < a^{2} < a^{3} then the number of all families of sets {A^{1}, A^{2}, A^{3}} ∈ A_{n}^{3}, such that A^{1}, A^{2}, A^{3}, A_{1}^{2}, A_{2}^{2}, A_{1}^{3}, A_{2}^{3}, A_{3}^{3}, A_{4}^{3} satisfy conditions (13)–(15) and (21)–(27), as well as a^{1} = #A^{1}, a^{2} = #A^{2}, a_{1}^{2} = #A_{1}^{2}, a_{2}^{2} = #A_{2}^{2}, a_{i}^{3} = #A_{i}^{3} for i ∈ {1, 2, 3, 4}, equals

\binom{n}{a^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n − a^{1}}{a_{2}^{2}}\binom{a_{1}^{2}}{a_{1}^{3}}\binom{a^{1} − a_{1}^{2}}{a_{2}^{3}}\binom{a_{2}^{2}}{a_{3}^{3}}\binom{n − a^{1} − a_{2}^{2}}{a_{4}^{3}}.

If a^{1} < a^{2} = a^{3} or a^{1} = a^{2} < a^{3} then the number of all such families of sets {A^{1}, A^{2}, A^{3}} ∈ A_{n}^{3}, equals

\binom{n}{a^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n − a^{1}}{a_{2}^{2}}\binom{a_{1}^{2}}{a_{1}^{3}}\binom{a^{1} − a_{1}^{2}}{a_{2}^{3}}\binom{a_{2}^{2}}{a_{3}^{3}}\binom{n − a^{1} − a_{2}^{2}}{a_{4}^{3}}/2.

If a^{1} = a^{2} = a^{3} then the number of all such families of sets {A^{1}, A^{2}, A^{3}} ∈ A_{n}^{3}, equals

\binom{n}{a^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n − a^{1}}{a_{2}^{2}}\binom{a_{1}^{2}}{a_{1}^{3}}\binom{a^{1} − a_{1}^{2}}{a_{2}^{3}}\binom{a_{2}^{2}}{a_{3}^{3}}\binom{n − a^{1} − a_{2}^{2}}{a_{4}^{3}}/3!.

However, if {A^{1}, A^{2}, A^{3}} ∈ AC_{n}^{3}, then a_{4}^{3} = n − a^{1} − a_{2}^{2}. Hence we obtain the following formulae:

D_{n}^{3} = ∑_{a^{1}=1}^{n−1} ∑_{a_{1}^{2}=max(0,2a^{1}−n)}^{a^{1}−1} ∑_{a_{2}^{2}=a^{1}−a_{1}^{2}}^{n−a^{1}} ∑_{(a_{1}^{3},a_{2}^{3},a_{3}^{3},a_{4}^{3}) satisfying conditions (29)}

\frac{\binom{n}{a^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n−a^{1}}{a_{2}^{2}}\binom{a_{1}^{2}}{a_{1}^{3}}\binom{a^{1}−a_{1}^{2}}{a_{2}^{3}}\binom{a_{2}^{2}}{a_{3}^{3}}\binom{n−a^{1}−a_{2}^{2}}{a_{4}^{3}}}{r(a^{1}, a^{2}, a^{3})}  (30)

T_{n}^{3} = ∑_{a^{1}=1}^{n−1} ∑_{a_{1}^{2}=max(0,2a^{1}−n)}^{a^{1}−1} ∑_{(a_{1}^{3},a_{2}^{3},a_{3}^{3},a_{4}^{3}) satisfying conditions (29)}

\frac{\binom{n}{a^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n−a^{1}}{a_{2}^{2}}\binom{a_{1}^{2}}{a_{1}^{3}}\binom{a^{1}−a_{1}^{2}}{a_{2}^{3}}\binom{a_{2}^{2}}{a_{3}^{3}}}{r(a^{1}, a^{2}, a^{3})},  (31)

where r(a, b, c) = \begin{cases}1, & if a < b < c; \\ 2, & if a < b = c or a = b < c; \\ 3!, & if a = b = c. \end{cases}.

Theorem 11. Let

I_{i}^{m} := ⋃_{k=0}^{2^{i−1}−1} [2k · 2^{m−1−i} + 1; (2k + 1) · 2^{m−1−i}] ∩ ℕ  (32)

for m ≥ 2 and i ∈ ℤ_{m−1}^{+}. For a natural number n and sequence of sequences of natural numbers (\underline{a}^{1}, \underline{a}^{2}, …) such that \underline{a}^{m} = (a_{1}^{m}, …, a_{2^{m−1}}^{m}) ∈ ℕ_{0}^{2^{m−1}} for m ∈ ℕ define:

a^{m} = ∑_{k=1}^{2^{m−1}} a_{k}^{m}  (33)
b_{1}^{1} := n  (34)
b_{k}^{m} := \begin{cases}a_{(k+1)/2}^{m−1}, & if 2 ∤ k \\ b_{k/2}^{m−1} − a_{k/2}^{m−1}, & if 2 | k \end{cases} , for m ≥ 2 and k ∈ ℤ_{2^{m−1}}^{+}  (35)
S_{m}^{n}(\underline{a}^{1}, …, \underline{a}^{m−1}) := \{ \begin{matrix}\underline{a}^{m} ∈ ℕ_{0}^{2^{m−1}} : 0 ≤ a_{k}^{m} ≤ b_{k}^{m}, & for k ∈ ℤ_{2^{m−1}}^{+}& \\ a^{m−1} ≤ a^{m} ≤ n − 1 & & \\ ∑_{k∈I_{i}^{m}} a_{k}^{m} ≤ a^{i} − 1, & for i ∈ ℤ_{m−1}^{+} \end{matrix} \} ,  (36)
for m ≥ 2
\overline{S_{m}^{n}}(\underline{a}^{1}, …, \underline{a}^{m−1}) := \{\underline{a}^{m} ∈ S_{m}^{n}(\underline{a}^{1}, …, \underline{a}^{m−1}): a_{2^{m−1}}^{m} = b_{2^{m−1}}^{m}\} , for m ≥ 2 (37)

For a non-decreasing sequence of natural numbers (a_{1}, …, a_{m}), natural numbers m_{1}, …, m_{k}, and M_{1}, …, M_{k} such that:

1. m_{1} + m_{2} + ⋯ + m_{k} = m

2. M_{1} = 0

3. M_{i} := m_{1} + ⋯ + m_{i−1} for 2 ≤ i ≤ k

4. ∀_{i∈ℤ_{k}^{+}}∀_{j∈ℤ_{m_{i}}^{+}}a_{M_{i}+j} = a_{M_{i}+1}

5. ∀_{i∈{2,...,k}}a_{M_{i}} < a_{M_{i}+1}. define function

r(a_{1}, …, a_{m}) := ∏_{i=1}^{k} m_{i}!.  (38)

With the above notation, for all natural numbers m, n ≥ 2 if m ≤ \binom{n}{⌊n/2⌋} then:

D_{n}^{m} = ∑_{a^{1}=1}^{n−1} ∑_{\underline{a}^{2}∈S_{2}^{n}(a^{1})} … ∑_{\underline{a}^{m−1}∈S_{m−1}^{n}(\underline{c}^{m−2})} ∑_{\underline{a}^{m}∈S_{m}^{n}(\underline{c}^{m−1})} ∏_{i=1}^{m} ∏_{j=1}^{2^{i−1}} \frac{\binom{b_{j}^{i}}{a_{j}^{i}}}{r(a^{1}, …, a^{m})}  (39)
T_{n}^{m} = ∑_{a^{1}=1}^{n−1} ∑_{\underline{a}^{2}∈S_{2}^{n}(a^{1})} … ∑_{\underline{a}^{m−1}∈S_{m−1}^{n}(\underline{c}^{m−2})} ∑_{\underline{a}^{m}∈\overline{S_{m}^{n}}(\underline{c}^{m−1})} ∏_{i=1}^{m} ∏_{j=1}^{2^{i−1}} \frac{\binom{b_{j}^{i}}{a_{j}^{i}}}{r(a^{1}, …, a^{m})}  (40)

where \underline{c}^{k} = (\underline{a}^{1}, \underline{a}^{2}, …, \underline{a}^{k}).

Remark 12. The set I_{i}^{m} defined in (32) for m ≥ 2 and i ∈ ℤ_{m−1}^{+} is intuitively the set of indices of sets belonging to the partition {A_{1}^{m}, …, A_{2^{m−1}}^{m}} of set A^{m}, which are included in A^{i}. Properties of these partitions are described by (13)–(15) and (21)–(27) in Example 10 for A^{2} and A^{3}, respectively, as well as in Lemma 17 occurring later in this article. So the condition ∑_{k∈I_{i}^{m}} a_{k}^{m} ≤ a^{i} − 1 from (36) can be translated in the context of these partitions as ⋃_{k∈I_{i}^{m}} A_{k}^{m} ⊊ A^{i} and it prevents A^{i} ⊆ A^{m} for all i ∈ ℤ_{m−1}^{+}. Thus this condition guarantees that sets A^{1}, …, A^{m}, consisting of these partitions form an antichain.

The following proposition gives an explicit formula for expressions defined recursively by (34) and (35).

Proposition 13. Let m, n ∈ ℕ, a_{1}^{0} := n and b_{k}^{m} be defined by (34) and (35). Then

b_{k}^{m} = a_{(r+1)/2}^{m−l−1} − ∑_{i=1}^{l} a_{2^{l−i}r}^{m−i}.  (41)

for all r ∈ ℕ and l ∈ ℤ_{m} such that 2 ∤ r, k = 2^{l} · r, and k ≤ 2^{m−1}.

Proof. The proof is by induction on m. For the base step of the induction, assume that m = 1. Then k = 1 = 2^{0} and by (34), b_{1}^{1} = n = a_{1}^{0} = a_{(r+1)/2}^{m−l−1} for l = 0 and r = 1.

Assume that (41) holds for some m ∈ ℕ. We shall show that (41) holds for m + 1. We shall consider two cases. Firstly, let us assume that 2 ∤ k. Then by (35), b_{k}^{m+1} = a_{(k+1)/2}^{m} = a_{(r+1)/2}^{m+1−l−1} for l = 0 and r = k. Therefore in this case (41) is true.

Assume that k = 2^{l} · r, where 0 < l ≤ m and 2 ∤ r. Then by (35),

b_{k}^{m+1} = b_{2^{l−1}·r}^{m} − a_{2^{l−1}·r}^{m}.  (42)

By the induction hypothesis,

b_{2^{l−1}·r}^{m} = a_{(r+1)/2}^{m−(l−1)−1} − ∑_{i=1}^{l−1} a_{2^{l−1−i}r}^{m−i}.  (43)

Therefore by (42) and (43),

b_{k}^{m+1} = a_{(r+1)/2}^{m−(l−1)−1} − ∑_{i=1}^{l−1} a_{2^{l−1−i}r}^{m−i} − a_{2^{l−1}·r}^{m}

= a_{(r+1)/2}^{m+1−l−1} − ∑_{i=1}^{l} a_{2^{l−i}r}^{m+1−i}.

So (41) holds for m + 1, and by an inductive procedure, (41) is true for all m ∈ ℕ.

Proof of Theorem 11. Lemma 14. Let I_{i}^{m} be defined by (32). Then

⋃_{i∈ℤ_{m−1}^{+}} I_{i}^{m} = ℤ_{2^{m−1}}^{+} \ {2^{m−1}}  (44)

for all natural numbers m ≥ 2. Proof. Fix any natural number m ≥ 2 and x ∈ ℤ_{2^{m−1}}^{+} \ {2^{m−1}}. Let

i := m − 1 − ⌊log_{2}(2^{m−1} − x)⌋  (45)

and k := 2^{i−1} − 1. Note that i ∈ ℤ_{m−1}^{+}. We shall show that

k · 2^{m−i} < x ≤ k · 2^{m−i} + 2^{m−i−1} :

Note that

k · 2^{m−i} = 2^{m−1} − 2 · 2^{⌊log_{2}(2^{m−1}−x)⌋},  (46)

and

2^{m−1} − 2 · 2^{⌊log_{2}(2^{m−1}−x)⌋} < 2^{m−1} − 2 · 2^{log_{2}(2^{m−1}−x)−1} = x  (47)
2^{m−1} − 2 · 2^{⌊log_{2}(2^{m−1}−x)⌋} ≥ 2^{m−1} − 2 · 2^{log_{2}(2^{m−1}−x)} = 2x − 2^{m−1}  (48)

Thus by (46) and (47) we have k · 2^{m−i} < x and

x ≤ 2^{m−1} − 2^{⌊log_{2}(2^{m−1}−x)⌋}, by (48)
= k · 2^{m−i} + 2^{⌊log_{2}(2^{m−1}−x)⌋}, by (46)
= k · 2^{m−i} + 2^{m−i−1}, by (45)

Therefore x ∈ I_{i}^{m}.

Let m, n ≥ 2 be natural numbers and

𝔄_{m}^{n} := { {(A^{1}, A^{2}, …, A^{m}) , {(A_{1}^{k}, …, A_{2^{k−1}}^{k}, B_{1}^{k}, …, B_{2^{k−1}}^{k}) : k ∈ ℤ_{m}^{+}}} :  (49)

∀_{k∈ℤ_{m}^{+}} (∅ ≠ A^{k} ⊊ ℤ_{n}^{+} ∧ #A^{k−1} ≤ #A^{k} ∧ ∀_{i∈ℤ_{2^{k−1}}^{+}} : (A_{i}^{k} ⊆ B_{i}^{k} ⊆ ℤ_{n}^{+})) },

where A^{0} := ∅.

Lemma 15. Let m, n ≥ 2 be natural numbers and A ∈ 𝔄_{m}^{n}. If A satisfies condition

B_{i}^{k} = \begin{cases}A_{(i+1)/2}^{k−1}, & if 2 ∤ i; \\ B_{i/2}^{k−1} \ A_{i/2}^{k−1}, & otherwise; \end{cases}  (50)

for all k ∈ {2, …, m} and i ∈ ℤ_{2^{k−1}}^{+}, where B_{1}^{1} = ℤ_{n}^{+} and A_{1}^{1} = A^{1}. Then for all k ∈ {2, …, m}:

⋃_{i∈ℤ_{2^{k−1}}^{+}} B_{i}^{k} = ℤ_{n}^{+}  (51)

B_{i}^{k} ∩ B_{j}^{k} = ∅, for all distinct i, j ∈ ℤ_{2^{k−1}}^{+}  (52)

Proof. The proof is by induction on k. For k = 2 by (50), B_{1}^{2} = A_{1}^{1} = A^{1} and B_{2}^{2} = B_{1}^{1}\A_{1}^{1} = ℤ_{n}^{+} \ A^{1}. Thus (51) and (52) hold.

Assume that (51) and (52) are satisfied for some natural number 2 ≤ k < m. We shall show that (51) holds for k + 1: By (50) and the induction hypothesis we have

⋃_{i∈ℤ_{2^{k}}^{+}} B_{i}^{k+1} = ⋃_{i∈ℤ_{2^{k−1}}^{+}} (B_{2i−1}^{k+1} ∪ B_{2i}^{k+1})

= ⋃_{i∈ℤ_{2^{k−1}}^{+}} (A_{i}^{k} ∪ (B_{i}^{k} \ A_{i}^{k})) = ⋃_{i∈ℤ_{2^{k−1}}^{+}} B_{i}^{k} = ℤ_{n}^{+}.

We shall show that (52) holds for k + 1: Assume that i, j ∈ ℤ_{2^{k}}^{+} and i ≠ j.

1. If 2 ∤ i and 2 ∤ j then by (50) and finally by the induction hypothesis,

B_{i}^{k+1} ∩ B_{j}^{k+1} = A_{(i+1)/2}^{k} ∩ A_{(j+1)/2}^{k} ⊆ B_{(i+1)/2}^{k} ∩ B_{(j+1)/2}^{k} = ∅.

2. If 2 ∤ i and 2 | j then

• if (i + 1)/2 = j/2 then by (50), we have

B_{i}^{k+1} ∩ B_{j}^{k+1} = A_{j/2}^{k} ∩ (B_{j/2}^{k} \ A_{j/2}^{k}) = ∅;

• if (i + 1)/2 ≠ j/2, then by (50) and the induction hypothesis we have

B_{i}^{k+1} ∩ B_{j}^{k+1} = A_{(i+1)/2}^{k} ∩ (B_{j/2}^{k} \ A_{j/2}^{k}) ⊆ B_{(i+1)/2}^{k} ∩ B_{j/2}^{k} = ∅.

3. If 2 | i and 2 | j then by (50) and the induction hypothesis we have

B_{i}^{k+1} ∩ B_{j}^{k+1} = (B_{i/2}^{k} \ A_{i/2}^{k}) ∩ (B_{j/2}^{k} \ A_{j/2}^{k}) ⊆ B_{i/2}^{k} ∩ B_{j/2}^{k} = ∅.

Lemma 16. Let m, n ≥ 2 be natural numbers and A ∈ 𝔄_{m}^{n}. If A satisfies condition (50) and the following condition:

A^{k} = ⋃_{i=1}^{2^{k−1}} A_{i}^{k}  (53)

for all k ∈ {2, …, m}. Then

⋃_{i∈I_{j}^{k}} B_{i}^{k} = A^{j}, for all j ∈ ℤ_{k−1}^{+}  (54)

B_{2^{k−1}}^{k} = ℤ_{n}^{+} \ ⋃_{i=1}^{k−1} A^{i}  (55)

for all natural numbers 2 ≤ k ≤ m.

Proof. The proof of (54) is by induction on k. For k = 2, by (32), I_{1}^{2} = {1}. Hence ⋃_{i∈I_{1}^{2}} B_{i}^{2} = B_{1}^{2} = A^{1}. Therefore (54) holds.

Assume that(54) is satisfied for some natural number k such that 2 ≤ k < m. Firstly we shall prove that ⋃_{i∈I_{k}^{k+1}} B_{i}^{k+1} = A^{k}: By (32), I_{k}^{k+1} = {2i + 1: i ∈ ℤ_{2^{k−1}}}. Thus, by (50) and (53),

⋃_{i∈I_{k}^{k+1}} B_{i}^{k+1} = ⋃_{i∈ℤ_{2^{k−1}}} B_{2i+1}^{k+1} = ⋃_{i∈ℤ_{2^{k−1}}^{+}} A_{i}^{k} = A^{k}

Fix any j ∈ {1, …, k − 1}. Then by (32), I_{j}^{k+1} is a union of 2^{j−1} 2^{k−j}-element sets, furthermore {(i + 1)/2: i ∈ I_{j}^{k+1} & 2 ∤ i} = I_{j}^{k}. Therefore by (50) and the induction hypothesis,

⋃_{i∈I_{j}^{k+1}} B_{i}^{k+1} = ⋃_{{i∈I{k+1 \atop j} \atop 2∤i}} (B_{i}^{k+1} ∪ B_{i+1}^{k+1})

= ⋃_{{i∈I{k+1 \atop j} \atop 2∤i}} (A_{(i+1)/2}^{k} ∪ (B_{(i+1)/2}^{k} \ A_{(i+1)/2}^{k})) = ⋃_{i∈I_{j}^{k}} B_{i}^{k} = A^{j}.

To prove (55), firstly we utilize (51) and (52) from Lemma 15, from which it follows that

B_{2^{k−1}}^{k} = ℤ_{n}^{+} \ ⋃_{i=1}^{2^{k−1}−1} B_{i}^{k}.

By (44) from Lemma 14, and next by (54) from Lemma 16 we have

B_{2^{k−1}}^{k} = ℤ_{n}^{+} \ ⋃ ; i∈⋃_{j∈ℤ{+ \atop k−1}} I_{j}^{k} B_{i}^{k}

= ℤ_{n}^{+} \ ⋃_{j∈ℤ_{k−1}^{+}} ⋃_{i∈I_{j}^{k}} B_{i}^{k}

= ℤ_{n}^{+} \ ⋃_{j∈ℤ_{k−1}^{+}} A^{j}

Lemma 17. Let m, n ≥ 2 be natural numbers, m ≤ \binom{n}{⌊n/2⌋}, A^{k} ⊆ ℤ_{n}^{+} for all k ∈ ℤ_{m}^{+}, and 1 ≤ #A^{1} ≤ … ≤ #A^{m} ≤ n − 1, then

1. A = {A^{1}, …, A^{m}} ∈ A_{n}^{m} if and only if for each k ∈ {2, …, m} there exist sets A_{1}^{k}, …, A_{2^{k−1}}^{k} and B_{1}^{k}, …, B_{2^{k−1}}^{k} such that conditions (50), (53), and

A_{i}^{k} ⊆ B_{i}^{k}, for all i ∈ ℤ_{2^{k−1}}^{+}  (56)
⋃_{i∈I_{j}^{k}} A_{i}^{k} ⊊ A^{j}, for all j ∈ ℤ_{k−1}^{+}  (57)

are satisfied for all k ∈ {2, …, m}.

2. A = {A^{1}, …, A^{m}} ∈ AC_{n}^{m} if and only if for each k ∈ {2, …, m} there exist sets A_{1}^{k}, …, A_{2^{k−1}}^{k} and B_{1}^{k}, …, B_{2^{k−1}}^{k} such that conditions (50), (53), (56), (57) are satisfied for all k ∈ {2, …, m} and A_{2^{m−1}}^{m} = B_{2^{m−1}}^{m}.

Proof. The proof is by induction on m. Firstly we shall prove this fact for m = 2. Assume that {A^{1}, A^{2}} ∈ A_{n}^{2}. Define A_{1}^{1} := A^{1}, B_{1}^{1} := ℤ_{n}^{+}, B_{1}^{2} := A^{1}, B_{2}^{2} := ℤ_{n}^{+} \ A^{1}, A_{1}^{2} := A^{1} ∩ A^{2}, and A_{2}^{2} := A^{2} \ A^{1}. Then conditions (50), (53), and (56) are straightforwardly satisfied. Moreover I_{1}^{2} = {1}. Hence ⋃_{i∈I_{1}^{2}} A_{i}^{2} = A_{1}^{2} ⊊ A^{1}, since A^{1} ⊈ A^{2}. Thus condition (57) is also true. If additionally {A^{1}, A^{2}} ∈ AC_{n}^{2}, then ℤ_{n}^{+} \ A^{1} ⊆ A^{2}. Hence A_{2}^{2} = B_{2}^{2}.

Now assume that conditions (50), (53), (56), (57) are satisfied. It follows from (57) that A_{1}^{2} ⊊ A^{1}, and by (56) and (50), A_{2}^{2} ⊆ ℤ_{n}^{+} \ A^{1}. Therefore by (53), A^{1} ⊈ A^{2}. Moreover, #A^{1} ≤ #A^{2}. Hence A^{2} ⊈ A^{1}, since otherwise A^{2} = A^{1} which contradicts A^{1} ⊈ A^{2}. So {A^{1}, A^{2}} ∈ A_{n}^{2}. If A_{2}^{2} = B_{2}^{2}, then by (53) and (50), A^{1} ∪ A^{2} = A^{1} ∪ A_{2}^{2} = A^{1} ∪ B_{2}^{2} = ℤ_{n}^{+}. Thus {A^{1}, A^{2}} ∈ AC_{n}^{2} and Lemma 17 is true for m = 2.

Assume that Lemma 17 is true for some natural number m such that 2 ≤ m < \binom{n}{⌊n/2⌋}. We shall show that it holds for m + 1. Assume {A^{1}, …, A^{m+1}} ∈ A_{n}^{m+1}. Then {A^{1}, …, A^{m}} ∈ A_{n}^{m} and by the induction hypothesis, for each k ∈ {2, …, m} there exist sets A_{1}^{k}, …, A_{2^{k−1}}^{k} and B_{1}^{k}, …, B_{2^{k−1}}^{k} such that conditions (50), (53), (56), (57) are satisfied for all k ∈ {2 …, m}.

Let A_{i}^{m+1} := A^{m+1}∩B_{i}^{m+1}, where B_{i}^{m+1} defined by (50) exist by the induction hypothesis, for all i ∈ ℤ_{2^{m}}^{+}. Then conditions (50) and (56) are also straightforwardly satisfied for k = m + 1. By (51) from Lemma 15,

⋃_{i=1}^{2^{m}} A_{i}^{m+1} = A^{m+1} ∩ ⋃_{i=1}^{2^{m}} B_{i}^{m+1} = A^{m+1};

thus (53) is also satisfied for m+1. Therefore by (54) from Lemma 16, we have ⋃_{i∈I_{j}^{m+1}} B_{i}^{m+1} = A^{j} for all j ∈ ℤ_{m}^{+}. So

⋃_{i∈I_{j}^{m+1}} A_{i}^{m+1} = A^{m+1} ∩ ⋃_{i∈I_{j}^{m+1}} B_{i}^{m+1} = A^{m+1} ∩ A^{j} ⊊ A^{j},

since otherwise A^{j} ⊆ A^{m+1} which would contradict with assumption {A^{1}, …, A^{m+1}} ∈ A_{n}^{m+1}. It follows from the above reasoning that (57) is satisfied for all k ∈ {2, …, m + 1}.

Assume now that {A^{1}, …, A^{m+1}} ∈ AC_{n}^{m+1}. Then by the previous part of the proof, conditions (50), (53), (56), (57) are satisfied for all k ∈ {2, …, m + 1}. We shall prove that A_{2^{m}}^{m+1} = B_{2^{m}}^{m+1}. By (56), A_{2^{m}}^{m+1} ⊆ B_{2^{m}}^{m+1}. Suppose that A_{2^{m}}^{m+1} ⊊ B_{2^{m}}^{m+1}. Then by (55), A_{2^{m}}^{m+1} ⊊ ℤ_{n}^{+} \ ⋃_{i=1}^{m} A^{i}, and hence

A_{2^{m}}^{m+1} ∪ ⋃_{i=1}^{m} A^{i} ⊊ ℤ_{n}^{+}.  (58)

On the other hand, by (57), ⋃_{j∈ℤ_{m}^{+}} ⋃_{i∈I_{j}^{m+1}} A_{i}^{m+1} ⊆ ⋃_{j∈ℤ_{m}^{+}} A^{j}. So by Lemma 14 and (53), A^{m+1} \ A_{2^{m}}^{m+1} ⊆ ⋃_{j∈ℤ_{m}^{+}} A^{j}. Therefore

⋃_{j∈ℤ_{m+1}^{+}} A^{j} = ⋃_{j∈ℤ_{m}^{+}} A^{j} ∪ A_{2^{m}}^{m+1}.  (59)

We see that (58) and (59) contradict assumption {A^{1}, …, A^{m+1}} ∈ AC_{n}^{m+1}.

Now assume that conditions (50), (53), (56), (57) are satisfied for all k ∈ {2, …, m + 1}. We shall show that {A^{1}, …, A^{m+1}} ∈ A_{n}^{m+1}. By assumption #A^{i} ≤ #A^{i+1} for all i ∈ ℤ_{m}^{+} and the induction hypothesis, it suffices to prove that A^{j} ⊈ A^{m+1} for all j ∈ ℤ_{m}^{+}. Fix any j ∈ ℤ_{m}^{+}. Then: by (54), A^{m+1} ∩ A^{j} = A^{m+1} ∩ ⋃_{i∈I_{j}^{m+1}} B_{i}^{m+1}; by (53), A^{m+1} ∩ ⋃_{i∈I_{j}^{m+1}} B_{i}^{m+1} = ⋃_{i∈ℤ_{2^{m}}^{+}} A_{i}^{m+1} ∩ ⋃_{i∈I_{j}^{m+1}} B_{i}^{m+1}; by Lemma 14, (51), (52), and (56), ⋃_{i∈ℤ_{2^{m}}^{+}} A_{i}^{m+1} ∩ ⋃_{i∈I_{j}^{m+1}} B_{i}^{m+1} = ⋃_{i∈I_{j}^{m+1}} A_{i}^{m+1}; hence by (57), A^{m+1} ∩ A^{j} ⊊ A^{j}. Therefore A^{j} ⊈ A^{m+1}.

If additionally A_{2^{m}}^{m+1} = B_{2^{m}}^{m+1}, then by (55), we have A_{2^{m}}^{m+1} ∪ ⋃_{i∈ℤ_{m}^{+}} A^{i} = ℤ_{n}^{+}. So by (53), ⋃_{i∈ℤ_{m+1}^{+}} A^{i} = ℤ_{n}^{+}. Thus {A^{1}, …, A^{m+1}} ∈ AC_{n}^{m+1}.

Using Lemma 17 we can determine the number of all antichains as well as the number of all antichain covers of an n-element set X which consist of m subsets of X. Let

ℭ_{m}^{n} := {(A^{1}, …, A^{m}): ∃_{A∈𝔄_{m}^{n}}: (A^{1}, …, A^{m}) ∈ A & A satisfies conditions (50), (53), (57)}

and

𝔇_{m}^{n} := {(A^{1}, …, A^{m}) ∈ ℭ_{m}^{n}: A_{2^{m−1}}^{m} = B_{2^{m−1}}^{m}}

By Lemma 17, if #A^{1} ≤ … ≤ #A^{m}, then {A^{1}, …, A^{m}} ∈ A_{n}^{m} iff (A^{1}, …, A^{m}) ∈ ℭ_{m}^{n} and {A^{1}, …, A^{m}} ∈ AC_{n}^{m} iff (A^{1}, …, A^{m}) ∈ 𝔇_{m}^{n}.

If (A^{1}, …, A^{m}) ∈ ℭ_{m}^{n}, then A^{1} can be chosen in \binom{b_{1}^{1}}{a^{1}} ways, where b_{1}^{1} = n, a^{1} = #A^{1}, and a^{1} can differ from 1 to n − 1. Generally, it follows from Lemma 17, that for fixed sets A^{1}, …, A^{k} of cardinality a^{1}, …, a^{k}, respectively, set A_{i}^{k+1} can be chosen in \binom{b_{i}^{k+1}}{a_{i}^{k+1}} ways, for

all i ∈ ℤ_{2^{k}}^{+}, where b_{i}^{k+1} are defined by (35), (a_{1}^{k+1}, …, a_{2^{k}}^{k+1}) ∈ S_{m}^{n} (\underline{a}^{1}, …, \underline{a}^{k}), and S_{m}^{n} is defined by (36). Moreover if (A^{1}, …, A^{m}) ∈ 𝔇_{m}^{n}, then by Lemma 17, A_{2^{m−1}}^{m} = B_{2^{m−1}}^{m}. So it can be chosen in one way. Furthermore, note that for any set {A^{1}, …, A^{m}} ∈ A_{n}^{m} if a_{i} = #A^{i} for all i ∈ ℤ_{m}^{+} and

\underbrace{a_{1} = ⋯ = a_{m_{1}}}_{m_{1}} < \underbrace{a_{m_{1}+1} = ⋯ = a_{m_{1}+m_{2}}}_{m_{2}} < ⋯ < \underbrace{a_{M_{k}+1} = ⋯ = a_{M_{k}+m_{k}}}_{m_{k}}

where M_{i} := m_{1} + ⋯ + m_{i−1} for all 1 < i ≤ k, then the number of all (B^{1}, …, B^{m}) ∈ ℭ_{m}^{n} such that {B^{1}, …, B^{m}} = {A^{1}, …, A^{m}} is equal to ∏_{i=1}^{k} m_{i}!. Therefore (39) and (40) are true.

3 Covers of labeled sets with antichains consisting of equinumerous sets

Let X be an n-element set and numbers k, m ∈ ℕ be such that \frac{n}{k} ≤ m ≤ \binom{n}{k}. We let AC^{m,k}(X) denote the set of all m-antichain covers {A_{1}, …, A_{m}} in the power set P(X) such that #A_{i} = k for all i ∈ ℤ_{m}^{+}. If X = ℤ_{n}^{+}, then AC^{m,k}(X) is denoted by AC_{n}^{m,k} and T_{n}^{m,k} = #AC_{n}^{m,k}.

Note that the assumption \frac{n}{k} ≤ m ≤ \binom{n}{k} is a necessary condition for the correctness of this notion, since for any n-element set X and {A_{1}, …, A_{m}} ∈ AC^{m,k}(X):

n = #X = # (⋃_{i=1}^{m} A_{i}) ≤ ∑_{i=1}^{m} #A_{i} = m · k

and A_{1}, …, A_{m} are distinct k-element subsets of X whose total number equals \binom{n}{k}.

Lemma 18. Let X be an n-element set, m, k ∈ ℕ be such that m ≤ \binom{n}{k},

C_{k}^{m}(X) := {{A_{1}, …, A_{m}}: A_{i} ⊆ X and #A_{i} = k for all i ∈ {1, …, m}},

n_{0} := min \{n′ ∈ ℕ: \binom{n′}{k} ≥ m\}. Then:

C_{k}^{m}(X) = ⋃_{Y ⊆X: n_{0}≤#Y ≤min(n,m·k)} AC^{m,k}(Y)  (60)

#C_{k}^{m}(X) = \binom{\binom{n}{k}}{m}  (61)

∑_{l=n_{0}}^{min(n,m·k)} \binom{n}{l} · T_{l}^{m,k} = \binom{\binom{n}{k}}{m}.  (62)

Proof.

1. Fix any {A_{1}, …, A_{m}} ∈ C_{k}^{m}(X). Let Y := ⋃_{i=1}^{m} A_{i}. Then {A_{1}, …, A_{m}} ∈ AC^{m,k}(Y), Y ⊆ X; moreover, we have, n′ := #Y ≤ min(n, m · k) and \binom{n′}{k} ≥ m. Thus n′ ≥ n_{0}. The converse inclusion is obvious.

2. The number of all k-element subsets of an n-element set equals \binom{n}{k}. Thus #C_{k}^{m}(X) as the number of all m-element subsets of the family of all k-element subsets of an n-element set equals \binom{\binom{n}{k}}{m}.

3. It follows straightforwardly from (60) and (61), since

#AC^{m,k}(Y) = #AC^{m,k}(Y′) = T_{l}^{m,k}

for all Y, Y′ ⊆ X such that n_{0} ≤ l := #Y = #Y′ ≤ min(n, m · k) and the number of all l-element subsets of X equals \binom{n}{l}.

Theorem 19. Assume that m, k ∈ ℕ and n_{0} := min \{n′ ∈ ℕ: \binom{n′}{k} ≥ m\}. Then

T_{n}^{m,k} = ∑_{t=0}^{n−n_{0}} \binom{n}{n − t} · \binom{\binom{n−t}{k}}{m} · (−1)^{t}  (63)

for all n ∈ {n_{0}, …, m · k}

Proof. Fix m, k ∈ ℕ and put n_{0} := min \{n′ ∈ ℕ: \binom{n′}{k} ≥ m\}. Let a_{n} := T_{n}^{m,k} and b_{n} := \binom{\binom{n}{k}}{m}.

Then by (62) from Lemma 18, b_{n} := ∑_{k=n_{0}}^{n} \binom{n}{k}a_{k}. Thus assumptions of Lemma 8 are satisfied. Therefore by the same lemma, (63) holds.

4 Numerical results

Example 20. Let us return to Example 10 and compute D_{n}^{m} for all n ≥ 3 and m ∈ {2, 3} using Theorem 11 and Proposition 13. By formulas (39) and (40),

D_{n}^{2} = ∑_{a^{1}=1}^{n−1} ∑_{\underline{a}^{2}∈S_{2}^{n}(a^{1})} \frac{\binom{b_{1}^{1}}{a_{1}^{1}}\binom{b_{1}^{2}}{a_{1}^{2}}\binom{b_{2}^{2}}{a_{2}^{2}}}{r(a^{1}, a^{2})}

T_{n}^{2} = ∑_{a^{1}=1}^{n−1} ∑_{\underline{a}^{2}∈\overline{S_{2}^{n}}(a^{1})} \frac{\binom{b_{1}^{1}}{a_{1}^{1}}\binom{b_{1}^{2}}{a_{1}^{2}}\binom{b_{2}^{2}}{a_{2}^{2}}}{r(a^{1}, a^{2})}

D_{n}^{3} = ∑_{a^{1}=1}^{n−1} ∑_{\underline{a}^{2}∈S_{2}^{n}(a^{1})} ∑_{\underline{a}^{3}∈S_{3}^{n}(a^{1},\underline{a}^{2})} \frac{\binom{b_{1}^{1}}{a_{1}^{1}}\binom{b_{1}^{2}}{a_{1}^{2}}\binom{b_{2}^{2}}{a_{2}^{2}}\binom{b_{1}^{3}}{a_{1}^{3}}\binom{b_{2}^{3}}{a_{2}^{3}}\binom{b_{3}^{3}}{a_{3}^{3}}\binom{b_{4}^{3}}{a_{4}^{3}}}{r(a^{1}, a^{2}, a^{3})}

T_{n}^{3} = ∑_{a^{1}=1}^{n−1} ∑_{\underline{a}^{2}∈S_{2}^{n}(a^{1})} ∑_{\underline{a}^{3}∈\overline{S_{3}^{n}}(a^{1},\underline{a}^{2})} \frac{\binom{b_{1}^{1}}{a_{1}^{1}}\binom{b_{1}^{2}}{a_{1}^{2}}\binom{b_{2}^{2}}{a_{2}^{2}}\binom{b_{1}^{3}}{a_{1}^{3}}\binom{b_{2}^{3}}{a_{2}^{3}}\binom{b_{3}^{3}}{a_{3}^{3}}\binom{b_{4}^{3}}{a_{4}^{3}}}{r(a^{1}, a^{2}, a^{3})}

By (41), b_{1}^{1} = a_{1}^{0} = n, b_{1}^{2} = a_{1}^{1} = a^{1}, b_{2}^{2} = a_{1}^{0} − a_{1}^{1} = n − a^{1}, b_{1}^{3} = a_{1}^{2}, b_{2}^{3} = a_{1}^{1} − a_{1}^{2} = a^{1} − a_{1}^{2}, b_{3}^{3} = a_{2}^{2}, and b_{4}^{3} = a_{1}^{0} − a_{2}^{2} − a_{1}^{1} = n − a^{1} − a_{2}^{2}. Note that by (32), I_{1}^{2} = {1}, I_{1}^{3} = {1, 2}, and I_{2}^{3} = {1, 3} So by (33) and (36),

S_{2}^{n}(a^{1}) = {(a_{1}^{2}, a_{2}^{2}): 0 ≤ a_{1}^{2} ≤ a^{1} − 1 & 0 ≤ a_{2}^{2} ≤ n − a^{1} & a^{1} ≤ a^{2} ≤ n − 1}
\overline{S_{2}^{n}}(a^{1}) = \{(a_{1}^{2}, a_{2}^{2}): 0 ≤ a_{1}^{2} ≤ a^{1} − 1 & a^{1} ≤ a^{2} ≤ n − 1 & a_{2}^{2} = n − a^{1}\}
S_{3}^{n}(a^{1}, \underline{a}^{2}) = \{(a_{1}^{3}, a_{2}^{3}, a_{3}^{3}, a_{4}^{3}): 0 ≤ a_{1}^{3} ≤ a_{1}^{2} & 0 ≤ a_{2}^{3} ≤ a^{1} − a_{1}^{2} & 0 ≤ a_{3}^{3} ≤ a_{2}^{2} &
0 ≤ a_{4}^{3} ≤ n − a^{1} − a_{2}^{2} & a^{2} ≤ a^{3} ≤ n − 1 &
a_{1}^{3} + a_{2}^{3} ≤ a^{1} − 1 & a_{1}^{3} + a_{3}^{3} ≤ a^{2} − 1}
\overline{S_{3}^{n}}(a^{1}, \underline{a}^{2}) = \{(a_{1}^{3}, a_{2}^{3}, a_{3}^{3}, a_{4}^{3}): 0 ≤ a_{1}^{3} ≤ a_{1}^{2} & 0 ≤ a_{2}^{3} ≤ a^{1} − a_{1}^{2} & 0 ≤ a_{3}^{3} ≤ a_{2}^{2} &
0 ≤ a_{4}^{3} = n − a^{1} − a_{2}^{2} & a^{2} ≤ a^{3} ≤ n − 1 &
a_{1}^{3} + a_{2}^{3} ≤ a^{1} − 1 & a_{1}^{3} + a_{3}^{3} ≤ a^{2} − 1}

It follows from the system of inequalities in S_{2}^{n}(a^{1}), that: max(0, 2a^{1} − n) ≤ a_{1}^{2} ≤ a^{1} − 1 and

1 ≤ a^{1} − a_{1}^{2} ≤ a_{2}^{2} ≤ n − a^{1} ≤ n − 1 − a_{1}^{2}.

From the system of inequalities and equality from \overline{S_{2}^{n}}(a^{1}) we obtain the same bound for a_{1}^{2} as above. Hence we obtain the same formulae (18) and (19) as in Example 10, as follows:

D_{n}^{2} = ∑_{a^{1}=1}^{n−1} ∑_{a_{1}^{2}=max(0,2a^{1}−n)}^{a^{1}−1} ∑_{a_{2}^{2}=a^{1}−a_{1}^{2}}^{n−a^{1}} \frac{\binom{n}{a_{1}^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n−a^{1}}{a_{2}^{2}}}{r(a^{1}, a^{2})}

T_{n}^{2} = ∑_{a^{1}=1}^{n−1} ∑_{a_{1}^{2}=max(0,2a^{1}−n)}^{a^{1}−1} \frac{\binom{n}{a_{1}^{1}}\binom{a^{1}}{a_{1}^{2}}}{r(a^{1}, a^{2})}.

Note that the systems of inequalities in S_{3}^{n}(a^{1}, \underline{a}^{2}) and \overline{S_{3}^{n}}(a^{1}, \underline{a}^{2}) are the same as in (29) from Example 10. Solving these systems we obtain the following formulas:

D_{n}^{3} = ∑_{a^{1}=1}^{n−1} ∑_{a_{1}^{2}=max(0,2a^{1}−n)}^{a^{1}−1} ∑_{a_{2}^{2}=a^{1}−a_{1}^{2}}^{min(n−a^{1},n−2)} ∑_{a_{1}^{3}=max(0,a^{2}+a_{1}^{2}−n)}^{min(a_{1}^{2},n−a_{2}^{2}−2)}

∑_{a_{2}^{3}=max(0,a^{1}+a_{2}^{2}−n+1,a^{1}+a^{2}−n−a_{1}^{3})}^{min(a^{1}−a_{1}^{2},a^{1}−1−a_{1}^{3})} ∑_{a_{3}^{3}=max(0,a^{2}+a_{2}^{2}−n,a^{1}+a^{2}+a_{2}^{2}−n−a_{1}^{3}−a_{2}^{3})}^{min(a_{2}^{2},a^{2}−1−a_{1}^{3})}

∑_{a_{4}^{3}=max(0,a^{2}−a_{1}^{3}−a_{2}^{3}−a_{3}^{3})}^{min(n−a^{1}−a_{2}^{2},n−1−a_{1}^{3}−a_{2}^{3}−a_{3}^{3})} \frac{\binom{n}{a_{1}^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n−a^{1}}{a_{2}^{2}}\binom{a_{1}^{2}}{a_{1}^{3}}\binom{a^{1}−a_{1}^{2}}{a_{2}^{3}}\binom{a_{2}^{2}}{a_{3}^{3}}\binom{n−a^{1}−a_{2}^{2}}{a_{4}^{3}}}{r(a^{1}, a^{2}, a^{3})}

T_{n}^{3} = ∑_{a^{1}=1}^{n−1} ∑_{a_{1}^{2}=max(0,2a^{1}−n)}^{a^{1}−1} ∑_{a_{2}^{2}=a^{1}−a_{1}^{2}}^{min(n−a^{1},n−2)} ∑_{a_{1}^{3}=max(0,a^{2}+a_{1}^{2}−n)}^{min(a_{1}^{2},n−a_{2}^{2}−2)} ∑_{a_{2}^{3}=max(0,a^{1}+a_{2}^{2}−n+1,a^{1}+a^{2}−n−a_{1}^{3})}^{min(a^{1}−a_{1}^{2},a^{1}−1−a_{1}^{3})}

∑_{a_{3}^{3}=max(0,a^{2}+a_{2}^{2}−n,a^{1}+a^{2}+a_{2}^{2}−n−a_{1}^{3}−a_{2}^{3})}^{min(a_{2}^{2},a^{2}−1−a_{1}^{3})} \frac{\binom{n}{a_{1}^{1}}\binom{a^{1}}{a_{1}^{2}}\binom{n−a^{1}}{a_{2}^{2}}\binom{a_{1}^{2}}{a_{1}^{3}}\binom{a^{1}−a_{1}^{2}}{a_{2}^{3}}\binom{a_{2}^{2}}{a_{3}^{3}}}{r(a^{1}, a^{2}, a^{3})}.

Table 1 gives the number of all summands in the sums (39) denoted by N_{A}^{m}(n), the number of all summands in the sums (40) denoted by N_{AC}^{m}(n), as well as values of D_{n}^{m} and T_{n}^{m} for n ∈ \{4, 5\} and m ∈ \{2, …, \binom{n}{⌊n/2⌋} − 1\}. Trivial cases when m ∈ \{0, 1, \binom{n}{⌊n/2⌋}\} are omitted in the table. They are considered in the following remark.

Remark 21. For all natural numbers n ∈ ℕ_{0}:

1. D_{n}^{0} = T_{n}^{0} = 1;

2. D_{n}^{1} = 2^{n} and T_{n}^{1} = 1;

3. if m = \binom{n}{⌊n/2⌋}, then D_{n}^{m} = T_{n}^{m} = \begin{cases}1, & if 2 | n; \\ 2, & if 2 ∤ n; \end{cases}

4. if m = \binom{n}{⌊n/2⌋} − 1, then T_{n}^{m} = \begin{cases}\binom{n}{⌊n/2⌋}, & if 2 | n; \\ 2\binom{n}{⌊n/2⌋}, & if 2 ∤ n; \end{cases}

5. if \binom{n−1}{⌊(n−1)/2⌋} < m ≤ \binom{n}{⌊n/2⌋}, then T_{n}^{m} = D_{n}^{m};

n m N_{A}^{m}(n) N_{AC}^{m}(n) D_{n}^{m} T_{n}^{m}
4 2  7  4  55 25
3  11  9  64 56
4  19  19  25 25
5  30  30  6  6
5 2  13  6  285 90
3  40  29  1090 790
4 164  145 2020 1895
5 760  730 2146 2116
6 3180  3150 1380 1375
7 11148 11148 490 490
8 31104 31104 115 115
9 60480 60480 20 20

Table 1: The number of all summands in the sums (39) — N_{A}^{m}(n), (40) — N_{AC}^{m}(n), D_{n}^{m}, and T_{n}^{m} for n ∈ \{4, 5\} and m ∈ \{2, …, \binom{n}{⌊n/2⌋} − 1\}.

Tables 2 and 3 depict the number of all summands in the sums (39) and (40) — N_{A}^{m}(n) and N_{AC}^{m}(n), respectively, as well as values of D_{n}^{m} and T_{n}^{m}, respectively, for n ∈ {6, …, 15} and m ∈ {2, 3, 4}.

\begin{matrix}n & N_{A}^{2}(n) & D_{n}^{2} & N_{A}^{3}(n) & D_{n}^{3} & N_{A}^{4}(n) & D_{n}^{4} \\ 6 & 22 & 1351 & 113 & 14000 & 913 & 82115 \\ 7 & 34 & 6069 & 272 & 153762 & 3889 & 2401910 \\ 8 & 50 & 26335 & 585 & 1533504 & 13850 & 58089465 \\ 9 & 70 & 111645 & 1154 & 14356610 & 43157 & 1245331920 \\ 10 & 95 & 465751 & 2129 & 128722000 & 121243 & 24625121455 \\ 11 & 125 & 1921029 & 3718 & 1119607522 & 313162 & 460316430970 \\ 12 & 161 & 7859215 & 6208 & 9528462944 & 754557 & 8266174350005 \\ 13 & 203 & 31964205 & 9976 & 79817940930 & 1714126 & 144171200793620 \\ 14 & 252 & 129442951 & 15520 & 660876543600 & 3702041 & 2461016066613195 \\ 15 & 308 & 522538389 & 23470 & 5424917141282 & 7650964 & 41343340015862430 \end{matrix}

Table 2: The number of all summands in the sums (39) — N_{A}^{m}(n) and values of D_{n}^{m} for n ∈ {6, …, 15} and m ∈ {2, 3, 4}.

\begin{matrix}n & N_{AC}^{2}(n) & T_{n}^{2} & N_{AC}^{3}(n) & T_{n}^{3} & N_{AC}^{4}(n) & T_{n}^{4} \\ 6 & 9 & 301 & 73 & 8380 & 749 & 70370 \\ 7 & 12 & 966 & 159 & 76482 & 2976 & 1868650 \\ 8 & 16 & 3025 & 313 & 638736 & 9961 & 41062035 \\ 9 & 20 & 9330 & 569 & 5043950 & 29307 & 802349205 \\ 10 & 25 & 28501 & 975 & 38390660 & 78086 & 14514339340 \\ 11 & 30 & 86526 & 1589 & 285007162 & 191919 & 249104207000 \\ 12 & 36 & 261625 & 2490 & 2079779416 & 441395 & 4120588431245 \\ 13 & 42 & 788970 & 3768 & 14995363110 & 959569 & 66392465654515 \\ 14 & 49 & 2375101 & 5544 & 107204473740 & 1987915 & 1049608974433110 \\ 15 & 56 & 7141686 & 7950 & 761823557042 & 3948923 & 16365222591176550 \end{matrix}

Table 3: The number of all summands in the sums (40) — N_{AC}^{m}(n) and values of T_{n}^{m} for n ∈ {6, …, 15} and m ∈ {2, 3, 4}.

Table 4 presents values of T_{n}^{m} for n ∈ {16, …, 50} and m ∈ {2, 3}.

Table 5 presents values of T_{n}^{m,k} for n = 7, m ∈ \{2, …, 35\}, and all possible k, i.e., k ≥ \frac{7}{m} and \binom{7}{k} ≥ m.

Methods enabling the computation of T_{n}^{m}, D_{n}^{m} for all n ∈ ℕ and 1 ≤ m ≤ \binom{n}{⌊n/2⌋}, as well as a method allowing the determination of T_{n}^{m,k}, for all m, n, k ∈ ℕ such that \frac{n}{k} ≤ m ≤ \binom{n}{k} were programmed in R. These methods were used to obtain results from Tables 1–3, 5, and 6. Methods permitting the determination of T_{n}^{m} for m ∈ {2, 3, 4} and all natural numbers n ≥ 4 were programmed in Maple, and were used to obtain the results in Table 4. All methods written in R were implemented on a PC with Intel Core i7-8750H 2.20-GHz CPU and 16 GB of RAM. However, methods written in Maple were implemented on a PC with Intel Core i5-3230M 2.60-GHz CPU and 6 GB of RAM.

Table 6 presents the running time of the method Ind(n, m, ind(n, m−1)) determining the list ind(n, m) of all possible sequences \underline{a}^{1}, …, \underline{a}^{m} for m ∈ \{2, 3, 4\} and n ∈ \{12, 13, 14, 15\} such that \underline{a}^{k} ∈ S_{k}^{n}(\underline{a}^{1}, …, \underline{a}^{k−1}), where S_{k}^{n}(\underline{a}^{1}, …, \underline{a}^{k−1}) are defined by (36), as well as the method AC(n, m, ind(n, m)) computing D_{n}^{m} and T_{n}^{m} according to (39) and (40) for m ∈ {2, 3, 4}, n ∈ {12, 13, 14, 15}, and the list of sequences ind(n, m). The list ind_{c}(n, m) of all possible sequences \underline{a}^{1}, …, \underline{a}^{m} suitable for (40) can be easily and quickly obtained from the list ind(n, m) of all possible sequences \underline{a}^{1}, …, \underline{a}^{m} suitable for (39). Therefore the running time of the procedure convToCl, converting one list into another, is omitted.

It can be seen in Table 6 that methods Ind and AC, based on Theorem 11, allow us to effectively compute D_{n}^{m} and T_{n}^{m} for small m ∈ {2, 3} and relatively large n.

\begin{matrix}n & T_{n}^{2} & T_{n}^{3} \\ 16 & 21457825 & 5390550296096 \\ 17 & 64439010 & 38026057186270 \\ 18 & 193448101 & 267656481977620 \\ 19 & 580606446 & 1881017836414122 \\ 20 & 1742343625 & 13204444871932776 \\ 21 & 5228079450 & 92618543463601430 \\ 22 & 15686335501 & 649270263511862300 \\ 23 & 47063200806 & 4549607376865786402 \\ 24 & 141197991025 & 31870882201493713456 \\ 25 & 423610750290 & 223214539710301456590 \\ 26 & 1270865805301 & 1563094445025734127780 \\ 27 & 3812664524766 & 10944627831536630201882 \\ 28 & 11438127792025 & 76627241923504206742136 \\ 29 & 34314651811530 & 536464983051964328959750 \\ 30 & 34314651811530 & 3755626545565209968614060 \\ 31 & 308834550658326 & 26291245004929410021308562 \\ 32 & 926505799458625 & 184048014423958633597002816 \\ 33 & 2779521693343170 & 1288382611752502969073278910 \\ 34 & 8338573669964101 & 9018910891539127690443801140 \\ 35 & 25015738189761486 & 63133539508515093365692674442 \\ 36 & 75047248929022825 & 441940593783822075229938159496 \\ 37 & 225141815506545210 & 3093613246149811622777248142070 \\ 38 & 675425583958589101 & 21655438185531666666398473609020 \\ 39 & 2026277026753674246 & 151588794667806792127575720587522 \\ 40 & 6078831630016836625 & 1061125199746752166787452564356176 \\ 41 & 18236495989562137650 & 7427894584494498851907618171437230 \\ 42 & 54709490167709668501 & 51995353026424486474819809382197700 \\ 43 & 164128474901175516606 & 363967925874293633608399150016855802 \\ 44 & 492385433499619572025 & 2547777754624695453699489227563016856 \\ 45 & 1477156318091044760490 & 17834455650128183338493646918462812390 \\ 46 & 4431468989457506370301 & 124841246390602318150989020114676767180 \\ 47 & 13294407038741263288566 & 873889008936455232899697038492373607282 \\ 48 & 39883221256961278221025 & 6117224483581236975434924744272427645536 \\ 49 & 119649664052358811373730 & 42820578490258331781970654161998901275550 \\ 50 & 358948992720026387542501 & 299744084957994372050034044992597868357460 \end{matrix}

Table 4: Values of T_{n}^{m} for n ∈ {16, …, 50} and m ∈ {2, 3}.

m k T_{7}^{m,k}  m k T_{7}^{m,k}  m k T_{7}^{m,k}  m k T_{7}^{m,k}
2 4 70  8 2 159390  15 2 54257  22 3 1476337800
5 105  3 22654975  3 3247834632  4 1476337800
6 21  4 23490775  4 3247943153 23 3 834451800
3 3 945  5 203490  5 54264  4 834451800
4 3570  9 2 259105  16 2 20349  24 3 417225900
5 1190  3 69431950  3 4059895035  4 417225900
6 35  4 70572425  4 4059928950 25 3 183579396
4 2 315  5 293930  5 20349  4 183579396
3 22820 10 2 331716  17 2 5985  26 3 70607460
4 42910  3 182286125  3 4537559670  4 70607460
5 5880  4 183558375  4 4537567650 27 3 23535820
6 35  5 352716  5 5985  4 23535820
5 2 4410  11 2 343161  18 2 1330  28 3 6724520
3 221396  3 416050180  3 4537566320  4 6724520
4 303632  4 417216345  4 4537567650 29 3 1623160
5 20307  5 352716  5 1330  4 1623160
6 21  12 2 290745  19 2 210  30 3 324632
6 2 23604  3 833570010  3 4059928810  4 324632
3 1356250  4 834448615  4 4059928950 31 3 52360
4 1588125  5 293930  5 210  4 52360
5 54257 13 2 202755  20 2 21  32 3 6545
6 7  3 1475795160  3 3247943153  4 6545
7 1 1  4 1476337065  4 3247943160 33 3 595
2 73755  5 203490  5 21  4 595
3 6184400 14 2 116175  21 2 1  34 3 35
4 6679475  3 2319688080  3 2319959400  4 35
5 116280  4 2319959295  4 2319959400 35 3 1
6 1  5 116280  5 1  4 1

Table 5: Values of T_{n}^{m,k} for n = 7, m ∈ {2, …, 35}, and all possible k.

5 Acknowledgment

The author gratefully acknowledges Charlotte Stȩpien for checking the text as well as the anonymous referee for valuable comments and suggestions.

Computational time (s)

n m Ind(n, m, ind(n, m − 1)) AC(n, m, ind(n, m)) AC(n, m, ind_{c}(n, m))
12 2 0.01  0.01  0
3 0.19  0.05  0.01
4 205.98  12.89  7.76
13 2 0  0  0
3 0.24  0.11  0.03
4 536.09  29.55  17.03
14 2 0  0  0
3 0.32  0.18  0.06
4 1668.4  65.19  34.6
15 2 0  0  0
3 0.47  0.25  0.079
4 5217.23  136.77  73.77

Table 6: The running time of methods Ind(n, m), AC(n, m, A) for m ∈ {2, 3, 4}, n ∈ {12, 13, 14, 15}, and A ∈ {ind(n, m), ind_{c}(n, m)}.

References

[1] V. Bakoev, One more way for counting monotone Boolean functions, Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory, Pomorie, Bulgaria, 2012 , pp. 47–52.

[2] R. Baumann and H. Strass, On the number of bipolar Boolean functions, J. Logic Comput. 27 (2017), 2431–2449.

[3] P. De Causmaecker and S. De Wannemacker, On the number of antichains of sets in a finite universe, preprint, 2014. Available at https://arxiv.org/abs/1407.4288.

[4] R. Church, Numerical analysis of certain free distributive structures, Duke. Math. J. 6 (1940), 732–734.

[5] R. Church, Enumeration by rank of the elements of the free distributive lattice with 7 generators, Notices Amer. Math. Soc. 12 (1965), 724.

[6] R. J. Clarke, Covering a set by subsets, Discrete Math. 81 (1990), 147–152.

[7] R. Dedekind, Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Theiler, Fest-Schrift der Herzoglichen Technischen Hochschule Carolo-Wilhelmina, Vieweg+Teubner Verlag, 1897, pp. 1–40.

[8] R. Fidytek, A. W. Mostowski, R. Somla, and A. Szepietowski, Algorithms counting monotone Boolean functions, Inform. Process. Lett. 79 (2001), 203–209.

[9] T. Hearne and C. Wagner, Minimal covers of finite sets, Discrete Math. 5 (1973), 247–251.

[10] V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F_{8}^{μ}, Diskretnaya Matematika 11 (1999), 127–138, translated in Discrete Math. Appl. 9 (1999), no. 6.

[11] V. Jovovic and G. Kilibarda, Antichains of multisets, J. Integer Sequences 7 (2004), Article 04.1.5.

[12] J. Kahn, Entropy, independent sets and antichains: a new approach to Dedekind’s problem, Proc. Amer. Math. Soc. 130 (2002), 371–378.

[13] G. Kilibarda, Enumeration of certain classes of antichains, Publications de l’Institut Mathematique, Nouvelle série, 97 (2015), 69–87.

[14] A. Kisielewicz, A solution of Dedekind’s problem on the number of isotone Boolean functions, J. Reine Angew. Math. 386 (1988), 139–144.

[15] D. Kleitman, On Dedekind’s problem: the number of isotone Boolean functions, Proc. Amer. Math. Soc. 21 (1969), 677–682.

[16] D. Kleitman and G. Markowsky, On Dedekind’s problem: the number of isotone Boolean functions, Trans. Amer. Math. Soc. 213 (1975), 373–390.

[17] A. D. Korshunov, The number of monotone Boolean functions, Problemy Kibernet. 38 (1981), 5–108.

[18] A. J. Macula, Covers of a finite set, Math. Mag. 67 (1994), 141–144.

[19] R. B. Nelsen and H. Schmidt, Chains in power sets, Math. Mag. 64 (1991), 23–31.

[20] I. Rival, Unsolved problems, Order, 1 (1984), 103–105.

[21] B. S. W. Schröder, Ordered Sets: An Introduction, Springer, 2003.

[22] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available

    at https://oeis.org.

[23] E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27 (1928), 544–548.

[24] C. Wagner, Minimal multiplicative covers of an integer, Discrete Math. 24 (1978), 87–94.

[25] M. Ward, Note on the order of free distributive lattices, Bull. Amer. Math. Soc. 52 (1946), 423.

[26] D. Wiedemann, A computation of the eighth Dedekind number, Order 8 (1991), 5–6.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 90B25. Keywords: ordered set, antichain, cover, Dedekind number.

(Concerned with sequences \underline{A000372}, \underline{A000392}, \underline{A006126}, \underline{A016269}, \underline{A047707}, \underline{A051112}, \underline{A056046}, and \underline{A056047}.)

Received September 1 2020; revised versions received February 17 2021; April 16 2021. Published in Journal of Integer Sequences, April 17 2021.

Return to Journal of Integer Sequences home page.