E.G.F. Challenge for New Triangle A102316

[Meeussen Wouter (bkarnd)]

small step:
q-ify the recurrence:
T[n_,k_] := T[n,k]= Expand[T[n,k-1] + (k+q)*T[n-1,k]]; T[n_,n_]:=T[n,n-1]; T[n_,0]:=1;

and write T[n,n] as polynomial in q
{1, 2 + q, 7 + 7*q + 2*q^2, 7 + 7*q + 2*q^2, 39 + 55*q + 28*q^2 + 5*q^3, ..}
..
giving a triangle again:
{1}
{2, 1}
{7, 7, 2}
{39, 55, 28, 5}
{314, 545, 373, 117, 14}
{3388, 6769, 5587, 2346, 496, 42}
{46409, 102792, 96816, 49029, 13962, 2110, 132}
{776267, 1862149, 1937475, 1121599, 387390, 79514, 8968, 429}

with the catalans on the diagonal.
Does that help any?

W.

-----Original Message-----
From: liskov [mailto:liskov at im.bas-net.by]
Sent: woensdag 5 januari 2005 11:24
To: Paul D. Hanna; Seqfan
Subject: Re: E.G.F. Challenge for New Triangle A102316



> "Paul D. Hanna" wrote:
> 
> Here is a nice E.G.F.-challenge to all of you Exceptionally Gifted Folks ...
> 
> Valery Liskovets has a nice sequence (along with formula):
> http://www.research.att.com/projects/OEIS?Anum=A082161
> 1,3,16,127,1363,18628,311250,6173791,142190703,3737431895,
> 110577492346,3641313700916,132214630355700,5251687490704524,
> 226664506308709858
> 
> I have by chance found a triangle that is related to A082161
> with a recurrence that is begging for a nice E.G.F. to come along ...
> 
> The triangle is as follows:
> 1,
> 1,1,
> 1,3,3,
> 1,7,16,16,
> 1,15,63,127,127,
> 1,31,220,728,1363,1363,
> 1,63,723,3635,10450,18628,18628,
> 1,127,2296,16836,69086,180854,311250,311250,
> 1,255,7143,74487,419917,1505041,3683791,6173791,6173791,
> ...
> and has the simple recurrence:
> 
> T(n,k) = T(n,k-1) + (k+1)*T(n-1,k) for n>k>0,
> with T(n,0)=1 for n>=0 and T(n,n)=T(n,n-1) for n>0.
> 
> I just now submitted this triangle to the OEIS as A102316.
> 
> I believe that this triangle should have an interesting E.G.F. ...
> can anyone find one?

In my opinion, this is an unexpected and impressive result, which is also
promising for obtaining asymptotics of A082161. Certainly, the equivalence of both formulae for A082161 needs to be proved. Presently I don't see 
a combinatorial proof of Paul's recurrence. Nor a combinatorial meaning 
of T(n,k), k<n-1, for (unlabeled) acyclic automata. Can anybody succeed?

Valery Liskovets


===============================
This email is confidential and intended solely for the use of the individual to whom it is addressed. 
If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited.
You are explicitly requested to notify the sender of this email that the intended recipient was not reached.