counting the number of antichains in $P_{m,n}$

Question

Define m and n be integers. $P_{m,n}$ denote the set of pairs of integers $(i,j)$ with $1\leq i\leq m$ and $1\leq j\leq n$. Define a partial order on $P_{m,n}$ as: \begin{equation} (i,j)\leq (i^{'},j^{'}) \iff (i\leq i^{'} and \ j\leq j^{'}) \end{equation} I've done the first part as "count the number of maximal chains in $P_{m,n}$", but I don't know how to count the number of the antichains in $P_{m,n}$(As it needs to count every size!). Thank you for your help!

Answer 1

The following are equal:

(1) the number of antichains in $P_{m,n}$;
(2) the number of lower sets in $P_{m,n}$
(3) the number of nondecreasing functions $f:\{1,\dots,m\}\to\{0,1,\dots,n\}$
(4) the number of solutions of the equation $x_0+x_1+\cdots+x_n=m$ in integers $x_i\ge0$;
(5) the binomial coefficient $\binom{m+n}n$.

(1) = (2): In any finite partially ordered set, the number of antichains is equal to the number of lower sets. If $L$ is a lower set, the set $a(L)$ of all maximal elements of $L$ is an antichain; if $A$ is an antichain, the set $\ell(A)=\{x:\exists a\in A\ (x\in a)\}$ is a lower set; the maps $a$ and $\ell$ are easily seen to be inverses.

(2) = (3): A lower set $L$ corresponds to the function $f(i)=|\{j:(i,j)\in L\}|.$

(3) = (4): A sequence $x_0,x_1,\dots,x_n$ of nonnegative integers with $x_0+x_1+\cdots+x_n=m$ corresponds to the unique nondecreasing function $f:\{1,\dots,m\}\to\{0,1,\dots,n\}$ such that $|\{i:f(i)=k\}|=x_k$ for $k=0,1,\dots,n.$

(4) = (5): this is the so-called stars and bars theorem.