I was reading a combinatorics textbook,and I came across this problem.
Let the $product$ of partially ordered sets $(S_1, \preceq_1),..., (S_n, \preceq_n)$ be the partial order $\preceq$ on the cartesian product $S_1 \times S_2 \times ... \times S_n$ given by $(s_1,...,s_n) \preceq (t_1,...,t_n)$ iff $s_i \preceq_i t_i \; \forall i \in [n]$. Also, let $(S, \leq)$ be a linearly ordered set with $m$ elements and $(S^n, \leq^n)$ be its $n^{th}$ power in the above sense. What is the closed form expression for $|\leq ^n|$?.
My intuition on this is that this $n-$ary cartesian power of $(S, \leq)$ is isomorphic to the space of all functions from $[m]$ to $[n]$, which is $n^m$. In other words, to me it seems like for every element $(s_1, s_2,...,s_m)$, any $s_i$ for $1\leq i \leq m$ can be chosen $n$ times regardless of other elements. Since $(S, \leq)$ is a linearly ordered set with $m$ elements, then $|\leq ^n| = n ^m$.
Is there any error in my reasoning? I would appreciate any help on this!
We can take $S$ to be $[m]$ with the usual order, in which case $|S^n|=m^n$, but that’s not what you’re asked to find: what’s wanted here is the cardinality of the order relation itself, i.e., the number of pairs
$$\big\langle\langle k_1,\ldots,k_n\rangle,\langle \ell_1,\ldots,\ell_n\rangle\big\rangle\in[m]^n\times[m]^n$$
such that $k_i\le\ell_i$ for $i=1,\ldots,n$.
When $n=1$ this is $\sum_{k=1}^mk=\frac{m+1}2$, since $|\{\ell\in[m]:\ell\le k\}|=k$ for each $k\in[m]$.
When $n=2$ it is
$$\begin{align*} \sum_{k=1}^m\sum_{\ell=1}^mk\ell&=\sum_{k=1}^mk\sum_{\ell=1}^m\ell\\ &=\sum_{k=1}^mk\binom{m+1}2\\ &=\binom{m+1}2\sum_{k=1}^mk\\ &=\binom{m+1}2^2\,, \end{align*}$$
since there are $k\ell$ pairs $\langle i,j\rangle\in[m]^2$ such that $i\le k$ and $j\le\ell$.
Can you take it from there?