Antichains of Multisets

Goran Kilibarda and Vladeta Jovović Faculty of Technology and Metallurgy University of Belgrade Karnegijeva 4 11001 Belgrade Serbia and Montenegro

                       gkilibar@EUnet.yu
                       vladeta@EUnet.yu

Abstract

The problem of enumeration of m-antichains of k-bounded multisets on an n-set is considered. A formula for calculating the cardinality of the corresponding family in terms of the graph theory was obtained. A more general case of multiantichains is also considered. As an illustration the corresponding explicit formulas are given for the case when 1 ≤ m ≤ 4, k ≥ 1 and n ≥ 0.

1 Introduction

By an m-antichain (an antichain or a Sperner family of the length m) on an n-set S we mean a family A of m subsets of S satisfying the condition A_{1} ⊈ A_{2} for every A_{1}, A_{2} ∈ A, A_{1} ≠ A_{2}. Denote by α(m, n) the number of all m-antichains on an n-set. From Sperner’s lemma [1] it follows that α(m, n) = 0 for all m > \binom{n}{⌊n/2⌋}. Thus, knowing the numbers α(m, n), 0 ≤ m ≤ \binom{n}{⌊n/2⌋}, we can find the number α(n) of all antichains on an n-set. The problem of finding numbers α(n) has a long history, and it is known as the Dedekind problem. It was formulated by R. Dedekind [2] as far back as 1897 as the problem of determining the number of elements in a free distributive lattice F D(n) on n generators (see also [3]). In terms of the theory of Boolean functions the problem is equivalent to the problem of enumerating the class A_{1}(n) of all monotone Boolean functions of n variables.

The expressions for the numbers α(m, n), when 1 ≤ m ≤ 3, and n is an arbitrary nonnegative integer, were obtained by N.M. Riviere [4]. D. Cvetković [5] solved the case m = 4 basically by computer generation. A further contribution to the solving of the problem was made by J.L. Arocha [6, 7], who gave in [7] the corresponding formulas for the case m = 5, 6.

Kilibarda and Jovović in [8] gave a general procedure for calculating numbers α(m, n), which made it possible to find the corresponding explicit formulas for the case when 1 ≤ m ≤ 10 and n is arbitrary. There it also is shown that the problem of finding numbers α(m, n) can be reduced to the problem of enumerating so-called ordered (n, m)-T_{1}-hypergraphs, which in its turn can be reduced to the problem of finding the number of all connected bipartite graphs with fixed numbers of vertices and edges, and with a given number of 2-colorings of a certain type.

In this paper we consider the problem that naturally arises as a generalization of the above mentioned problem of calculating numbers α(m, n). In fact, here we consider the problem of finding the number α(k, m, n) of all m-antichains of k-bounded multisets on an n-set. It turns out that ”increasing the dimension” of the problem does not impose particular modification on the corresponding formula obtained in [8]. The formula obtained in this paper, a special case of which is the formula from [8] for finding numbers α(m, n), has the same structure up to the type of colorings. Thus the generalization of the problem discussed in [8] affects only the complexity of determining the number of respective colorings.

Note that one of the interpretations of the number α(k, m, n) is the following: it is equal to the number of all monotone k-valued Boolean functions of n variables with m lower units, and with their values from the set {0, 1}.

We also consider a more general problem of finding numbers α^{∗}(k, m, n) of all (k, m, n)- multiantichains of multisets on an n-set.

At the end of the paper as an illustration we give explicit expressions for the numbers α(k, m, n) and α^{∗}(k, m, n), k ∈ N, 1 ≤ m ≤ 4, n ∈ N_{0}.

2 Basic notions

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\}. By pr_{i}(a), i ∈ \overline{n}, denote the i-th component of an n-tuple a.

Let (a_{1}, …, a_{n}) and (b_{1}, …, b_{n}) be two n-tuples from the set ( \overline{0, k − 1} )^{n}. We write (a_{1}, …, a_{n}) ≤ (b_{1}, …, b_{n}) if a_{i} ≤ b_{i} for every i ∈ \overline{n}. If, in addition, there exists i_{0} ∈ \overline{n} such that a_{i_{0}} < b_{i_{0}}, we write (a_{1}, …, a_{n}) < (b_{1}, …, b_{n}).

Let us introduce some notions which we are going to use in the paper. The notions of the graph theory that we do not define here are taken from [9].

Following [1], by a multiset on a set S we mean an ordered pair consisting of S and a mapping f: S → N_{0}; the value f(s) is called multiplicity of s ∈ S in (S, f). By cardinality of a multiset a = (S, f) we mean the number |a| = ∑_{s∈S} f(s). A multiset a is called an m-multiset if |a| = m. Let a = (S, f) and b = (S, g) be two multisets. We write a ⊆ b if f(s) ≤ g(s) for every s ∈ S.

A multiset a = (S, f) is called k-bounded (k ∈ N) if f(s) ≤ k − 1 for every s ∈ S. Then, actually, a 2-bounded multiset on S is simply a subset of S, and an 1-bounded multiset is the empty set. Let us denote by M_{k}(S) the set of all k-bounded multisets on S.

Let M be a set of multisets on S. Let us call it an antichain of multisets on S if a ⊈ b for every a, b ∈ M, a ≠ b. If |M| = m (m ∈ N_{0}), then we also call M an m-antichain on S. In the following for brevity sake instead of antichain of multisets on S we shall simply say an antichain on S.

Let us fix an n-set S = {s_{1}, …, s_{n}}, and define on S a linear order ≤ in the following way: s_{1} ≤ s_{2} ≤ ⋯ ≤ s_{n}. Every multiset considered here will be a multiset on S. In what follows, instead of the notation M_{k}(S) we use M_{k}. Obviously, every multiset a = (S, f) can be given by the n-tuple a⃗ = (f(s_{1}), …, f(s_{n})).

