\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm
{\LARGE\bf Antichains of Multisets}
\vskip 1cm
\large
Goran Kilibarda and Vladeta Jovovi\'{c}\\
Faculty of Technology and Metallurgy\\
University of Belgrade\\
Karnegijeva 4\\
11001 Belgrade\\
Serbia and Montenegro\\
\href{mailto:vladeta@EUnet.yu}{\tt gkilibar@EUnet.yu}\\
\href{mailto:gkilibar@EUnet.yu}{\tt vladeta@EUnet.yu}\\
\end{center}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]

\font\got = eufm10 scaled 1200
\font\gots = eufm7 scaled 1200

\def\bk#1{\mbox{\boldmath $#1$}}
\def\bks#1{\mbox{\small\boldmath $#1$}}

\def\gt#1{\mbox{\got #1}}
\def\gts#1{{\mbox{\gots #1}}}
\def\cl#1{{\cal #1}}
\def\ov#1{\overline{#1}}

\newcommand{\hyplnk}[2]{\mbox{\hyperlink{#1}{\textcolor{green}{#2}}}}
\newcommand{\seqnumw}[2]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{#2}}

\makeatletter

\vskip .3in

\begin{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 \hbox{multiantichains} is also considered. As an illustration the corresponding explicit formulas are
  given for the case when $1\le m\le4$, $k\ge1$ and $n\ge0$.
\end{abstract}




\section{Introduction}

By an $m$-antichain (an antichain or a Sperner family of the length $m$) on an $n$-set $S$ we mean a family
${\cal A}$
of $m$ subsets of $S$ satisfying the condition
$A_1\not\subseteq A_2$
for every
$A_1,A_2\in{\cal A}$, $A_1\ne A_2$.
Denote by
$\alpha(m,n)$
the number of all $m$-antichains on an $n$-set. From Sperner's lemma \cite{Aig} it follows that
$\alpha(m,n)=0$
for all
$m>\binom{n}{\lfloor n/2\rfloor}$.
Thus, knowing the numbers
$\alpha(m,n)$, $0\le m\le\binom{n}{\lfloor n/2\rfloor}$,
we can find the number
$\alpha(n)$
of all antichains on an $n$-set. The problem of finding numbers
$\alpha(n)$
has a long history, and it is known as the Dedekind problem. It was formulated by R.\ Dedekind \cite{Ded} as far back as
1897 as the problem of determining the number of elements in a free distributive lattice
$FD(n)$
on $n$ generators (see also \cite{Bir}). 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
$\alpha(m,n)$,
when
$1\le m\le3$,
and $n$ is an arbitrary nonnegative integer, were obtained by N.M.~Riviere \cite{Riv}. D.\ Cvetkovi\'c \cite{Cve} solved
the case
$m=4$
basically by computer generation. A further contribution to the solving of the problem was made by J.L.~Arocha
\cite{Aro1,Aro2}, who gave in \cite{Aro2} the corresponding formulas for the case
$m=5,6$.

Kilibarda and Jovovi\'{c} in \cite{KiJ} gave a general procedure for calculating numbers
$\alpha(m,n)$,
which made it possible to find the corresponding explicit formulas for the case when
$1\le m\le10$
and $n$ is arbitrary. There it also is shown that the problem of finding numbers $\alpha(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
$\alpha(m,n)$.
In fact, here we consider the problem of finding the number
$\alpha(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 \cite{KiJ}. The formula obtained
in this paper, a special case of which is the formula from \cite{KiJ} for finding numbers
$\alpha(m,n)$,
has the same structure up to the type of colorings. Thus the generalization of the problem discussed in \cite{KiJ}
affects only the complexity of determining the number of respective colorings.

Note that one of the interpretations of the number
$\alpha(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
$\alpha^\ast(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
$\alpha(k,m,n)$ and $\alpha^\ast(k,m,n)$, $k\in\mbox{\bf N}$, $1\le m\le 4$, $n\in\mbox{\bf N}_0$.




\section{Basic notions}

Let $X$ be a set. Denote by
$|X|$
the cardinality of the set $X$, by
$\mbox{\got B}(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\in\mbox{\bf Z}$, $m_1\le m_2$, by $\overline{m_1,m_2}$
denote the integer interval
$\{m_1,m_1+1,\dots,m_2\}$.
Also, by
$\overline{n}$
denote the set
$\{1,\dots,n\}$
for every
$n\in\mbox{\bf N}$,
and let
$\mbox{\bf N}_0=\mbox{\bf N}\cup\{0\}$.
By
$\mbox{\bf pr}_i(a)$, $i\in\overline{n}$,
denote the $i$-th component of an $n$-tuple $a$.

Let
$(a_1,\dots,a_n)$ and $(b_1,\dots,b_n)$
be two $n$-tuples from the set
$\left(\,\overline{0,k-1}\,\right)^n$.
We write
$(a_1,\dots,a_n)\le(b_1,\dots,b_n)$ if $a_i\le b_i$
for every
$i\in\overline{n}$.
If, in addition, there exists
$i_0\in\overline{n}$
such that
$a_{i_0}<b_{i_0}$,
we write
$(a_1,\dots,a_n)<(b_1,\dots,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 \cite{Har}.

Following \cite{Aig}, by a {\it multiset\/} on a set $S$ we mean an ordered pair consisting of $S$ and a mapping
$f\!: S\to\mbox{\bf N}_0$;
the value
$f(s)$
is called {\it multiplicity\/} of
$s\in S$ in $(S,f)$.
By {\it cardinality\/} of a multiset
$\bk{a}=(S,f)$
we mean the number
$|\bk{a}|=\sum_{s\in S}f(s)$.
A multiset
$\bk{a}$
is called an $m$-{\it multiset} if
$|\bk{a}|=m$.
Let
$\bk{a}=(S,f)$ and $\bk{b}=(S,g)$
be two multisets. We write
$\bk{a}\subseteq\bk{b}$
if
$f(s)\le g(s)$
for every
$s\in S$.

A multiset
$\bk{a}=(S,f)$
is called
{\it $k$-bounded\/} ($k\in\mbox{\bf N}$) if $f(s)\le k-1$
for every
$s\in 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
${\cal M}_k(S)$
the set of all $k$-bounded multisets on $S$.

Let
${\cal M}$
be a set of multisets on $S$. Let us call it an {\it antichain of multisets\/} on $S$ if
$\bk{a}\not\subseteq\bk{b}$
for every
$\bk{a},\bk{b}\in{\cal M}$, $\bk{a}\ne\bk{b}$. If  $|{\cal M}|=m$ ($m\in\mbox{\bf N}_0$),
then we also call
${\cal M}$
an $m$-{\it 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,\dots,s_n\}$,
and define on $S$ a linear order $\le$ in the following way:
$s_1\le s_2\le\dots\le s_n$.
Every multiset considered here will be a multiset on $S$. In what follows, instead of the notation
${\cal M}_k(S)$
we use
${\cal M}_k$.
Obviously, every multiset
$\bk{a}=(S,f)$
can be given by the $n$-tuple
$\vec{\bk{a}}=(f(s_1),\dots,f(s_n))$.

Let us denote by
${\cal A}(k,m,n)$
the set of all $m$-antichains of $k$-bounded multisets on $S$.
Also, let
$\alpha(k,m,n)=|{\cal A}(k,m,n)|$.
Our goal is to find the numbers
$\alpha(k,m,n)$.
Let
${\cal M}\subseteq{\cal M}_k$.
It is easy to see that
${\cal M}\in{\cal A}(k,m,n)$ iff $\vec{\bk{a}}\not\le\vec{\bk{b}}$
for every
$\bk{a},\bk{b}\in{\cal M}$, $\bk{a}\ne\bk{b}$.

We denote the set of vertices of a digraph $G$ by
$VG$,
and the set of its arcs --- by
$EG$.

Let
$G=(V,E)$
be a digraph, and let
$k\in\mbox{\bf N}$.
By {\it $k$-coloring\/} of $G$ we mean a mapping
$\nu:V\to\overline{0,k-1}$.
We say that a vertex from the set
$\nu^{-1}(i)$ ($i\in\overline{0,k-1}$)
is $i$-{\it colored\/}. If a $k$-coloring
$\nu$
is a mapping onto we call it an {\it exact $k$-coloring\/}. A $k$-coloring
$\nu$
of a digraph is called monotone if
$\nu(u)\le\nu(v)$
for every
$(u,v)\in E$.
By
$H_k(D)$ ($\hat{H}_k(D)$)
denote the set of all monotone $k$-colorings (exact $k$-colorings) of a digraph $D$, and let
$\eta_k(D)=|H_k(D)|$ ($\hat\eta_k(D)=|\hat{H}_k(D)|$);
in the following, $k$ is fixed, and because of
that, instead of
$H_k(D)$ ($\hat{H}_k(D)$) and $\eta_k(D)$ ($\hat\eta_k(D)$)
we usually write
$H(D)$ ($\hat{H}(D)$) and $\eta(D)$ ($\hat\eta(D)$),
respectively.




\section{On the number of $m$-antichains of $k$-bounded\\ multisets on an $n$-set}


Let us fix an infinite countable set
$V_{\infty}=\{v_1,v_2,\dots\}$ such that $V_{\infty}\cap S=\emptyset$.
Put
$V_m=\{v_1,v_2,\dots,v_m\}$
for every natural number $m$. Denote by
${\cal 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
${\cal D}_m$.

Let
$D\in{\cal D}_m$.
Let us denote by
$F(D)$
the set of all functions
$f\!:V_m\to{\cal M}_k$
satisfying the following condition: if
$(v,v')\in ED$, then $f(v)\subseteq f(v')$.
Assign to every function
$f\in F(D)$
the $m$-tuple
$\vec{\cal M}(f)=(\bk{a}_1,\dots,\bk{a}_m)$
of multisets on $S$ such that
$\bk{a}_i=f(v_i)$
for every
$i\in\overline{m}$.
Let
$\mbox{\got M}(D)=\{\vec{\cal M}(f)\,|\,f\in F(D)\}$ and ${\lambda}(D)=|F(D)|=|\mbox{\got M}(D)|$.

Let us denote by
$\vec{\cal A}(k,m,n)$
the set of all $m$-tuples
$(\bk{a}_1,\dots,\bk{a}_m)$
of $k$-bounded multisets on $S$ satisfying the condition that the set consisting of these multisets is an $m$-antichain. Let
$\vec\alpha(k,m,n)=|\vec{\cal A}(k,m,n)|$.
Then it is clear that
\begin{equation}
  \vec\alpha(k,m,n)=m!\,\alpha(k,m,n).\hypertarget{first}{}
\end{equation}

Denote by
${\cal J}_m$
the set of all digraphs from
${\cal D}_m$
in which there is no directed path of the length
$\ge 2$.
Let us call every digraph from
${\cal J}_m$
a {\it hedgehog\/}. Denote by
$V_1(J)$ ($V_2(J)$)
the set of all vertices of a hedgehog
$J\in{\cal J}_m$
for which the input (output) degree is equal to 0. It is clear that
$V_0(J)=V_1(J)\cap V_2(J)$
is the set of all isolated vertices of the hedgehog $J$. The set
$V_1(J)\backslash V_0(J)$ ($V_2(J)\backslash V_0(J)$)
is called the {\it upper\/} ({\it lower\/}) part of $J$.

The proof of the following lemma can be found in \cite{KiJ}. Here we give another proof of this assertion.


\begin{lemma}\hypertarget{lmm1}{}
  $\displaystyle\sum_{D\in{\cal J}_m}(-1)^{|ED|}=(-1)^{m-1}$.
\end{lemma}

{\it Proof\/}. Put
$H_{m}(x)=\sum_{i=0}^{s}h_{m,i}\ x^{i}$,
where
$s=\left\lfloor\frac{m^{2}}{4}\right\rfloor$, 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)=\sum_{k=0}^{m}\binom{m}{k}((1+x)^{m-k}-1)^{k}$ (\seqnum{A052296}).
Henceforth we have that
$\sum_{D\in J_{m}}(-1)^{|ED|}=H_{m}(-1)=(-1)^{m-1}$.\,$\Box$

Note that
$H_{m}(1)=\sum_{k=0}^{m}\binom{m}{k}(2^{m-k}-1)^{k}$
is the number of hedgehogs with $m$ vertices (\seqnum{A001831}).

Also, denote by
$\mbox{\got M}^{(i)}(D)$, $i\in\overline{m}$,
the set of all $m$-tuples from
$\mbox{\got M}(D)$
containing exactly $i$ different multisets. It is clear that
\begin{equation}
  \lambda(D)=\displaystyle\sum_{i=1}^m|\mbox{\got M}^{(i)}(D)|.\hypertarget{second}{}
\end{equation}
Let
$s(n,k)$ and $S(n,k)$
be Stirling numbers of the first and second kind respectively \cite{Aig}.


\begin{lemma}\hypertarget{lmm2}{}
  For every $i\in\ov{m}$,
  $$
  \sum_{D\in\cl{J}_m}(-1)^{|ED|}|\gt{M}^{(i)}(D)|=(-1)^{m-i}\,S(m,i)\,\vec\alpha(k,i,n).
  $$
\end{lemma}

{\it Proof\/}.\ First, let us introduce families:
$\gt{P}_j=\{\cl{M}\subseteq\cl{M}_k\,|\,|\cl{M}|=j\}$ ($j\in\ov{m}$),
$\gt{P}'_1=\emptyset$,
$\gt{P}'_j=\{\cl{M}\in\gt{P}_j\,|\,(\exists\,\bk{a},\bk{b}\in\cl{M})\;\bk{a}\subseteq\bk{b}\land\bk{a}\ne\bk{b}\}$
($j\in\overline{2,m}$),
$\gt{P}''_j=\gt{P}_j\backslash\gt{P}'_j$ ($j\in\ov{m}$).
It is clear that
$\gt{P}''_j=\cl{A}(k,j,n)$
for every
$j\in\ov{m}$.

\smallskip
Fix some
$i\in\ov{m}$,
and let
$\cl{M}\in\gt{P}_i$.
Let
$F(\cl{M})=\{f:V_m\to\cl{M}_k\,|\,f(V_m)=\cl{M}\}$ and $F(D,\cl{M})=F(\cl{M})\cap F(D)$
for every
$D\in\cl{D}_m$.
Also, by
$\cl{J}_m(\cl{M})$
denote the set of all vertex-weighted digraphs
$(D,f)$
such that
$D\in\cl{J}_m$ and $f\in F(D,\cl{M})$.
Let
$V_m(\bk{a};D,f)=\{v\in V_m\,|\,f(v)=\bk{a}\}$
for every
$(D,f)\in\cl{J}_m(\cl{M})$ and $\bk{a}\in\cl{M}$.
Obviously the following equation holds:
$$
\begin{array}{lcl}
\sigma
& = & \displaystyle\sum_{D\in\cl{J}_m}(-1)^{|ED|}|\gt{M}^{(i)}(D)|=
      \sum_{D\in\cl{J}_m}(-1)^{|ED|}\sum_{\cl{M}\in\gts{P}_i}
      |F(D,\cl{M})|=\\
& = & \displaystyle\sum_{\cl{M}\in\gts{P}_i}
      \sum_{D\in\cl{J}_m}(-1)^{|ED|}|F(D,\cl{M})|=
      \sum_{\cl{M}\in\gts{P}_i}
      \sum_{(D,f)\in\cl{J}_m(\cl{M})}(-1)^{|ED|}=\\
& = & \displaystyle\sum_{\cl{M}\in{\mbox{\gots P}}'_i}
      \sum_{(D,f)\in\cl{J}_m(\cl{M})}(-1)^{|ED|}+
      \sum_{\cl{M}\in\gts{P}''_i}
      \sum_{(D,f)\in\cl{J}_m(\cl{M})}(-1)^{|ED|}.
\end{array}
$$
In the above expression denote the first sum after the last sign $=$ by
$\sigma_1$,
and the second one --- by
$\sigma_2$.
Note that if
$i=1$, then $\sigma_1=0$,
and consequently
$\sigma=0+\sigma_2=\sigma_2$.
Let us show that the equation
$\sigma=\sigma_2$
holds for every
$i\in\ov{m}$.

Take some
$\cl{M}\in\gt{P}'_i$, $i\in\ov{2,m}$.
Then there exists
$\bk{a}',\bk{b}'\in\cl{M}$, $\bk{a}'\ne\bk{b}'$,
so that
$\bk{a}'\subseteq\bk{b}'$.
Let
$\bk{a}$ and $\bk{b}$
be respectively the minimal element and the maximal element of a chain in
$\cl{M}$
containing
$\bk{a}'$ and $\bk{b}'$.
It is clear that for every
$(D,f)\in{\cal J}_m({\cal M})$
the sets
$V_m^{(1)}(\bk{a};D,f)=V_1(D)\cap V_m(\bk{a};D,f)$
and
$V_m^{(2)}(\bk{b};D,f)=V_2(D)\cap V_m(\bk{b};D,f)$
are nonempty. Break the class
$\cl{J}_m(\cl{M})$
into subclasses
$[\cl{J}_m(\cl{M})]_j$, $j=1,\dots,c_0$,
so that two digraphs
$(D',f'),(D'',f'')$
belong to the same subclass
$[\cl{J}_m(\cl{M})]_j$
iff
$f'=f''=f$, $V_m^{(1)}(\bk{a};D',f')=V_m^{(1)}(\bk{a};D'',f'')$, $V_m^{(2)}(\bk{b};D',f')=V_m^{(2)}(\bk{b};D'',f'')$
and
$(V_m,ED'\backslash E_0)=(V_m,ED''\backslash E_0)=\hat{D}_j$,
where
$E_0=V_m^{(1)}(\bk{a};D',f)\times V_m^{(2)}(\bk{b};D',f)$.
Now we have
$$
\begin{array}{l}
  \sigma_1(\cl{M})=\displaystyle\sum_{(D,f)\in\cl{J}_m(\cl{M})}(-1)^{|ED|}=
  \sum_{j=1}^{c_0}\sum_{(D,f)\in[\cl{J}_m(\cl{M})]_j}(-1)^{|ED|}=\\
  \hskip4cm=\displaystyle\sum_{j=1}^{c_0}(-1)^{|E\hat{D}_j|}
  \sum_{E'\subseteq E_0}(-1)^{|E'|}=0.
\end{array}
$$
As
$\sigma_1(\cl{M})=0$
for every
$\cl{M}\in\gt{P}'_i$,
we have again that
$\sigma_1=0$.

Now let
$\cl{M}\in\gt{P}''_i$, $i\in\ov{m}$.
Note that
$\bk{a}\not\subseteq\bk{b}$
for every two different
$\bk{a},\bk{b}\in\cl{M}$.
Break the class
$\cl{J}_m(\cl{M})$
into subclasses
$[\cl{J}_m(\cl{M})]_f$, $f\in F(\cl{M})$
so that the digraph
$(D',f')\in\cl{J}_m(\cl{M})$
belongs to the subclass
$[\cl{J}_m(\cl{M})]_f$
iff
$f'=f$.
Then we have
$$
\sigma=\sigma_2=\sum_{\cl{M}\in\gts{P}''_i}\sum_{f\in F(\cl{M})}\sum_{(D,f)\in[\cl{J}_m(\cl{M})]_f}(-1)^{|ED|}.
$$

Let us fix
$\cl{M}=\{\bk{a}_1,\dots,\bk{a}_i\}\in\gt{P}''_i$ and $f\in F(\cl{M})$,
and take some
$(D,f)\in[\cl{J}_m(\cl{M})]_f$.
Put
$W_j=V_m(\bk{a}_j;D,f)$, $D_j'=(W_j,ED\cap W_j^2)$ and $m_j=|W_j|$
for every
$j\in\ov{i}$.
Note that
$ED\cap(W_{j_1}\times W_{j_2})=\emptyset$
for every
$j_1,j_2\in\ov{i}$, $j_1\ne j_2$. By $D_j$, $j\in\ov{i}$,
denote the digraph from
$\cl{J}_{m_j}$
that is isomorphic to
$D_j'$.
It is clear that when
$(D,f)$
passes completely the set
$[\cl{J}_m(\cl{M})]_f$
then the digraph
$D_j$
for every
$j\in\overline{i}$
passes the whole set
$\cl{J}_{m_j}$.
Then using \hyplnk{lmm1}{Lemma 3.1} we have
$$
\begin{array}{l}
  \displaystyle\sum_{(D,f)\in[\cl{J}_m(\cl{M})]_{f}}(-1)^{|ED|}=
  \sum_{D_1\in\cl{J}_{m_1}}\dots
  \sum_{D_i\in\cl{J}_{m_i}}(-1)^{|ED_1|}\dots(-1)^{|ED_i|}=\\
  \hskip1cm=\displaystyle\sum_{D_1\in\cl{J}_{m_1}}\dots
  \sum_{D_{i-1}\in\cl{J}_{m_{i-1}}}(-1)^{|ED_1|}\dots(-1)^{|ED_{i-1}|}
  \sum_{D_i\in\cl{J}_{m_i}}(-1)^{|ED_i|}=\\
  \hskip1cm=(-1)^{m_i-1}\displaystyle\sum_{D_1\in\cl{J}_{m_1}}\dots
  \sum_{D_{i-1}\in\cl{J}_{m_{i-1}}}(-1)^{|ED_1|}\dots(-1)^{|ED_{i-1}|}=\dots=\\
  \hskip1cm=(-1)^{m_1-1}\dots(-1)^{m_i-1}=(-1)^{m-i}.
\end{array}
$$
Note that
$|\gt{P}_i''|=\alpha(k,i,n)$ and $|F(\cl{M})|=i!S(m,i)$.
Finally, using (1) we get
$$
\begin{array}{lcl}
\sigma & = & \displaystyle\sum_{D\in\cl{J}_m}(-1)^{|ED|}|\gt{M}^{(i)}(D)|=(-1)^{m-i}\sum_{\cl{M}\in\gts{B}''_i}
             \sum_{f\in F(\cl{M})}1=\\
       & = & (-1)^{m-i}\alpha(k,i,n)\,i!\,S(m,i)=(-1)^{m-i}S(m,i)\,\vec\alpha(k,i,n).\,\Box
\end{array}
$$

Now we could give the basic formula of the paper.

\begin{theorem}\hypertarget{trm1}{}
  For every $k,m\in\mbox{\bf N}$ and $n\in\mbox{\bf N}_0$,
  $$
  \alpha(k,m,n)=\displaystyle\dfrac{1}{m!}\sum_{i=1}^m|s(m,i)|\,\beta(k,i,n),
  $$
  where
  $$
  \beta(k,i,n)=\sum_{D\in\cl{J}_i}(-1)^{|ED|}\lambda(D).
  $$
\end{theorem}

{\it Proof\/}.\ From (\hyplnk{second}{2}) it follows that
$$
\beta(k,m,n)=\sum_{D\in\cl{J}_m}(-1)^{|ED|}\sum_{i=1}^m|\gt{M}^{(i)}(D)|.
$$
Changing the order of summation in the last sum and using \hyplnk{lmm2}{Lemma 3.2}, we obtain that
$$
\beta(k,m,n)=\sum_{i=1}^m\sum_{D\in\cl{J}_m}(-1)^{|ED|}|\gt{M}^{(i)}(D)|=
             \sum_{i=1}^m(-1)^{m-i}\,S(m,i)\,\vec\alpha(k,i,n).
$$
Finally, applying the Stirling inversion \cite{Aig} to the previous formula we get
\begin{equation}
  \vec\alpha(k,m,n)=\displaystyle\sum_{i=1}^m|s(m,i)|\,\beta(k,i,n).\hypertarget{third}{}
\end{equation}
Now from (\hyplnk{first}{1}) follows the statement.\,$\Box$

It is easy to see that the following statement holds.


\begin{lemma}\hypertarget{lmm3}{}
  If
  $C_1,C_2,\dots, C_i$
  are all weak components of a digraph $D$, then we have
  $$
  \lambda(D)=\lambda(C_1)\cdot\lambda(C_1)\cdot\ldots\cdot\lambda(C_i).
  $$
\end{lemma}

Let
$B_n(k_1,k_2,\dots,k_n)$
be the number of all partitions of an $n$-set into
$k_1+k_2+\dots+k_n$
subsets among which there are exactly
$k_i$ $i$-subsets ($i\in\ov{n}$).
Then the polynomials
$$
Y_n(x_1,x_2,\dots,x_n)=\sum_{(k_1,k_2,\dots,k_n)}
B_n(k_1,k_2,\dots,k_n)\,x_1^{k_1}x_2^{k_2}\dots x_n^{k_n},
$$
where
$k_1+2k_2+\dots+nk_n=n$ ($k_i\ge0$),
are called, as it is known, Bell polynomials \cite{Rio}. Let
${\cal J}^c_{m}$
be the set of all weakly connected hedgehogs from the set
${\cal D}_m$, and let
$$
\gamma(k,i,n)=\sum_{D\in{\cal J}^c_{i}}(-1)^{|ED|}\lambda(D),\quad i\in\ov{1,m}.
$$
Now using Lemma 3.3 we can pass in \hyplnk{trm1}{Theorem 3.1} from the class of all hedgehogs to the class of all connected
hedgehogs.


\begin{lemma}\hypertarget{lmm4}{}
  For every $i\in\ov{m}$, $\beta(k,i,n)=Y_i(\gamma(k,1,n),\gamma(k,2,n),\dots,\gamma(k,i,n))$.
\end{lemma}

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


\smallskip
\begin{lemma}\hypertarget{lmm5}{}
  For every
  $D\in{\cal D}_m$,
  ${\lambda}(D)=\eta^n(D)$.
\end{lemma}

{\it Proof\/}.\
Let a digraph $D$ be given, and let
$(\bk{a}_1,\dots,\bk{a}_m)\in\mbox{\got M}(D)$.
Note that
$\bk{a}_i\subseteq\bk{a}_j$ ($i,j\in\overline{m}$, $i\ne j$)
iff
$\vec{\bk{a}}_i\le\vec{\bk{a}}_j$.
Hence it follows that for every
$i\in\overline{n}$,
the mapping
$\hat{\nu}_i$
of
$V_m$
into
$\overline{0,k-1}$,
where
$\hat{\nu}_i(v_j)=\mbox{\bf pr}_i(\bk{a}_j)$
for every
$j\in\overline{m}$,
is a monotone $k$-coloring of $D$. Assign to
$(\bk{a}_1,\dots,\bk{a}_m)$
the ordered $n$-tuple
$(\hat{\nu}_1,\dots,\hat{\nu}_n)$
of monotone $k$-colorings of $D$. Now let
$(\nu_1,\dots,\nu_n)$
be an ordered $n$-tuple of monotone $k$-colorings of $D$. Assign to this tuple the ordered $m$-tuple
$(\bk{a}_1,\dots,\bk{a}_m)$,
where
$\vec{\bk{a}}_i=(\nu_1(v_i),\dots,\nu_n(v_i))$
for every
$i\in\overline{m}$.
It is easy to see that
$(\bk{a}_1,\dots,\bk{a}_m)\in\mbox{\got M}(D)$.
As both of the above mappings are one-to-one, the required equation holds.\,$\Box$

From \hyplnk{trm1}{Theorem 3.1} and Lemma 3.5 we get the following theorem:

\begin{theorem}\hypertarget{trm2}{}
  $\alpha(k,m,n)=\displaystyle\frac{1}{m!}\sum_{i=1}^m|s(m,i)|\sum_{D\in\cl{J}_i}(-1)^{|ED|}\eta^n(D)$.
\end{theorem}


Finally, using \hyplnk{trm1}{Theorem 3.1}, Lemma 3.4 and Lemma 3.5, we are able to prove the following theorem:


\begin{theorem}\hypertarget{trm3}{}
  For every $k,m\in\mbox{\bf N}$ and $n\in\mbox{\bf N}_0$,
  $$
  \alpha(k,m,n)=\dfrac{1}{m!}\sum_{i=1}^{m}|s(m,i)|\,\beta(k,i,n),
  $$
  where
  $$
  \beta(k,i,n)=Y_i(\gamma(k,1,n),\gamma(k,2,n),\dots,\gamma(k,i,n)),\quad i\in\ov{m},
  $$
  and
  $$
  \gamma(k,j,n)=\sum_{D\in{\cal J}^c_{j}}(-1)^{|ED|}\eta^n_k(D),\quad j\in\ov{1,m}.
  $$
\end{theorem}




\section{On monotone $k$-colorings of digraphs}

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


\begin{proposition}\hypertarget{prp1}{}
  If
  $D$ and $D'$
  are two isomorphic digraphs, then
  $\eta(D)=\eta(D')$.
\end{proposition}

\begin{proposition}\hypertarget{prp2}{}
  If
  $D^\ast$
  is the condensation of a digraph $D$, then
  $\eta(D^\ast)=\eta(D)$.
\end{proposition}

\begin{proposition}\hypertarget{prp3}{}
  If
  $C_1,C_2,\dots, C_k$
  are all weak components of a digraph $D$, then
  $$
  \eta(D)=\eta(C_1)\cdot\eta(C_1)\cdot\dots\cdot\eta(C_k).
  $$
\end{proposition}

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.


\begin{proposition}\hypertarget{prp4}{}
  For every digraph
  $D$,
  $\eta(D^{-1})=\eta(D)$.
\end{proposition}


{\it Proof\/}. Let
$D=(V,E)$
be a digraph, and
$f\!:V\to\overline{0,k-1}$
be a monotone $k$-coloring of $D$. Then the mapping
$\hat{f}\!:V\to\overline{0,k-1}$,
where
$\hat{f}(v)=k-1-f(v)$
for every
$v\in V$,
is a monotone $k$-coloring of
$D^{-1}$.
Obviously, the correspondence
$f\mapsto\hat{f}$
defines a bijection between sets
$H(D)$ and $H(D^{-1})$, and consequently
$|H(D)|=|H(D^{-1})|$, i.e., $\eta(D^{-1})=\eta(D)$.\,$\Box$

\medskip
Let $D$ be a digraph, and
$V_1\subseteq VD$
be a set of its vertices. Denote by
$D-V_1$
the subgraph
$<\!VD\backslash V_1\!>$
of $D$ induced by the set of vertices
$VD\backslash V_1$.
Let $v$ be a vertex of $D$. Denote by
$\mbox{Out}(v)$
the set of all vertices from
$VD\backslash\{v\}$
which are accessible in $D$ from $v$, and by
$\mbox{In}(v)$
--- the set of all vertices from
$VD\backslash\{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\in VD$).

Let $D\in{\cal D}_m$ be an arbitrary digraph. Suppose that we have
$k$ colors at our disposal. To find the number $\eta(D)=\eta_k(D)$
we make use of the following {\it General coloring procedure\/}:
\begin{enumerate}
\item Find the condensation $D^\ast$ of the digraph $D$. Go to the next step.
\item If in
  $D^\ast$
  there are two vertices
  $u,v\in VD$
  such that
  $(u,v)\in ED$,
  and there exists a path
  $v_1=u,e_1,v_2,\dots,v_{n-1},e_{n-1},v_n=v$ ($n\ge3$),
  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.
\item Take
  $l:=0$ and $\mbox{\got D}_0:=\{D_1^{(0)}\}$, where
  $D_1^{(0)}$
  is the vertex-weighted digraph
  $(D',f_{D'})$
  such that
  $|v|=\ov{0,k-1}$
  for every
  $v\in VD'$.
  Go to the next step.
\item If all digraphs from
  $\mbox{\got D}_l=\{D_1^{(l)},D_2^{(l)},\dots,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\in\ov{n_l}$) from $\mbox{\got D}_l$
  that is not totally disconnected. Let
  $v\in D_{i_0}^{(l)}$,
  and let
  $||v||=p$
  (here
  $||v||$
  means cardinality of the set
  $|v|$).
  Take $p$ isomorphic copies
  $$
  \ov{D}_{i_0}^{(l+1)},\ov{D}_{i_0+1}^{(l+1)},\dots,\ov{D}_{i_0+p-1}^{(l+1)}
  $$
  of the vertex-weighted digraph
  $D_{i_0}^{(l)}-v$
  so that
  $V\ov{D}_{i_0+j-1}^{(l+1)}\cap VD_i^{(l)}=\emptyset$
  for every
  $j\in\ov{p}$ and $i\in\ov{n_l}$,
  and
  $V\ov{D}_{i_0+j_1-1}^{(l+1)}\cap V\ov{D}_{i_0+j_2-1}^{(l+1)}=\emptyset$
  for every
  $j_1,j_2\in\ov{p}$, $j_1\ne j_2$.
  For every vertex
  $u\in V(D_{i_0}^{(l)}-v)$, by $u^{(j)}$ ($j\in\ov{p}$)
  denote the corresponding vertex of the vertex-weighted digraph
  $\ov{D}_{i_0+j-1}^{(l+1)}$;
  consequently,
  $|u^{(j)}|=|u|$
  for every
  $j\in\ov{p}$.
  For each
  $t\in |v|=\ov{n_1,n_2}$,
  perform the following operations. For every
  $u\in\mbox{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)}|\cap\,\ov{t,k-1}$.
  Also, for every
  $u\in\mbox{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)}|\cap\,\ov{0,t}$.
  Let us denote the obtained vertex-weighted digraph by
  $\ov{\ov{D}}_{(i_0+t-n_1)}^{(l+1)}$.
  Now put
  $$
  \hat{D}_j^{(l+1)}:=\left\{\begin{array}{ll}
                              D_j^{(l)}, & j\in\ov{1,i_0-1},\\
                              \ov{\ov{D}}_j^{(l)}, & j\in\ov{i_0,i_0+p-1},\\
                              D_{j-p+1}^{(l)}, & j\in\ov{i_0+p,n_l+p-1}.
                     \end{array}\right.
  $$
  Increase the value of the parameter $l$ by 1. Go to the next step.
\item If for some vertex $v$ of a digraph
  $\hat{D}_j^{(l)}\in\mbox{\got D}_l$ ($j\in\overline{n_l}$)
  it holds that
  $|v|=1$ and $|V\hat{D}_j^{(l)}|\ne1$, then
  $\hat{D}_j^{(l)}:=\hat{D}_j^{(l)}-\{v\}$.
  Repeat this operation until it is possible. Put
  $D_j^{(l)}:=\hat{D}_j^{(l)}$
  for every
  $j\in\overline{n_l}$.
  Go again to the forth step.
\item Calculate the value
  $$
  \eta_k(D)=\sum_{i=1}^{n_l}\prod_{v\in{D^{(l)}_i}}||v||,
  $$
  and finish the procedure.
\end{enumerate}

Let $D$ be a digraph, and let
$|VD|=m$.
It is clear that
$\hat\eta_i(D)=0$
for every
$i>m$,
and that
\begin{equation}
  \eta_k(D)=\sum_{i=1}^{k}\binom{k}{i}\hat\eta_i(D).\hypertarget{forth}{}
\end{equation}
The last formula is very useful: knowing the finite set of numbers
$\hat\eta_i(D)$, $i\in\ov{m}$,
we can find
$\eta_k(D)$
for every
$k\in\mbox{\bf N}$.
By applying binomial inversion \cite{Aig} to (4) we get
\begin{equation}
  \hat\eta_{k}(D)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\eta_{i}(D).\hypertarget{fifth}{}
\end{equation}

Let us give formulas for
$\eta_k(D)$
in some special cases of digraph
$D$.


\smallskip\noindent
{\bf Example 1}\,\;
By using General coloring procedure we can find, for example, the value
$\eta_3$
of the following digraph $D$:


\setlength{\unitlength}{0.1pt}
\thicklines
$$
\begin{array}{lcl}
\makebox(650,640)[20,20]{
\put(240,0){\circle*{40}}
\put(480,0){\circle*{40}}
\put(120,240){\circle*{40}}
\put(360,240){\circle*{40}}
\put(240,480){\circle*{40}}
\put(480,480){\circle*{40}}
\put(0,360){\circle*{40}}
\put(0,600){\circle*{40}}
\put(480,480){\line(-1,-2){120}}
\put(480,480){\vector(-1,-2){100}}
\put(360,240){\line(1,-2){120}}
\put(360,240){\vector(1,-2){100}}
\put(240,0){\line(1,2){120}}
\put(240,0){\vector(1,2){100}}
\put(240,480){\line(1,-2){120}}
\put(240,480){\vector(1,-2){100}}
\put(240,480){\line(-1,-2){120}}
\put(240,480){\vector(-1,-2){100}}
\put(120,240){\line(1,-2){120}}
\put(120,240){\vector(1,-2){100}}
\put(240,480){\line(-2,-1){240}}
\put(240,480){\vector(-2,-1){220}}
\put(0,600){\line(2,-1){240}}
\put(0,600){\vector(2,-1){220}}
\put(0,360){\line(0,1){240}}
\put(0,360){\vector(0,1){220}}}
&
\hskip20pt
\makebox(80,640)[0,0]{
\put(40,200){\makebox(0,0){\large $=$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip-10pt
&
\makebox(640,640)[20,20]{
\put(0,200){\circle*{40}}
\put(0,400){\circle*{40}}
\put(0,600){\circle*{40}}
\put(300,0){\circle*{40}}
\put(400,200){\circle*{40}}
\put(500,0){\circle*{40}}
\put(0,600){\line(0,-1){200}}
\put(0,600){\vector(0,-1){180}}
\put(0,400){\line(0,-1){200}}
\put(0,400){\vector(0,-1){180}}
\put(0,200){\line(3,-2){300}}
\put(0,200){\vector(3,-2){280}}
\put(0,600){\line(1,-2){300}}
\put(0,600){\vector(1,-2){280}}
\put(400,200){\line(-1,-2){100}}
\put(400,200){\vector(-1,-2){80}}
\put(300,0){\line(1,0){200}}
\put(300,0){\vector(1,0){180}}}
%
\hskip25pt
\makebox(80,640)[0,0]{
\put(40,200){\makebox(0,0){\large $=$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip0pt
%
\makebox(640,640)[20,20]{
\put(0,200){\circle*{40}}
\put(0,400){\circle*{40}}
\put(0,600){\circle*{40}}
\put(300,0){\circle*{40}}
\put(400,200){\circle*{40}}
\put(500,0){\circle*{40}}
\put(0,600){\line(0,-1){200}}
\put(0,600){\vector(0,-1){180}}
\put(0,400){\line(0,-1){200}}
\put(0,400){\vector(0,-1){180}}
\put(0,200){\line(3,-2){300}}
\put(0,200){\vector(3,-2){280}}
\put(400,200){\line(-1,-2){100}}
\put(400,200){\vector(-1,-2){80}}
\put(300,0){\line(1,0){200}}
\put(300,0){\vector(1,0){180}}}
%
\hskip25pt
\makebox(80,640)[0,0]{
\put(40,200){\makebox(0,0){\large $=$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip0pt
%
\makebox(640,640)[20,20]{
\put(0,200){\circle*{40}}
\put(-18,182){\makebox(0,0)[rt]{\scriptsize $\overline{0,2}$}}
\put(0,400){\circle*{40}}
\put(-18,382){\makebox(0,0)[rt]{\scriptsize $\overline{0,2}$}}
\put(0,600){\circle*{40}}
\put(-18,582){\makebox(0,0)[rt]{\scriptsize $\overline{0,2}$}}
\put(300,0){\circle*{40}}
\put(300,0){\circle{80}}
\put(282,-22){\makebox(0,0)[rt]{\scriptsize $\overline{0,2}$}}
\put(400,200){\circle*{40}}
\put(418,182){\makebox(0,0)[lt]{\scriptsize $\overline{0,2}$}}
\put(500,0){\circle*{40}}
\put(482,-22){\makebox(0,0)[rt]{\scriptsize $\overline{0,2}$}}
\put(0,600){\line(0,-1){200}}
\put(0,600){\vector(0,-1){180}}
\put(0,400){\line(0,-1){200}}
\put(0,400){\vector(0,-1){180}}
\put(0,200){\line(3,-2){300}}
\put(0,200){\vector(3,-2){280}}
\put(400,200){\line(-1,-2){100}}
\put(400,200){\vector(-1,-2){80}}
\put(300,0){\line(1,0){200}}
\put(300,0){\vector(1,0){180}}}
%
\hskip30pt
\makebox(80,600)[0,0]{
\put(40,200){\makebox(0,0){\large $=$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip-10pt\\[10pt]
&
\hskip20pt
\makebox(80,640)[0,0]{
\put(40,200){\makebox(0,0){\large $=$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip-10pt
&
\makebox(640,640)[20,20]{
\put(0,200){\circle*{40}}
\put(-18,182){\makebox(0,0)[rt]{\scriptsize $0$}}
\put(0,400){\circle*{40}}
\put(-18,382){\makebox(0,0)[rt]{\scriptsize $0$}}
\put(0,600){\circle*{40}}
\put(-18,582){\makebox(0,0)[rt]{\scriptsize $0$}}
\put(300,240){\circle*{40}}
\put(282,222){\makebox(0,0)[rt]{\scriptsize $0$}}
\put(300,40){\circle*{40}}
\put(282,22){\makebox(0,0)[rt]{\scriptsize $\overline{0,2}$}}
\put(0,600){\line(0,-1){200}}
\put(0,600){\vector(0,-1){180}}
\put(0,400){\line(0,-1){200}}
\put(0,400){\vector(0,-1){180}}}
%
\hskip5pt
\makebox(80,640)[0,0]{
\put(40,200){\makebox(0,0){\large $+$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip5pt
%
\makebox(650,640)[30,20]{
\put(0,200){\circle*{40}}
\put(-18,182){\makebox(0,0)[rt]{\scriptsize $\overline{0,1}$}}
\put(0,400){\circle*{40}}
\put(-18,382){\makebox(0,0)[rt]{\scriptsize $\overline{0,1}$}}
\put(0,600){\circle*{40}}
\put(-18,582){\makebox(0,0)[rt]{\scriptsize $\overline{0,1}$}}
\put(300,240){\circle*{40}}
\put(282,222){\makebox(0,0)[rt]{\scriptsize $\overline{0,1}$}}
\put(300,40){\circle*{40}}
\put(282,22){\makebox(0,0)[rt]{\scriptsize $\overline{1,2}$}}
\put(0,600){\line(0,-1){200}}
\put(0,600){\vector(0,-1){180}}
\put(0,400){\line(0,-1){200}}
\put(0,400){\vector(0,-1){180}}}
%
\hskip5pt
\makebox(80,640)[0,0]{
\put(40,200){\makebox(0,0){\large $+$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip5pt
%
\makebox(650,640)[30,20]{
\put(0,200){\circle*{40}}
\put(-18,182){\makebox(0,0)[rt]{\scriptsize $\overline{0,2}$}}
\put(0,400){\circle*{40}}
\put(-18,382){\makebox(0,0)[rt]{\scriptsize $\overline{0,2}$}}
\put(0,600){\circle*{40}}
\put(-18,582){\makebox(0,0)[rt]{\scriptsize $\overline{0,2}$}}
\put(300,240){\circle*{40}}
\put(282,222){\makebox(0,0)[rt]{\scriptsize $\overline{0,2}$}}
\put(300,40){\circle*{40}}
\put(282,22){\makebox(0,0)[rt]{\scriptsize $2$}}
\put(0,600){\line(0,-1){200}}
\put(0,600){\vector(0,-1){180}}
\put(0,400){\line(0,-1){200}}
\put(0,400){\vector(0,-1){180}}}
%
\hskip15pt
\makebox(80,600)[0,0]{
\put(40,200){\makebox(0,0){\large $=$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip-10pt\\[-10pt]
&
\hskip20pt
\makebox(80,600)[0,0]{
\put(40,200){\makebox(0,0){\large $=$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip-10pt
&
\makebox(2300,600)[0,0]{
\put(40,200){\makebox(0,0){\large $3\cdot1\cdot1\;+\;4\cdot2\cdot2\;+\;10\cdot3\cdot1$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip5pt
%
\hskip-5pt
\makebox(80,600)[0,0]{
\put(40,200){\makebox(0,0)[r]{\large $=$}}
\put(0,0){\makebox(80,400)[b]{}}}
\hskip15pt
%
\makebox(80,640)[0,0]{
\put(40,200){\makebox(0,0){\large $49.$}}
\put(0,0){\makebox(80,400)[b]{}}}
\end{array}
$$


\vskip-24pt\noindent
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{center}
\begin{tabular}{l|rrrrrrrr}
$k$             & 1 & 2  & 3   & 4    & 5   & 6    & 7    & 8\\ \hline
$\eta_k(D)$     & 1\quad & 10\quad & 49\quad  & 168\quad  & 462\quad & 1092\quad & 2310\quad & 4488\\ \hline
$\hat\eta_k(D)$ & 1 & 8  & 22  & 28   & 17  & 4    & 0    & 0
\end{tabular}
\end{center}


\noindent
Using (\hyplnk{fifth}{5}) from the first row we get the second row of the table. Now from (\hyplnk{forth}{4}) we have
$$
\eta_{k}(D)=\dfrac{1}{360}\cdot(24k+98k^2+135k^3+80k^4+21k^5+2k^6).
$$
Note that we accidentally have obtained the sequence (\seqnum{A051947}).


\smallskip\noindent
{\bf 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
$$
\eta_k(P_n)=\binom{n+k-1}{k-1}.
$$


\smallskip\noindent
{\bf Example 3}\,\;
Denote by
$\vec{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
$\vec{K}(1,n)$
we immediately have that
\begin{equation}
  \eta_k[\vec{K}(1,n)]=1^n+2^n+\dots+k^n.\hypertarget{sixth}{}
\end{equation}

Now let us generalize formula (6).


\begin{proposition}\hypertarget{prp5}{}
  For every $k,m,n\in\mbox{\bf N}$,
  \begin{equation}
    \eta_k[\vec{K}(m,n)]=\sum_{i=1}^{k}[(k+1-i)^n-(k-i)^n]\cdot i^m\hypertarget{seventh}{}
  \end{equation}
  or
  $$
  \eta_k[\vec{K}(m,n)]=\sum_{i=1}^{k}[(k+1-i)^m-(k-i)^m]\cdot i^n.
  $$
\end{proposition}

{\it 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
$\Phi_i(J)$, $i\in\ov{2}$,
the set of all functions
$f\!:V_i(J)\to\ov{0,k-1}$.
Then
\begin{equation}
\eta(J)=\sum_{f\in\Phi_2(J)}\prod_{v\in V_1(J)}(\min\{f(u)\,|\,u\in\mbox{Out}(v)\}+1)\hypertarget{eight}{}
\end{equation}
or
\begin{equation*}
  \eta(J)=\sum_{f\in\Phi_1(J)}\prod_{v\in V_2(J)}(k-\max\{f(u)\,|\,u\in\mbox{In}(v)\}).
\end{equation*}

Because
$\vec{K}(m,n)\in{\cal J}_{m+n}^{c}$
we can make, for example, use of the first formula, and calculate the number of functions
$f\in\Phi_2(\vec{K}(m,n))$
satisfying the condition
$$
\min\{f(u)\,|\,u\in V_2(\vec{K}(m,n))\}=i-1.
$$
For this purpose we have to find the number of $n$-tuples of the numbers
$i-1,i,\dots,k-1$
containing the number $i-1$, and by using the formula (\hyplnk{eight}{8}) we get the formula from the proposition.

The second equality of the proposition follows immediately from (\hyplnk{seventh}{7}) and
\hyplnk{prp4}{Proposition 4.4}.\,$\Box$




\section{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$-{\it multiantichain\/}
${\cal M}$
of multisets on a set $S$ we mean an $m$-multiset
${\cal M}$
of multisets on $S$ such that
$\bk{a}\not\subseteq\bk{b}$
or
$\bk{a}=\bk{b}$
for every
$\bk{a},\bk{b}\in{\cal M}$.
An $m$-multiantichain of $k$-bounded multisets on an $n$-set $S$ is called a $(k,m,n)$-{\it multiantichain\/} on $S$.

Let us denote by
${\cal A}^\ast(k,m,n)$
the set of all $(k,m,n)$-multi\-anti\-chains on $S$,
and put
$$
\alpha^\ast(k,m,n)=|{\cal A}^\ast(k,m,n)|.
$$
Introduce the numbers
$$
t(m,i)=\sum_{l=i}^{m}L'(m,l)\,|s(l,i)|,\quad i\in\overline{m},
$$
where $L'(m,l)$ are unsigned Lah numbers \cite{Aig}, or, as they
are also called, Stirling numbers of the third kind; let us call
the numbers $t(m,i)$ {\it unsigned Lah-Stirling numbers of the
first kind\/}. The following table gives these numbers for small
values of $m$ and $i$ (\seqnum{A079638}):
\begin{center}
\begin{tabular}{r|lllllll}\hypertarget{Table}{}
$t(m,i)$ & $i=1$   & 2      & 3     & 4     & 5    & 6  & 7 \\
\hline
$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\phantom{1} & 143892 & 70924\phantom{1} & 14805\phantom{1} & 1435\phantom{11} & 63\phantom{1111} & 1
\end{tabular}
\end{center}
Now let us prove the following assertion:


\begin{theorem}\hypertarget{trm4}{}
  $\displaystyle\alpha^\ast(k,m,n)=\frac{1}{m!}\sum_{i=1}^{m}t(m,i)\,\beta(k,i,n)$.
\end{theorem}

{\it Proof.\/}\ As
$\binom{m-1}{l-1}$
is the number of compositions of the number $m$ into $l$ parts \cite{Aig}, we have
\begin{eqnarray*}
\alpha^\ast(k,m,n)& = & \sum_{l=1}^{m}\binom{m-1}{l-1}\alpha(k,l,n) = \\
                  & = & \frac{1}{m!}\sum_{l=1}^{m}\frac{m!}{l!}
                        \binom{m-1}{l-1}\vec\alpha(k,l,n)=\frac{1}{m!}
                        \sum_{l=1}^{m}L'(m,l)\,\vec\alpha(k,l,n).
\end{eqnarray*}

Now, applying formula (\hyplnk{third}{3}) and changing the order of the summation we get
$$
\alpha^{\ast }(k,m,n)=\frac{1}{m!}\sum_{l=1}^{m}L'(m,l)\sum_{i=1}^{l}|s(l,i)|\,\beta(k,i,n)=
                      \frac{1}{m!}\sum_{i=1}^{m}t(m,i)\,\beta (k,i,n).\,\Box
$$




\section{Explicit formulas for small values of $m$}

Let us calculate
$\alpha(k,m,n)$ and $\alpha^\ast(k,m,n)$ for $k\ge 1$, $1\le m\le 4$ and $n\ge0$.
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
$\iota(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
\seqnum{A007776} and \seqnum{A002031}.) By using General coloring procedure, as in Example 1, one could fill the third
column that gives the corresponding polynomials
$\eta_k(J_i)$, $i\in\ov{8}$
(in the case of
$J_i$, $i\in\ov{2,6}$
we can make use of (\hyplnk{sixth}{6}), and in the case of
$J_8$
we can make use of \hyplnk{prp5}{Proposition 4.5}). Also let us note that from \hyplnk{prp4}{Proposition 4.4} we have that
$\eta_k(J_3)=\eta_k(J_4)$ and $\eta_k(J_5)=\eta_k(J_6)$
for every
$k\in\mbox{\bf N}$.
The last column of the table gives the corresponding reference to \cite{Slo}.


\bigskip

\def\graphw{\setlength{\unitlength}{0.06pt}\makebox(400,420)[bl]{
\put(0,0){\circle*{40}}}}

\def\grapha{\setlength{\unitlength}{0.06pt}\makebox(400,420)[bl]{
\put(0,0){\circle*{40}}
\put(0,360){\circle*{40}}
\put(0,360){\vector(0,-1){320}}
\put(0,360){\line(0,-1){360}}}}

\def\graphb{\setlength{\unitlength}{0.06pt}\makebox(400,420)[bl]{
\put(0,0){\circle*{40}}
\put(90,360){\circle*{40}}
\put(180,0){\circle*{40}}
\put(90,360){\vector(-1,-4){70}}
\put(90,360){\line(-1,-4){90}}
\put(90,360){\vector(1,-4){70}}
\put(90,360){\line(1,-4){90}}}}

\def\graphc{\setlength{\unitlength}{0.06pt}\makebox(400,420)[bl]{
\put(90,0){\circle*{40}}
\put(0,360){\circle*{40}}
\put(180,360){\circle*{40}}
\put(0,360){\vector(1,-4){70}}
\put(90,0){\line(-1,4){90}}
\put(180,360){\vector(-1,-4){70}}
\put(90,0){\line(1,4){90}}}}

\def\graphd{\setlength{\unitlength}{0.06pt}\makebox(400,420)[bl]{
\put(0,0){\circle*{40}}
\put(180,360){\circle*{40}}
\put(180,0){\circle*{40}}
\put(180,360){\vector(-1,-2){160}}
\put(180,360){\line(-1,-2){180}}
\put(180,360){\vector(1,-2){160}}
\put(180,360){\line(1,-2){180}}
\put(360,0){\circle*{40}}
\put(180,360){\vector(0,-1){320}}
\put(180,360){\line(0,-1){360}}}}

\def\graphe{\setlength{\unitlength}{0.06pt}\makebox(400,420)[bl]{
\put(180,0){\circle*{40}}
\put(0,360){\circle*{40}}
\put(180,360){\circle*{40}}
\put(0,360){\vector(1,-2){160}}
\put(180,0){\line(-1,2){180}}
\put(180,360){\vector(0,-1){320}}
\put(180,0){\line(0,1){360}}
\put(360,360){\circle*{40}}
\put(360,360){\vector(-1,-2){160}}
\put(180,0){\line(1,2){180}}}}

\def\graphf{\setlength{\unitlength}{0.06pt}\makebox(400,420)[bl]{
\put(0,0){\circle*{40}}
\put(0,360){\circle*{40}}
\put(360,0){\circle*{40}}
\put(360,360){\circle*{40}}
\put(0,360){\vector(0,-1){320}}
\put(0,360){\line(0,-1){360}}
\put(0,360){\vector(1,-1){320}}
\put(0,360){\line(1,-1){360}}
\put(360,360){\vector(0,-1){320}}
\put(360,360){\line(0,-1){360}}}}

\def\graphg{\setlength{\unitlength}{0.06pt}\makebox(400,420)[bl]{
\put(0,0){\circle*{40}}
\put(0,360){\circle*{40}}
\put(360,0){\circle*{40}}
\put(360,360){\circle*{40}}
\put(0,360){\vector(0,-1){320}}
\put(0,360){\line(0,-1){360}}
\put(0,360){\vector(1,-1){320}}
\put(0,360){\line(1,-1){360}}
\put(360,360){\vector(0,-1){320}}
\put(360,360){\line(0,-1){360}}
\put(360,360){\vector(-1,-1){320}}
\put(360,360){\line(-1,-1){360}}}}

\newlength{\ww}
\settowidth{\ww}{\large Aut($J$)}

{\normalsize
\begin{center}
\begin{tabular}{|l|l||c|c|c|l|}\hline
$m$&\,$i$\,& $J_i$    & $\iota(J_i)$ & \makebox[\ww]{$p_i=p_i(k)=\eta_k(J_i)$} &\mbox{\normalsize OEIS ID} \\\hline\hline
1  &\,1\,  & \graphw  & 1            & $k$                                     &\\\hline\hline
2  &\,2\,  & \grapha  & 2            & $(k^2+k)/2$                             &{\normalsize\seqnum{A000217}}\\\hline\hline
3  &\,3\,  & \graphb  & 3            & $(2k^3+3k^2+k)/6$                       &{\normalsize\seqnum{A000330}}\\\cline{2-6}
   &\,4\,  & \graphc  & 3            & $(2k^3+3k^2+k)/6$                       &{\normalsize\seqnum{A000330}}\\\hline\hline
4  &\,5\,  & \graphd  & 4            & $(k^4+2k^3+k^2)/4$                      &{\normalsize\seqnum{A000537}}\\\cline{2-6}
   &\,6\,  & \graphe  & 4            & $(k^4+2k^3+k^2)/4$                      &{\normalsize\seqnum{A000537}}\\\cline{2-6}
   &\,7\,  & \graphf  & 24           & $(5k^4+10k^3+7k^2+2k)/24$               &{\normalsize\seqnum{A006322}}\\\cline{2-6}
   &\,8\,  & \graphg  & 6            & $(k^4+2k^3+2k^2+k)/6$                   &{\normalsize\seqnum{A006325}}\\\hline
\end{tabular}
\end{center}}

\bigskip


By using the above table and the third formula from \hyplnk{trm3}{Theorem 3.3}, we get
$$
\gamma(k,1,n)=p_1^n,\quad\gamma(k,2,n)=-2p_2^n,\quad\gamma(k,3,n)=6p_3^n,\quad\gamma(k,4,n)=-8p_5^n-24p_7^n+6p_8^n.
$$
Replacing $x_i$ by $\gamma(k,i,n)$ ($i\in\ov{4}$) in Bell
polynomials $Y_j(x_1,\dots,x_j)$, $j\in\ov{4}$, \cite{Rio}:
\begin{equation*}
\begin{array}{l}
  Y_1(x_1)=x_1,\quad Y_2(x_1,x_2)=x_1^2+x_2,\quad
  Y_3(x_1,x_2,x_3)=x_1^3+3x_1x_2+x_3,\\
  Y_4(x_1,x_2,x_3,x_4)=x_1^4+6x_1^2x_2+4x_1x_3+3x_2^2+x_4,
\end{array}
\end{equation*}
and using the second formula from \hyplnk{trm3}{Theorem 3.3}, we
obtain the expressions:
$$
\begin{array}{l}
  \beta(k,1,n)=q_1^n,\quad\beta(k,2,n)=q_3^n-2q_2^n,\quad
  \beta(k,3,n)=q_6^n-6q_5^n+6q_4^n,\\
  \beta(k,4,n)=q_{12}^n-12q_{11}^n+24q_{10}^n+4q_9^n-24q_8^n+6q_7^n,
\end{array}
$$
where
$$
\begin{array}{l}
q_1=p_1,\quad q_2=p_2,\quad q_3=p_1^2,\quad q_4=p_3,\quad q_5=p_1p_2,\quad q_6=p_1^3,\quad q_7=p_8,\\
q_8=p_7,\quad q_9=p_5,\quad q_{10}=p_1p_3,\quad q_{11}=p_1^2p_2,\quad q_{12}=p_1^4
\end{array}
$$
(it is not difficult to see that
$q_i<q_j$
for every
$i,j\in\ov{12}$, $i\ne j$,
and every
$k\ge4$).
By using the first formula from \hyplnk{trm3}{Theorem 3.3}, we finally have that
$$
\begin{array}{lcl}
\alpha(k,1,n)&=&q_1^n,\\[3pt]
\alpha(k,2,n)&=&\dfrac{1}{2!}\,(q_1^n-2q_2^n+q_3^n),\\[9pt]
\alpha(k,3,n)&=&\dfrac{1}{3!}\,(2q_1^n-6q_2^n+3q_3^n+6q_4^n-6q_5^n+q_6^n),\\[9pt]
\alpha(k,4,n)&=&\dfrac{1}{4!}\,(6q_1^n-22q_2^n+11q_3^n+36q_4^n-36q_5^n+6q_6^n+\\
\phantom{\alpha(k,4,n)}&\phantom{=}&\phantom{\dfrac{1}{4!}\,(6q_1^n-22q_2^n+11q_3^n}
+6q_7^n-24q_8^n+4q_9^n+24q_{10}^n-12q_{11}^n+q_{12}^n).
\end{array}
$$
Similarly, using \hyplnk{trm4}{Theorem 5.1} and the unsigned Lah-Stirling numbers of the first kind from the
\hyplnk{Table}{table} given in Section 5, we get
$$
\begin{array}{lcl}
\alpha^\ast(k,1,n)&=&q_1^n,\\[3pt]
\alpha^\ast(k,2,n)&=&\dfrac{1}{2!}\,(3q_1^n-2q_2^n+q_3^n),\\[9pt]
\alpha^\ast(k,2,n)&=&\dfrac{1}{3!}\,(14q_1^n-18q_2^n+9q_3^n+6q_4^n-6q_5^n+q_6^n),\\[9pt]
\alpha^\ast(k,4,n)&=&\dfrac{1}{4!}\,(90q_1^n-166q_2^n+83q_3^n+108q_4^n-108q_5^n+18q_6^n+\\
\phantom{\alpha(k,4,n)^\ast}&\phantom{=}&\phantom{\dfrac{1}{4!}\,(90q_1^n-166q_2^n+83q_3^n}
+6q_7^n-24q_8^n+4q_9^n+24q_{10}^n-12q_{11}^n+q_{12}^n).
\end{array}
$$

\def\pp{\phantom{1}}

\smallskip\noindent
{\bf Example 4}\,\;
Let us give the values of
$q_i$ ($i\in\ov{12}$, $k\in\overline{10}$)
in the following table:
\begin{center}
\begin{tabular}{|l||r|r|r|r|r|r|r|r|r|r|}\hline
         & $k=1$ & \pp\pp\pp2  & \pp\pp\pp3  & \pp\pp\pp4   & \pp\pp\pp5      & 6    & 7    & 8    & 9    & 10   \\\hline\hline
$q_1$    & \pp\pp\pp1 & \pp\pp\pp2  & \pp\pp\pp3  & \pp\pp\pp4   & \pp\pp\pp5 & 6    & 7    & 8    & 9    & 10   \\\hline
$q_2$    & 1 & 3  & 6  & 10  & 15  & 21   & 28   & 36   & 45   & 55   \\\hline
$q_3$    & 1 & 4  & 9  & 16  & 25  & 36   & 49   & 64   & 81   & 100  \\\hline
$q_4$    & 1 & 5  & 14 & 30  & 55  & 91   & 140  & 204  & 285  & 385  \\\hline
$q_5$    & 1 & 6  & 18 & 40  & 75  & 126  & 196  & 288  & 405  & 550  \\\hline
$q_6$    & 1 & 8  & 27 & 64  & 125 & 216  & 343  & 512  & 729  & 1000 \\\hline
$q_7$    & 1 & 7  & 26 & 70  & 155 & 301  & 532  & 876  & 1365 & 2035 \\\hline
$q_8$    & 1 & 8  & 31 & 85  & 190 & 371  & 658  & 1086 & 1695 & 2530 \\\hline
$q_9$    & 1 & 9  & 36 & 100 & 225 & 441  & 784  & 1296 & 2025 & 3025 \\\hline
$q_{10}$ & 1 & 10 & 42 & 120 & 275 & 546  & 980  & 1632 & 2565 & 3850 \\\hline
$q_{11}$ & 1 & 12 & 54 & 160 & 375 & 756  & 1372 & 2304 & 3645 & 5500 \\\hline
$q_{12}$ & 1 & 16 & 81 & 256 & 625 & 1296 & 2401 & 4096 & 6561 & 10000\\\hline
\end{tabular}
\end{center}
Now using this table and the above given formulas, we can calculate the numbers
$\alpha(k,m,n)$ and $\alpha^\ast(k,m,n)$ for $m\in\overline4$, $k\in\overline{10}$,
and for every $n$. For example, using the forth column of this table, we immediately get the corresponding expressions for
$\alpha(4,m,n)$ ($m\in\ov{4}$):
$$
\begin{array}{lcl}
\alpha(4,1,n)&=&4^n,\\[3pt]
\alpha(4,2,n)&=&\dfrac{1}{2!}(4^n-2\cdot10^n+16^n),\\[9pt]
\alpha(4,3,n)&=&\dfrac{1}{3!}(2\cdot4^n-6\cdot10^n+3\cdot16^n+6\cdot30^n-6\cdot40^n+64^n),\\[9pt]
\alpha(4,4,n)&=&\dfrac{1}{4!}(6\cdot4^n-22\cdot10^n+11\cdot16^n+36\cdot30^n-36\cdot40^n+6\cdot64^n+\\
& &
\phantom{\dfrac{1}{4!}(6\cdot4^n}+6\cdot70^n-24\cdot85^n+4\cdot100^n+24\cdot120^n-12\cdot160^n+256^n).
\end{array}
$$
In this way, using the isomorphism testing program Nauty \cite{McKay} we can derive the expressions for
$\alpha(k,m,n)$ and $\alpha^\ast(k,m,n)$
at least up to
$m=16$.
For
$k=2$  and $k=3$
the corresponding expressions can be found in \cite{Slo} under the following IDs:

\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|}\hline
                    &$k=2$, $m=2$    &2, 3            &2, 4            &3, 2            &3, 3            &3, 4 \\\hline
$\alpha(k,m,n)$     &\seqnum{A016269}&\seqnum{A047707}&\seqnum{A051112}&\seqnum{A084874}&\seqnum{A084875}&\seqnum{A084876}\\\hline
$\alpha^\ast(k,m,n)$&\seqnum{A084869}&\seqnum{A084870}&\seqnum{A084871}&\seqnum{A084879}&\seqnum{A084880}&\seqnum{A084881}\\\hline
\end{tabular}
\end{center}

Note that the numbers
$\alpha(2,m,n)$
give the numbers of all ``ordinary" (not consisting of multisets, but consisting of sets) $m$-antichains on an $n$-set.
In \cite{KiJ} only the case of the numbers
$\alpha(2,m,n)$
is considered, and the expressions for these numbers, when
$m\in\ov{1,7}$ and $n\in\mbox{\bf N}$,
are given. These expressions, and the expressions for
$\alpha(2,m,n)$,
when
$8\le m\le 10$ and $n\in\mbox{\bf N}$,
together with their values for small values of $n$ are presented on site \cite{Slo} (\seqnum{A016269}, \seqnum{A047707},
\seqnum{A051112}, \seqnum{A051113}, \seqnum{A051114}, \seqnum{A051115}, \seqnum{A051116}, \seqnum{A051117},
\seqnum{A051118}).




\bibstyle{plain}
\begin{thebibliography}{xxx}
\bibitem{Aig} M. Aigner, {\it Combinatorial Theory}, Springer-Verlag, 1979.
\bibitem{Ded} R. Dedekind, Ueber Zerlegungen von Zahlen durch ihre gr\"ossten gemein\-samen Teiler,
    in ``Festschrift Hoch.\ Braunschweig u.\ ges.\ Werke" Vol.\ II, 1897, pp. 103--148.
\bibitem{Bir} G. Birkhoff, {\it Lattice Theory}, Providence, Rhode Island, 1967.
\bibitem{Riv} N. M. Riviere, Recursive formulas on free distributive lattices, {\it J.\ Combin.\ Theory} {\bf 5}
    (1968), 229--234.
\bibitem{Cve} D. Cvetkovi\'c, The number of antichains of finite power sets, {\it Publ.\ Inst.\ Math.\ (Beograd)
    (N.S.)\/} {\bf 13} (27) (1972), 5--9.
\bibitem{Aro1} J. L. Arocha, Anticadenas en conjuntos ordenados, {\it An.\ Inst.\ Mat.\ Univ.\ Nac.\ Autonoma Mexico}
    {\bf 27} (1987), 1--21.
\bibitem{Aro2} J. L. Arocha, The number of antichains of the length 5 and 6 (in Russian), VINITI 06.04.82.\ Reg.\ \#1631-82
    Dep., 1982.
\bibitem{KiJ} G. Kilibarda and V. Jovovi\'c, On the number of monotone Boolean functions with fixed number of lower units
    (in Russian), {\it Intellektualnye sistemy} ({\it Moscow\/}) {\bf 7} (1--4) (2003), 193--217.
\bibitem{Har} F. Harary, {\it Graph Theory}, Addison-Wesley, 1969.
\bibitem{Rio} J. Riordan, {\it Combinatorial Identities}, John Wiley \& Sons, 1968.
\bibitem{Slo} N. J. A.\,Sloane, {\it On-Line Encyclopedia of Integer Sequences},\\
    {\tt http://www.research.att.com/\~{}njas/sequences/}
\bibitem{McKay} B. McKay, Program Nauty for computing automorphism groups of graphs,\\
    {\tt http://cs.anu.edu.au/people/bdm/nauty}
\vspace{-1.5ex}
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 68R05; Secondary 68R10, 05A10, 05A15, 11B73, 11B83.

\noindent \emph{Keywords:}
Exact enumeration, antichain, multiset, digraph, bipartite graph, monotone coloring of a digraph, monotone Boolean function.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip


\vspace*{+.1in}
\noindent
Received October 14 2003;
revised version received  January 28 2004.
Published in {\it Journal of Integer Sequences}, February 17 2004.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.


\end{document}


\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in


\end{document}