# Close Form Expression of The Cartesian Product of Linearly Ordered Sets

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?

• Thanks for the response! So, do we end up getting $\binom{m+1}{2}^n$?
– John
Oct 28, 2020 at 20:05
• @John: Yes, via sums $$\sum_{k_1=1}^m\sum_{k_2=1}^m\ldots\sum_{k_n=1}^mk_1k_2\ldots k_n\,;$$ showing that these evaluate to $\binom{m+1}2^n$ is perhaps most easily done by induction on $n$. Oct 28, 2020 at 20:09