Let us denote by A(k, m, n) the set of all m-antichains of k-bounded multisets on S. Also, let α(k, m, n) = |A(k, m, n)|. Our goal is to find the numbers α(k, m, n). Let M ⊆ M_{k}. It is easy to see that M ∈ A(k, m, n) iff a⃗ ≰ b⃗ for every a, b ∈ M, a ≠ b.

We denote the set of vertices of a digraph G by V G, and the set of its arcs — by EG. Let G = (V, E) be a digraph, and let k ∈ N. By k-coloring of G we mean a mapping

ν : V → \overline{0, k − 1}. We say that a vertex from the set ν^{−1}(i) (i ∈ \overline{0, k − 1}) is i-colored. If a k-coloring ν is a mapping onto we call it an exact k-coloring. A k-coloring ν of a digraph is called monotone if ν(u) ≤ ν(v) for every (u, v) ∈ E. By H_{k}(D) (Ĥ_{k}(D)) denote the set of all monotone k-colorings (exact k-colorings) of a digraph D, and let η_{k}(D) = |H_{k}(D)| (η̂_{k}(D) = |Ĥ_{k}(D)|); in the following, k is fixed, and because of that, instead of H_{k}(D) (Ĥ_{k}(D)) and η_{k}(D) (η̂_{k}(D)) we usually write H(D) (Ĥ(D)) and η(D) (η̂(D)), respectively.

3 On the number of m-antichains of k-bounded multisets on an n-set

Let us fix an infinite countable set V_{∞} = {v_{1}, v_{2}, … } such that V_{∞} ∩ S = ∅. Put V_{m} = {v_{1}, v_{2}, …, v_{m}} for every natural number m. 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}.

Let D ∈ D_{m}. Let us denote by F (D) the set of all functions f: V_{m} → M_{k} satisfying the following condition: if (v, v′) ∈ ED, then f(v) ⊆ f(v′). Assign to every function f ∈ F (D) the m-tuple M⃗(f) = (a_{1}, …, a_{m}) of multisets on S such that a_{i} = f(v_{i}) for every i ∈ \overline{m}. Let 𝔐(D) = {M⃗(f) | f ∈ F (D)} and λ(D) = |F (D)| = |𝔐(D)|.

Let us denote by A⃗(k, m, n) the set of all m-tuples (a_{1}, …, a_{m}) of k-bounded multisets on S satisfying the condition that the set consisting of these multisets is an m-antichain. Let α⃗(k, m, n) = |A⃗(k, m, n)|. Then it is clear that

α⃗(k, m, n) = m! α(k, m, n).  (1)

Denote by J_{m} the set of all digraphs from D_{m} in which there is no directed path of the length ≥ 2. Let us call every digraph from J_{m} a hedgehog. Denote by V_{1}(J) (V_{2}(J)) the set of all vertices of a hedgehog J ∈ J_{m} for which the input (output) degree is equal to 0. It is clear that V_{0}(J) = V_{1}(J) ∩ V_{2}(J) is the set of all isolated vertices of the hedgehog J. The set V_{1}(J)\V_{0}(J) (V_{2}(J)\V_{0}(J)) is called the upper (lower) part of J.

The proof of the following lemma can be found in [8]. Here we give another proof of this assertion.

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

Proof . Put H_{m}(x) = ∑_{i=0}^{s} h_{m,i} x^{i}, where s = ⌊\frac{m^{2}}{4} ⌋, and h_{m,i} is the number of all

hedgehogs with m vertices and i arcs. It is not difficult to show that H_{m}(x) = ∑_{k=0}^{m} \binom{m}{k}((1+ x)^{m−k} − 1)^{k} (\underline{A052296}). Henceforth we have that ∑_{D∈J_{m}}(−1)^{|ED|} = H_{m}(−1) = (−1)^{m−1}. □

Note that H_{m}(1) = ∑_{k=0}^{m} \binom{m}{k}(2^{m−k} − 1)^{k} is the number of hedgehogs with m vertices (\underline{A001831}).

Also, denote by 𝔐^{(i)}(D), i ∈ \overline{m}, the set of all m-tuples from 𝔐(D) containing exactly i different multisets. It is clear that

λ(D) = ∑_{i=1}^{m} |𝔐^{(i)}(D)|.  (2)

Let s(n, k) and S(n, k) be Stirling numbers of the first and second kind respectively [1].

Lemma 3.2 For every i ∈ \overline{m},

∑_{D∈J_{m}}(−1)^{|ED|}|𝔐^{(i)}(D)| = (−1)^{m−i} S(m, i) α⃗(k, i, n).

Proof . First, let us introduce families: 𝔓_{j} = \{M ⊆ M_{k} | |M| = j\} (j ∈ \overline{m}), 𝔓′_{1} = ∅, 𝔓′_{j} = \{M ∈ 𝔓_{j} | (∃ a, b ∈ M) a ⊆ b ∧ a ≠ b\} (j ∈ \overline{2, m}), 𝔓′′_{j} = 𝔓_{j}\𝔓′_{j} (j ∈ \overline{m}). It is clear that 𝔓′′_{j} = A(k, j, n) for every j ∈ \overline{m}.

Fix some i ∈ \overline{m}, and let M ∈ 𝔓_{i}. Let F (M) = \{f : V_{m} → M_{k} | f(V_{m}) = M\} and F (D, M) = F (M) ∩ F (D) for every D ∈ D_{m}. Also, by J_{m}(M) denote the set of all vertexweighted digraphs (D, f) such that D ∈ J_{m} and f ∈ F (D, M). Let V_{m}(a; D, f) = {v ∈ V_{m} | f(v) = a} for every (D, f) ∈ J_{m}(M) and a ∈ M. Obviously the following equation holds:

