0
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Thanks for the response! So, do we end up getting $\binom{m+1}{2}^n$? $\endgroup$
    – John
    Oct 28, 2020 at 20:05
  • 1
    $\begingroup$ @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$. $\endgroup$ Oct 28, 2020 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.