6
$\begingroup$

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.

4 Answers 4

1

This is equivalent to the number of paths from $(0,0)$ to $(n,n)$ allowing -any- lattice steps that move closer to $(n,n)$ (this takes into account 'repeated points in the chain). Another way of saying this is integer compositions of $(n,n)$ (adding any sequence of pairs from $(i,j)$, where $i,j$ can run independently from 0 to $n$, but at least one is greater than 0).

The recurrence for $F(n,m,k)$ is $ F(m,n,k) = \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} F(i,j,k-1) + \sum_{i=0}^{n-1} F(i,m,k-1)+ \sum_{j=0}^{m-1} F(n,j,k-1) $ which converts to

$ \begin{eqnarray} F(0,0,0) &=& 1\\ F(n,m,0) &=& 0\\ F(n,m,k) &=& F(n,m-1,k) + F(n-1,m,k) - F(n-1, m-1,k) +\\ && F(n,m-1,k-1) + F(n-1,m,k-1) - F(n-1, m-1,k-1) \end{eqnarray} $

The following table is for $\sum_{k\ge0} F(n,m,k)$:

1       1       2       4       8       16      32      64      128     256 1       3       8       20      48      112     256     576     1280 2       8       26      76      208     544     1376    3392 4       20      76      252     768     2208    6080 8       48      208     768     2568    8016 16      112     544     2208    8016 32      256     1376    6080 64      576     3392 128     1280 256 

with main diagonal: $ 1, 3, 26, 252, 2568, 26928, 287648, 3112896,... $

the number of paths to $(n,n)$ of any length (1 to 2n), which is OEIS sequence A02141, closely related to the central Delannoy numbers({OEIS A001850](http://oeis.org/A001850)).

The original question, for the table $F(n,n,k)$ for those paths of length $k$, this is given by OEIS A059576.

  • 0
    Thank you very much! I've lost hope for this question already :)2011-07-12
2

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.

  • 0
    I think repeated points are disallowed. Though I haven't mentioned it specifically. I'll edit the question. Thanks however Robert, it is a good point we didn't think of.2011-03-22
1

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$.

  • 0
    @shamovic: OK. Well then, I answered -some- question :)2011-03-22
1

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.

  • 0
    Thanks Jacob, We've reached the same breaking point before I've posted the question here. It seems that recursion can't be resolved easily. Maybe our thought that the solution should be rather trivial is wrong :)2011-03-22