Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 1 down vote accepted

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.

share|improve this answer
    
Thank you very much! I've lost hope for this question already :) –  shamovic Jul 12 '11 at 21:56

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.

share|improve this answer
    
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. –  shamovic Mar 22 '11 at 19:43

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

share|improve this answer
    
Does this work? I'm not entirely convinced, what you've described is the number of paths of length $k$ in $2$-tree. Unless ascending chain has a stricter definition than I'm aware of, I don't see why (1,1)->(1,n) is invalid. –  JSchlather Mar 21 '11 at 21:26
    
Thanks for the answer, but as Jacob said, the elements in the chains need not be adjacent... My first thought as well :) –  shamovic Mar 22 '11 at 14:08
    
@shamovic: OK. Well then, I answered -some- question :) –  Mitch Mar 22 '11 at 17:00

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.

share|improve this answer
    
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 :) –  shamovic Mar 22 '11 at 19:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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