σ = ∑_{D∈J_{m}}(−1)^{|ED|}|𝔐^{(i)}(D)| = ∑_{D∈J_{m}}(−1)^{|ED|} ∑_{M∈𝔓_{i}} |F (D, M)| =
= ∑_{M∈𝔓_{i}} ∑_{D∈J_{m}}(−1)^{|ED|}|F (D, M)| = ∑_{M∈𝔓_{i}} ∑_{(D,f)∈J_{m}(M)}(−1)^{|ED|} =
= ∑_{M∈𝔓′_{i}} ∑_{(D,f)∈J_{m}(M)}(−1)^{|ED|} + ∑_{M∈𝔓′′_{i}} ∑_{(D,f)∈J_{m}(M)}(−1)^{|ED|}.

In the above expression denote the first sum after the last sign = by σ_{1}, and the second one — by σ_{2}. Note that if i = 1, then σ_{1} = 0, and consequently σ = 0 + σ_{2} = σ_{2}. Let us show that the equation σ = σ_{2} holds for every i ∈ \overline{m}.

Take some M ∈ 𝔓′_{i}, i ∈ \overline{2, m}. Then there exists a′, b′ ∈ M, a′ ≠ b′, so that a′ ⊆ b′. Let a and b be respectively the minimal element and the maximal element of a chain in M containing a′ and b′. It is clear that for every (D, f) ∈ J_{m}(M) the sets V_{m}^{(1)}(a; D, f) = V_{1}(D) ∩ V_{m}(a; D, f) and V_{m}^{(2)}(b; D, f) = V_{2}(D) ∩ V_{m}(b; D, f) are nonempty. Break the class J_{m}(M) into subclasses [J_{m}(M)]_{j}, j = 1, …, c_{0}, so that two digraphs (D′, f′), (D′′, f′′) belong to the same subclass [J_{m}(M)]_{j} iff f′ = f′′ = f, V_{m}^{(1)}(a; D′, f′) = V_{m}^{(1)}(a; D′′, f′′), V_{m}^{(2)}(b; D′, f′) = V_{m}^{(2)}(b; D′′, f′′) and (V_{m}, ED′\E_{0}) = (V_{m}, ED′′\E_{0}) = D̂_{j}, where E_{0} = V_{m}^{(1)}(a; D′, f) × V_{m}^{(2)}(b; D′, f). Now we have

\begin{matrix}σ_{1}(M) = ∑_{(D,f)∈J_{m}(M)}(−1)^{|ED|} = ∑_{j=1}^{c_{0}} ∑_{(D,f)∈[J_{m}(M)]_{j}}(−1)^{|ED|} = \\ = ∑_{j=1}^{c_{0}}(−1)^{|ED̂_{j}|} ∑_{E′⊆E_{0}}(−1)^{|E′|} = 0. \end{matrix}

As σ_{1}(M) = 0 for every M ∈ 𝔓′_{i}, we have again that σ_{1} = 0.

Now let M ∈ 𝔓′′_{i}, i ∈ \overline{m}. Note that a ⊈ b for every two different a, b ∈ M. Break the class J_{m}(M) into subclasses [J_{m}(M)]_{f}, f ∈ F (M) so that the digraph (D′, f′) ∈ J_{m}(M) belongs to the subclass [J_{m}(M)]_{f} iff f′ = f. Then we have

σ = σ_{2} = ∑_{M∈𝔓′′_{i}} ∑_{f∈F (M)} ∑_{(D,f)∈[J_{m}(M)]_{f}}(−1)^{|ED|}.

Let us fix M = {a_{1}, …, a_{i}} ∈ 𝔓′′_{i} and f ∈ F (M), and take some (D, f) ∈ [J_{m}(M)]_{f}. Put W_{j} = V_{m}(a_{j}; D, f), D′_{j} = (W_{j}, ED ∩ W_{j}^{2}) and m_{j} = |W_{j}| for every j ∈ \overline{i}. Note that ED∩(W_{j_{1}} ×W_{j_{2}}) = ∅ for every j_{1}, j_{2} ∈ \overline{i}, j_{1} ≠ j_{2}. By D_{j}, j ∈ \overline{i}, denote the digraph from J_{m_{j}} that is isomorphic to D′_{j}. It is clear that when (D, f) passes completely the set [J_{m}(M)]_{f} then the digraph D_{j} for every j ∈ \overline{i} passes the whole set J_{m_{j}}. Then using Lemma 3.1 we have

∑_{(D,f)∈[J_{m}(M)]_{f}}(−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}.

Note that |𝔓′′_{i}| = α(k, i, n) and |F (M)| = i!S(m, i). Finally, using (1) we get

\begin{aligned}σ & = & ∑_{D∈J_{m}}(−1)^{|ED|}|𝔐^{(i)}(D)| = (−1)^{m−i} ∑_{M∈𝔅′′_{i}} ∑_{f∈F (M)} 1 = \\ & = & (−1)^{m−i}α(k, i, n) i! S(m, i) = (−1)^{m−i}S(m, i) α⃗(k, i, n). □ \end{aligned}

Now we could give the basic formula of the paper.

Theorem 3.1 For every k, m ∈ N and n ∈ N_{0},

α(k, m, n) = \frac{1}{m!} ∑_{i=1}^{m} |s(m, i)| β(k, i, n),

where

β(k, i, n) = ∑_{D∈J_{i}}(−1)^{|ED|}λ(D).

Proof . From (2) it follows that

β(k, m, n) = ∑_{D∈J_{m}}(−1)^{|ED|} ∑_{i=1}^{m} |𝔐^{(i)}(D)|.

Changing the order of summation in the last sum and using Lemma 3.2, we obtain that

