Number of ascending chains in a lattice Let $A = \{1,\ldots,n\}^2$, for some $n \in \mathbb{N}$. We define a partial order on $A$ by $(a,b) \leq (c,d)$ when $a \leq c$ and $b \leq d$. What is the number of ascending non-degenerate (all points are different) chains of length $k$, for relevant $k$. 
Help please...
This is not a homework assignment, but just a question of interest.
 A: Let F(m,n,k) be the number of ascending chains of length k in $\{1,...,m\} \times \{1,...n\}$.  Note that since the partial order satisfies $(a,b) \le (a,b)$, an ascending chain should be allowed to include points repeated arbitrarily many times.
By first-step analysis, $F(m,n,k) = \sum_{i=1}^m \sum_{j=1}^n F(i,j,k-1)$, with
$F(m,n,0) = 1$. I get $F(m,n,k) = {m+k-1 \choose k} {n+k-1 \choose k}$.
Or did you want to disallow repeated points in the chain?  That would make things more complicated.
A: At the peril of answering someone else's homework problem...
Think of a chain as a sequence of moves of length 1 in either the first or second of the pair. A move of 1 in the first we designate by 0, in the second by 1. an ascending chain of length $k$ is then any such binary sequence of length $k$. Since there are no restrictions on these binary strings, there is a one-to-one correspondence between chains of length $k$ and binary sequences of length $k$, or $2^k$.
A: I put a little bit of thought into this and came up with some not very helpful formulas, but maybe you'd like to see them. Let $A,n,\leq$ be as defined in your question. Suppose that $F(n,k,a,b)$ is the number of ascending chains in $A$ starting at $(a,b)$ and $F(n,k)$ is the number of ascending chains in $A$ of length $k$. Then we may define $F$ recursively, let $C:=\{(c,d) \in A: (a,b)\leq (c,d) \}
$
$$F(n,k,a,b)=\sum_{(c,d) \in C} F(n,k-1,c,d).$$
Clearly $F(n,0,a,b)=1$  and we may also deduce without too much work that $F(n,1,a,b)=(n-a+1)(n-b+1)-1$, that is we have (n-a+1) numbers greater than or equal to a in our set and likewise for b, but we can't use (a,b) so we have to subtract 1. Using that formula I can calculate $F(n,1)$ but the result isn't very pretty. Also note that for $k>2n-2, F(n,k)=0$, since the longest a chain can be is $2n-2$. 
It's plausible that I'm looking at the problem the wrong way, but I couldn't get anywhere past the $k=1$ case calculating directly and I don't find the recurrence that much more useful. And while I can relate $F(n,k,a,b)$ to $F(n,k-1),c,d)$ in a reasonable manner, I don't see any "neat" way to relate $F(n,k)$ and $F(n,k-1)$ without invoking the previous relation. 
