Sequence counting question

[Paul D. Hanna]

Franklin (and Seqfans),
      Let us change the column offset of your recurrence, so that it
becomes 
a(n,m) = a(n-1,m-1) + a(n-1,m) + (m+1)*a(n-1,m+1).  
We can deduce this recurrence from the formulas found in A000085 and
A111062. 
Also, the e.g.f. and matrix log of A111062 are given at the bottom of
this message.  
  
Let B(n) = A000085(n) with B(0)=B(1)=1, 
then we have the recurrence 
(*) B(n) = B(n-1) + (n-1)*B(n-2) for n>=2 .
 
Given the formula found in A111062: 
(**) a(n,m) = C(n,m)*B(n-m)  with a(n,0)=A000085(n)
then your recurrence 
(***) a(n,m) = a(n-1,m-1) + a(n-1,m) + (m+1)*a(n-1,m+1)
can be established as follows.
 
 From (*) and (**) we can state: 
C(n,m)*B(n-m) = C(n,m)*B(n-m-1) + (n-m-1)*C(n,m)*B(n-m-2) .
 
Employ binomial identity: 
(n-m-1)*C(n,m) = (n-m-1)*C(n-1,m-1) + (m+1)*C(n-1,m+1) 
to obtain 
C(n,m)*B(n-m) = [C(n-1,m-1) + C(n-1,m)]*B(n-m-1) + 
      [(n-m-1)*C(n-1,m-1) + (m+1)*C(n-1,m+1)]*B(n-m-2) .
Rearranging,
C(n,m)*B(n-m) = C(n-1,m-1)*[B(n-m-1) + (n-m-1)*B(n-m-2)] +
C(n-1,m)*B(n-m-1) + 
      (m+1)*C(n-1,m+1)*B(n-m-2) .
 
 From (*), [B(n-m-1) + (n-m-1)*B(n-m-2)] = B(n-m), 
thus 
C(n,m)*B(n-m) = C(n-1,m-1)*B(n-m) + C(n-1,m)*B(n-m-1) +
(m+1)*C(n-1,m+1)*B(n-m-2)
which is equivalent to (***).

------------------------------------------------------------------------
E.G.F.  of A111062.
 From Philippe Deleham's formula for A111062: 
  T(n,k) = binomial(n,k)*A000085(n-k) 
and since the E.g.f. of A000085 is: 
  G(x) = exp(x*(2+x)/2) 
then we get the E.g.f. of A111062 to be: 
  E.g.f.: A(x,y) = exp(x*(2+x)/2 + x*y) 
where 
  T(n,k) = n! * [x^n*y^k] A(x,y). 
   
LOG of A111062. 
The matrix log of triangle A111062 is simple: 
0;
1,0;
1,2,0;
0,3,3,0;
0,0,6,4,0;
0,0,0,10,5,0; 
0,0,0,0,15,6,0; ... 
0,0,0,...,0, n*(n-1)/2, n, 0; ...
 
END. 
------------------------------------------------------------------------
On Wed, 21 Dec 2005 22:50:34 -0500 franktaw at netscape.net writes:
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20051222/94f8e397/attachment-0001.htm>