β(k, m, n) = ∑_{i=1}^{m} ∑_{D∈J_{m}}(−1)^{|ED|}|𝔐^{(i)}(D)| = ∑_{i=1}^{m}(−1)^{m−i} S(m, i) α⃗(k, i, n).

Finally, applying the Stirling inversion [1] to the previous formula we get

α⃗(k, m, n) = ∑_{i=1}^{m} |s(m, i)| β(k, i, n).  (3)

Now from (1) follows the statement. □

It is easy to see that the following statement holds.

Lemma 3.3 If C_{1}, C_{2}, …, C_{i} are all weak components of a digraph D, then we have

λ(D) = λ(C_{1}) · λ(C_{1}) · . . . · λ(C_{i}).

Let B_{n}(k_{1}, k_{2}, …, k_{n}) be the number of all partitions of an n-set into k_{1} + k_{2} + ⋯ + k_{n} subsets among which there are exactly k_{i} i-subsets (i ∈ \overline{n}). Then the polynomials

Y_{n}(x_{1}, x_{2}, …, x_{n}) = ∑_{(k_{1},k_{2},...,k_{n})} B_{n}(k_{1}, k_{2}, …, k_{n}) x_{1}^{k_{1}}x_{2}^{k_{2}} … x_{n}^{k_{n}},

where k_{1} + 2k_{2} + ⋯ + nk_{n} = n (k_{i} ≥ 0), are called, as it is known, Bell polynomials [10]. Let J_{m}^{c} be the set of all weakly connected hedgehogs from the set D_{m}, and let

γ(k, i, n) = ∑_{D∈J_{i}^{c}}(−1)^{|ED|}λ(D), i ∈ \overline{1, m}.

Now using Lemma 3.3 we can pass in Theorem 3.1 from the class of all hedgehogs to the class of all connected hedgehogs.

Lemma 3.4 For every i ∈ \overline{m}, β(k, i, n) = Y_{i}(γ(k, 1, n), γ(k, 2, n), …, γ(k, i, n)).

The following assertion shows in which way the number λ(D) is connected with the number of all monotone k-colorings of a digraph D.

Lemma 3.5 For every D ∈ D_{m}, λ(D) = η^{n}(D).

Proof . Let a digraph D be given, and let (a_{1}, …, a_{m}) ∈ 𝔐(D). Note that a_{i} ⊆ a_{j} (i, j ∈ \overline{m}, i ≠ j) iff a⃗_{i} ≤ a⃗_{j}. Hence it follows that for every i ∈ \overline{n}, the mapping ν̂_{i} of V_{m} into \overline{0, k − 1}, where ν̂_{i}(v_{j}) = pr_{i}(a_{j}) for every j ∈ \overline{m}, is a monotone k-coloring of D. Assign to (a_{1}, …, a_{m}) the ordered n-tuple (ν̂_{1}, …, ν̂_{n}) of monotone k-colorings of D. Now let (ν_{1}, …, ν_{n}) be an ordered n-tuple of monotone k-colorings of D. Assign to this tuple the ordered m-tuple (a_{1}, …, a_{m}), where a⃗_{i} = (ν_{1}(v_{i}), …, ν_{n}(v_{i})) for every i ∈ \overline{m}. It is easy to see that (a_{1}, …, a_{m}) ∈ 𝔐(D). As both of the above mappings are one-to-one, the required equation holds. □

From Theorem 3.1 and Lemma 3.5 we get the following theorem:

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

Finally, using Theorem 3.1, Lemma 3.4 and Lemma 3.5, we are able to prove the following theorem:

Theorem 3.3 For every k, m ∈ N and n ∈ N_{0},

α(k, m, n) = \frac{1}{m!} ∑_{i=1}^{m} |s(m, i)| β(k, i, n),

where

β(k, i, n) = Y_{i}(γ(k, 1, n), γ(k, 2, n), …, γ(k, i, n)), i ∈ \overline{m},

and

γ(k, j, n) = ∑_{D∈J_{j}^{c}}(−1)^{|ED|}η_{k}^{n}(D), j ∈ \overline{1, m}.

4 On monotone k-colorings of digraphs

It is easy to see that the following three propositions are true.

Proposition 4.1 If D and D′ are two isomorphic digraphs, then η(D) = η(D′).

Proposition 4.2 If D^{∗} is the condensation of a digraph D, then η(D^{∗}) = η(D).

Proposition 4.3 If C_{1}, C_{2}, …, C_{k} are all weak components of a digraph D, then

η(D) = η(C_{1}) · η(C_{1}) · · · · · η(C_{k}).

For every digraph D by D^{−1} denote the converse of D, namely, the digraph that is obtained from D when we change the orientation of every arc.

Proposition 4.4 For every digraph D, η(D^{−1}) = η(D).

Proof . Let D = (V, E) be a digraph, and f: V → \overline{0, k − 1} be a monotone k-coloring of D. Then the mapping f̂: V → \overline{0, k − 1}, where f̂(v) = k−1−f(v) for every v ∈ V, is a monotone k-coloring of D^{−1}. Obviously, the correspondence f ↦ f̂ defines a bijection between sets H(D) and H(D^{−1}), and consequently |H(D)| = |H(D^{−1})|, i.e., η(D^{−1}) = η(D). □

Let D be a digraph, and V_{1} ⊆ V D be a set of its vertices. Denote by D −V_{1} the subgraph <V D\V_{1} > of D induced by the set of vertices V D\V_{1}. Let v be a vertex of D. Denote by Out(v) the set of all vertices from V D\{v} which are accessible in D from v, and by In(v)

— the set of all vertices from V D\{v} from which in D the vertex v is accessible. Also let us make an agreement. Below we shall deal with vertex-weighted digraphs. Let (D, f_{D}) be a such digraph. For shortness sake, we denote by |v| the value f_{D}(v) (v ∈ V D).

