Sequence counting question

[franktaw at netscape.net]

I've gotten a little further on this.  This sequence can be generated as the row sums of the triangle defined by: a(n,m) = a(n-1,m-1) + a(n-1,m) + m * a(n-1,m+1).  This triangle starts:
1
1 1
2 2 1
4 6 3 1
10 16 12 4 1
26 50 40 20 5 1
 
a(n,m) is that number of sequences of length n which will limit the continuation to size n+1 to a maximum value of m+1.  Using this, I have verified the match with A005425 for 18 terms.
 
This triangle also appears to be in the OEIS: it is A111062.  However, A111062 does not have the formula above, and I don't see how to establish it.  (Incidently, A111062 has a typo - the third from the last term should be 72, not 42.  The value 72 is shown correctly in the example.)
 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645
 
 
-----Original Message-----
From: franktaw at netscape.net
To: seqfan at ext.jussieu.fr
Sent: Wed, 21 Dec 2005 22:20:42 -0500
Subject: Sequence counting question


Consider finite sequences of positive integers <b(m)> of length n with b(1)=1, and with the constraint that b(m) <= max_{0<k<n} b(k)+k-n+2.  The question is how many such sequences there are.
 
(Note that when we consider only the term k=m-1, this becomes b(m) <= b(m-1)+1, and it is well known that the number of sequences under this constraint is the Catalan numbers.)
 
This sequence starts (from n = 1) 1,2,5,14,43,142,499,1850,7193.
 
This appears to be A005425 (this many terms matching is not going to be a coincidence).  But I don't see any way to prove it.
 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645


Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com 
___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20051221/61033f6f/attachment-0001.htm>