Let D ∈ D_{m} be an arbitrary digraph. Suppose that we have k colors at our disposal. To find the number η(D) = η_{k}(D) we make use of the following General coloring procedure:

1. Find the condensation D^{∗} of the digraph D. Go to the next step.

2. If in D^{∗} there are two vertices u, v ∈ V D such that (u, v) ∈ ED, and there exists a path v_{1} = u, e_{1}, v_{2}, …, v_{n−1}, e_{n−1}, v_{n} = v (n ≥ 3), then delete the arc (u, v). Repeat this operation until such pairs of vertices exist. The obtained digraph design by D′. Go to the next step.

3. Take l := 0 and 𝔇_{0} := {D_{1}^{(0)}}, where D_{1}^{(0)} is the vertex-weighted digraph (D′, f_{D′}) such that |v| = \overline{0, k − 1} for every v ∈ V D′. Go to the next step.

4. If all digraphs from 𝔇_{l} = {D_{1}^{(l)}, D_{2}^{(l)}, …, D_{n_{l}}^{(l)}} are totally disconnected (they have no arcs), we go to step 6. Otherwise, let us take a digraph D_{i_{0}}^{(l)} (i_{0} ∈ \overline{n_{l}}) from 𝔇_{l} that is not totally disconnected. Let v ∈ D_{i_{0}}^{(l)}, and let ||v|| = p (here ||v|| means cardinality of the set |v|). Take p isomorphic copies

\overline{D}_{i_{0}}^{(l+1)}, \overline{D}_{i_{0}+1}^{(l+1)}, …, \overline{D}_{i_{0}+p−1}^{(l+1)}

of the vertex-weighted digraph D_{i_{0}}^{(l)} − v so that V \overline{D}_{i_{0}+j−1}^{(l+1)} ∩ V D_{i}^{(l)} = ∅ for every j ∈ \overline{p}

and i ∈ \overline{n_{l}}, and V \overline{D}_{i_{0}+j_{1}−1}^{(l+1)}∩V \overline{D}_{i_{0}+j_{2}−1}^{(l+1)} = ∅ for every j_{1}, j_{2} ∈ \overline{p}, j_{1} ≠ j_{2}. For every vertex u ∈ V (D_{i_{0}}^{(l)} −v), by u^{(j)} (j ∈ \overline{p}) denote the corresponding vertex of the vertex-weighted digraph \overline{D}_{i_{0}+j−1}^{(l+1)}; consequently, |u^{(j)}| = |u| for every j ∈ \overline{p}. For each t ∈ |v| = \overline{n_{1}, n_{2}}, perform the following operations. For every u ∈ Out(v), replace the mark |u^{(i_{0}+t−n_{1})}| of the vertex u^{(i_{0}+t−n_{1})} with interval |u^{(i_{0}+t−n_{1})}| ∩ \overline{t, k − 1}. Also, for every u ∈ In(v), replace the label |u^{(i_{0}+t−n_{1})}| of the vertex u^{(i_{0}+t−n_{1})} with the interval |u^{(i_{0}+t−n_{1})}| ∩ \overline{0, t}.

Let us denote the obtained vertex-weighted digraph by \overline{\overline{D}}_{(i_{0}+t−n_{1})}^{(l+1)}. Now put

D̂_{j}^{(l+1)} := \{ \begin{matrix}D_{j}^{(l)}, & j ∈ \overline{1, i_{0} − 1}, \\ \overline{\overline{D}}_{j}^{(l)}, & j ∈ \overline{i_{0}, i_{0} + p − 1}, \\ D_{j−p+1}^{(l)}, & j ∈ \overline{i_{0} + p, n_{l} + p − 1}. \end{matrix}

Increase the value of the parameter l by 1. Go to the next step.

5. If for some vertex v of a digraph D̂_{j}^{(l)} ∈ 𝔇_{l} (j ∈ \overline{n_{l}}) it holds that |v| = 1 and |V D̂_{j}^{(l)}| ≠ 1, then D̂_{j}^{(l)} := D̂_{j}^{(l)} − {v}. Repeat this operation until it is possible. Put D_{j}^{(l)} := D̂_{j}^{(l)} for every j ∈ \overline{n_{l}}. Go again to the forth step.

6. Calculate the value

η_{k}(D) = ∑_{i=1}^{n_{l}} ∏_{v∈D_{i}^{(l)}} ||v||,

and finish the procedure.

Let D be a digraph, and let |V D| = m. It is clear that η̂_{i}(D) = 0 for every i > m, and that

η_{k}(D) = ∑_{i=1}^{k} \binom{k}{i}η̂_{i}(D).  (4)

The last formula is very useful: knowing the finite set of numbers η̂_{i}(D), i ∈ \overline{m}, we can find η_{k}(D) for every k ∈ N. By applying binomial inversion [1] to (4) we get

η̂_{k}(D) = ∑_{i=1}^{k}(−1)^{k−i}\binom{k}{i}η_{i}(D).  (5)

Let us give formulas for η_{k}(D) in some special cases of digraph D. Example 1 By using General coloring procedure we can find, for example, the value η_{3} of the following digraph D:

[figure: =; =; =; \overline{0, 2}; \overline{0, 2}; \overline{0, 2}; \overline{0, 2}; \overline{0, 2}; \overline{0, 2}; =]

= [figure: 0; 0; 0; 0; \overline{0, 2}; +; \overline{0, 1}; \overline{0, 1}; \overline{0, 1}; \overline{0, 1}; \overline{1, 2}; +; \overline{0, 2}; \overline{0, 2}; \overline{0, 2}; \overline{0, 2}; 2; =]

= ^{3 · 1 · 1 + 4 · 2 · 2 + 10 · 3 · 1 = 49.}

In the above illustration we pass from the first digraph, digraph D, to the second one by using the first step of General coloring procedure. The third digraph is obtained by using the second step of the procedure. In the same way we can find the other values of the first row of the following table.

\begin{matrix}k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ η_{k}(D) & 1 & 10 & 49 & 168 & 462 & 1092 & 2310 & 4488 \\ η̂_{k}(D) & 1 & 8 & 22 & 28 & 17 & 4 & 0 & 0 \end{matrix}

Using (5) from the first row we get the second row of the table. Now from (4) we have

η_{k}(D) = \frac{1}{360} · (24k + 98k^{2} + 135k^{3} + 80k^{4} + 21k^{5} + 2k^{6}).

Note that we accidentally have obtained the sequence (\underline{A051947}). Example 2 Denote by P_{n} the digraph having the form of a directed path of the length n − 1 (with n vertices). It is easy to see that

η_{k}(P_{n}) = \binom{n + k − 1}{k − 1}.

Example 3 Denote by K⃗(m, n) the complete hedgehog with m vertices in its upper part and n vertices in its lower part. By using General coloring procedure and beginning with the unique vertex from the upper part of the digraph K⃗(1, n) we immediately have that

η_{k}[K⃗(1, n)] = 1^{n} + 2^{n} + ⋯ + k^{n}.  (6)

Now let us generalize formula (6).

Proposition 4.5 For every k, m, n ∈ N,

η_{k}[K⃗(m, n)] = ∑_{i=1}^{k}[(k + 1 − i)^{n} − (k − i)^{n}] · i^{m}  (7)

or

η_{k}[K⃗(m, n)] = ∑_{i=1}^{k}[(k + 1 − i)^{m} − (k − i)^{m}] · i^{n}.

Proof . Let J be a connected hedgehog. As hedgehog J is weekly connected, V_{1}(J) is the upper part, and V_{2}(J) — the lower part of J. Denote by Φ_{i}(J), i ∈ \overline{2}, the set of all functions f: V_{i}(J) → \overline{0, k − 1}. Then

η(J) = ∑_{f∈Φ_{2}(J)} ∏_{v∈V_{1}(J)}(min{f(u) | u ∈ Out(v)} + 1)  (8)

or

η(J) = ∑_{f∈Φ_{1}(J)} ∏_{v∈V_{2}(J)}(k − max{f(u) | u ∈ In(v)}).

Because K⃗(m, n) ∈ J_{m+n}^{c} we can make, for example, use of the first formula, and calculate the number of functions f ∈ Φ_{2}(K⃗(m, n)) satisfying the condition

min{f(u) | u ∈ V_{2}(K⃗(m, n))} = i − 1.

For this purpose we have to find the number of n-tuples of the numbers i − 1, i, …, k − 1 containing the number i − 1, and by using the formula (8) we get the formula from the proposition.

The second equality of the proposition follows immediately from (7) and Proposition 4.4. □

5 On the number of m-multiantichains of k-bounded multisets on an n-set

The notion of an m-antichain of multisets on a set can be naturally generalized to the notion of an m-multiantichain of multisets on a set in the following way. By an m-multiantichain M of multisets on a set S we mean an m-multiset M of multisets on S such that a ⊈ b or a = b for every a, b ∈ M. An m-multiantichain of k-bounded multisets on an n-set S is called a (k, m, n)-multiantichain on S.

Let us denote by A^{∗}(k, m, n) the set of all (k, m, n)-multiantichains on S, and put

α^{∗}(k, m, n) = |A^{∗}(k, m, n)|.

Introduce the numbers

t(m, i) = ∑_{l=i}^{m} L′(m, l) |s(l, i)|, i ∈ \overline{m},

where L′(m, l) are unsigned Lah numbers [1], or, as they are also called, Stirling numbers of the third kind; let us call the numbers t(m, i) unsigned Lah-Stirling numbers of the first kind. The following table gives these numbers for small values of m and i (\underline{A079638}):

t(m, i) i = 1 2  3  4  5  6  7
m = 1 1
2 3  1
3 14  9  1
4 90  83  18  1
5 744  870  275  30  1
6 7560 10474 4275 685  45  1
7 91440 143892 70924 14805 1435 63  1

Now let us prove the following assertion:

Theorem 5.1 α^{∗}(k, m, n) = \frac{1}{m!} ∑_{i=1}^{m} t(m, i) β(k, i, n).

Proof. As \binom{m−1}{l−1} is the number of compositions of the number m into l parts [1], we have

α^{∗}(k, m, n) = ∑_{l=1}^{m} \binom{m − 1}{l − 1}α(k, l, n) =

= \frac{1}{m!} ∑_{l=1}^{m} \frac{m!}{l!}\binom{m − 1}{l − 1}α⃗(k, l, n) = \frac{1}{m!} ∑_{l=1}^{m} L′(m, l) α⃗(k, l, n).

Now, applying formula (3) and changing the order of the summation we get

α^{∗}(k, m, n) = \frac{1}{m!} ∑_{l=1}^{m} L′(m, l) ∑_{i=1}^{l} |s(l, i)| β(k, i, n) = \frac{1}{m!} ∑_{i=1}^{m} t(m, i) β(k, i, n). □

6 Explicit formulas for small values of m

Let us calculate α(k, m, n) and α^{∗}(k, m, n) for k ≥ 1, 1 ≤ m ≤ 4 and n ≥ 0. In the table below the first column gives unlabeled (weakly) connected hedgehogs with less than or equal to 4 vertices, and the second column gives the number ι(J) of isomorphic (labeled) digraphs to the corresponding hedgehog J. (For example there are 4 unlabeled and 38 labeled connected hedgehogs on 4 vertices. Numbers of unlabeled and labeled connected hedgehogs on m vertices are given under \underline{A007776} and \underline{A002031}.) By using General coloring procedure, as in Example 1, one could fill the third column that gives the corresponding polynomials η_{k}(J_{i}), i ∈ \overline{8} (in the case of J_{i}, i ∈ \overline{2, 6} we can make use of (6), and in the case of J_{8} we can make use of Proposition 4.5). Also let us note that from Proposition 4.4 we have that η_{k}(J_{3}) = η_{k}(J_{4}) and η_{k}(J_{5}) = η_{k}(J_{6}) for every k ∈ N. The last column of the table gives the corresponding reference to [11].

m i  J_{i} ι(J_{i})  p_{i} = p_{i}(k) = η_{k}(J_{i})  OEIS ID
1 1 1  k
[figure: 2; 2; 2; (k^{2} + k)/2; \underline{A000217}]
[figure: 3; 3; 3; (2k^{3} + 3k^{2} + k)/6; \underline{A000330}]
[figure: 4; 3; (2k^{3} + 3k^{2} + k)/6; \underline{A000330}]
[figure: 4; 5; 4; (k^{4} + 2k^{3} + k^{2})/4; \underline{A000537}]
[figure: 6; 4; (k^{4} + 2k^{3} + k^{2})/4; \underline{A000537}]
[figure: 7; 24; (5k^{4} + 10k^{3} + 7k^{2} + 2k)/24; \underline{A006322}]
[figure: 8; 6; (k^{4} + 2k^{3} + 2k^{2} + k)/6; \underline{A006325}]

By using the above table and the third formula from Theorem 3.3, we get

γ(k, 1, n) = p_{1}^{n}, γ(k, 2, n) = −2p_{2}^{n}, γ(k, 3, n) = 6p_{3}^{n}, γ(k, 4, n) = −8p_{5}^{n} − 24p_{7}^{n} + 6p_{8}^{n}.

Replacing x_{i} by γ(k, i, n) (i ∈ \overline{4}) in Bell polynomials Y_{j}(x_{1}, …, x_{j}), j ∈ \overline{4}, [10]:

\begin{matrix}Y_{1}(x_{1}) = x_{1}, Y_{2}(x_{1}, x_{2}) = x_{1}^{2} + x_{2}, Y_{3}(x_{1}, x_{2}, x_{3}) = x_{1}^{3} + 3x_{1}x_{2} + x_{3}, \\ Y_{4}(x_{1}, x_{2}, x_{3}, x_{4}) = x_{1}^{4} + 6x_{1}^{2}x_{2} + 4x_{1}x_{3} + 3x_{2}^{2} + x_{4}, \end{matrix}

and using the second formula from Theorem 3.3, we obtain the expressions:

\begin{matrix}β(k, 1, n) = q_{1}^{n}, β(k, 2, n) = q_{3}^{n} − 2q_{2}^{n}, β(k, 3, n) = q_{6}^{n} − 6q_{5}^{n} + 6q_{4}^{n}, \\ β(k, 4, n) = q_{12}^{n} − 12q_{11}^{n} + 24q_{10}^{n} + 4q_{9}^{n} − 24q_{8}^{n} + 6q_{7}^{n}, \end{matrix}

where

\begin{matrix}q_{1} = p_{1}, q_{2} = p_{2}, q_{3} = p_{1}^{2}, q_{4} = p_{3}, q_{5} = p_{1}p_{2}, q_{6} = p_{1}^{3}, q_{7} = p_{8}, \\ q_{8} = p_{7}, q_{9} = p_{5}, q_{10} = p_{1}p_{3}, q_{11} = p_{1}^{2}p_{2}, q_{12} = p_{1}^{4} \end{matrix}

(it is not difficult to see that q_{i} < q_{j} for every i, j ∈ \overline{12}, i ≠ j, and every k ≥ 4). By using the first formula from Theorem 3.3, we finally have that

α(k, 1, n) = q_{1}^{n},
α(k, 2, n) = \frac{1}{2!} (q_{1}^{n} − 2q_{2}^{n} + q_{3}^{n}),
α(k, 3, n) = \frac{1}{3!} (2q_{1}^{n} − 6q_{2}^{n} + 3q_{3}^{n} + 6q_{4}^{n} − 6q_{5}^{n} + q_{6}^{n}),
α(k, 4, n) = \frac{1}{4!} (6q_{1}^{n} − 22q_{2}^{n} + 11q_{3}^{n} + 36q_{4}^{n} − 36q_{5}^{n} + 6q_{6}^{n}+
+ 6q_{7}^{n} − 24q_{8}^{n} + 4q_{9}^{n} + 24q_{10}^{n} − 12q_{11}^{n} + q_{12}^{n}).

Similarly, using Theorem 5.1 and the unsigned Lah-Stirling numbers of the first kind from the table given in Section 5, we get

α^{∗}(k, 1, n) = q_{1}^{n},
α^{∗}(k, 2, n) = \frac{1}{2!} (3q_{1}^{n} − 2q_{2}^{n} + q_{3}^{n}),
α^{∗}(k, 2, n) = \frac{1}{3!} (14q_{1}^{n} − 18q_{2}^{n} + 9q_{3}^{n} + 6q_{4}^{n} − 6q_{5}^{n} + q_{6}^{n}),
α^{∗}(k, 4, n) = \frac{1}{4!} (90q_{1}^{n} − 166q_{2}^{n} + 83q_{3}^{n} + 108q_{4}^{n} − 108q_{5}^{n} + 18q_{6}^{n}+
+ 6q_{7}^{n} − 24q_{8}^{n} + 4q_{9}^{n} + 24q_{10}^{n} − 12q_{11}^{n} + q_{12}^{n}).

Example 4 Let us give the values of q_{i} (i ∈ \overline{12}, k ∈ \overline{10}) in the following table:

k = 1  2  3  4  5  6  7  8  9  10
q_{1}  1  2  3  4  5  6  7  8  9  10
q_{2}  1  3  6 10 15 21 28 36 45  55
q_{3}  1  4  9 16 25 36 49 64 81 100
q_{4}  1  5 14 30 55 91 140 204 285 385
q_{5}  1  6 18 40 75 126 196 288 405 550
q_{6}  1  8 27 64 125 216 343 512 729 1000
q_{7}  1  7 26 70 155 301 532 876 1365 2035
q_{8}  1  8 31 85 190 371 658 1086 1695 2530
q_{9}  1  9 36 100 225 441 784 1296 2025 3025
q_{10}  1 10 42 120 275 546 980 1632 2565 3850
q_{11}  1 12 54 160 375 756 1372 2304 3645 5500
q_{12}  1 16 81 256 625 1296 2401 4096 6561 10000

Now using this table and the above given formulas, we can calculate the numbers α(k, m, n) and α^{∗}(k, m, n) for m ∈ \overline{4}, k ∈ \overline{10}, and for every n. For example, using the forth column of this table, we immediately get the corresponding expressions for α(4, m, n) (m ∈ \overline{4}):

α(4, 1, n) = 4^{n},
α(4, 2, n) = \frac{1}{2!}(4^{n} − 2 · 10^{n} + 16^{n}),
α(4, 3, n) = \frac{1}{3!}(2 · 4^{n} − 6 · 10^{n} + 3 · 16^{n} + 6 · 30^{n} − 6 · 40^{n} + 64^{n}),
α(4, 4, n) = \frac{1}{4!}(6 · 4^{n} − 22 · 10^{n} + 11 · 16^{n} + 36 · 30^{n} − 36 · 40^{n} + 6 · 64^{n}+
+ 6 · 70^{n} − 24 · 85^{n} + 4 · 100^{n} + 24 · 120^{n} − 12 · 160^{n} + 256^{n}).

In this way, using the isomorphism testing program Nauty [12] we can derive the expressions for α(k, m, n) and α^{∗}(k, m, n) at least up to m = 16. For k = 2 and k = 3 the corresponding expressions can be found in [11] under the following IDs:

k = 2, m = 2  2, 3  2, 4  3, 2  3, 3  3, 4
α(k, m, n)  \underline{A016269} \underline{A047707} \underline{A051112} \underline{A084874} \underline{A084875} \underline{A084876}
α^{∗}(k, m, n) \underline{A084869} \underline{A084870} \underline{A084871} \underline{A084879} \underline{A084880} \underline{A084881}

Note that the numbers α(2, m, n) give the numbers of all “ordinary” (not consisting of multisets, but consisting of sets) m-antichains on an n-set. In [8] only the case of the numbers α(2, m, n) is considered, and the expressions for these numbers, when m ∈ \overline{1, 7} and n ∈ N, are given. These expressions, and the expressions for α(2, m, n), when 8 ≤ m ≤ 10 and n ∈ N, together with their values for small values of n are presented on site [11] (\underline{A016269}, \underline{A047707}, \underline{A051112}, \underline{A051113}, \underline{A051114}, \underline{A051115}, \underline{A051116}, \underline{A051117}, \underline{A051118}).

References

[1] M. Aigner, Combinatorial Theory, Springer-Verlag, 1979.

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

[3] G. Birkhoff, Lattice Theory, Providence, Rhode Island, 1967.

[4] N. M. Riviere, Recursive formulas on free distributive lattices, J. Combin. Theory 5 (1968), 229–234.

[5] D. Cvetković, The number of antichains of finite power sets, Publ. Inst. Math. (Beograd) (N.S.) 13 (27) (1972), 5–9.

[6] J. L. Arocha, Anticadenas en conjuntos ordenados, An. Inst. Mat. Univ. Nac. Autonoma Mexico 27 (1987), 1–21.

[7] J. L. Arocha, The number of antichains of the length 5 and 6 (in Russian), VINITI 06.04.82. Reg. #1631-82 Dep., 1982.

[8] G. Kilibarda and V. Jovović, On the number of monotone Boolean functions with fixed number of lower units (in Russian), Intellektualnye sistemy (Moscow) 7 (1–4) (2003), 193–217.

[9] F. Harary, Graph Theory, Addison-Wesley, 1969.

[10] J. Riordan, Combinatorial Identities, John Wiley & Sons, 1968.

[11] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences,

     http://www.research.att.com/~njas/sequences/

[12] B. McKay, Program Nauty for computing automorphism groups of graphs,

     http://cs.anu.edu.au/people/bdm/nauty

2000 Mathematics Subject Classification: Primary 68R05; Secondary 68R10, 05A10, 05A15, 11B73, 11B83. Keywords: Exact enumeration, antichain, multiset, digraph, bipartite graph, monotone coloring of a digraph, monotone Boolean function.

(Concerned with sequences \underline{A016269}, \underline{A047707}, \underline{A051112}, \underline{A051113}, \underline{A051114}, \underline{A051115}, \underline{A051116}, \underline{A051117}, \underline{A051118}, \underline{A084869}, \underline{A084870}, \underline{A084871}, \underline{A084872}, \underline{A084873}, \underline{A084874}, \underline{A084875}, \underline{A084876}, \underline{A084877}, \underline{A084878}, \underline{A084879}, \underline{A084880}, \underline{A084881}, \underline{A084882}, \underline{A084883}, \underline{A085461}, \underline{A085462}, \underline{A085463}, \underline{A085464}, \underline{A085465}.)

Received October 14 2003; revised version received January 28 2004. Published in Journal of Integer Sequences, February 17 2004.

Return to Journal of Integer Sequences home page.