E.G.F. Challenge for New Triangle A102316

Wed Jan 5 16:33:58 CET 2005

Wouter, 
     Your insightful approach prompts me to show 
just how relevant your q-recurrence really is.  

It is related to triangle A102086, a solution to a certain 
recursive matrix equation. 

Below I describe how that each column q of A102086 is equal to 
the main diagonal of a triangle generated by the recurrence: 

(1) T(0,0)=(q+1), T(n,k) = T(n,k-1) + (k+q)*T(n-1,k),
    T(n,n) = T(n,n-1) for n>0

the very form of which you had intuitioned!

The triangular matrix M given by:
http://www.research.att.com/projects/OEIS?Anum=A102086
1,
1, 2,
3, 4, 3,
16, 20, 9, 4,
127, 156, 63, 16, 5,
1363, 1664, 648, 144, 25, 6,
18628, 22684, 8703, 1840, 275, 36, 7,
311250, 378572, 144243, 29824, 4200, 468, 49, 8,
...
is a triangular matrix solution of the equation:

(2)  M^2 = SHIFTUP(M)

where SHIFTUP denotes shifting each column up 1,
so in effect drops the main diagonal: 
M^2 =
1, 
3, 4, 
16, 20, 9, 
127, 156, 63, 16, 
1363, 1664, 648, 144, 25,   
...

Any matrix solution to equation (2) is completely determined 
by the elements along the main diagonal. 

In the solution given by A102086, M has the diagonal {1,2,3,...}.

As a simple example, if we let the diagonal be {1,1,1,1,...},
then the solution is M =
1,
1, 1,
2, 1, 1,
5, 2, 1, 1,
14, 5, 2, 1, 1,
...
which has of course the Catalan sequence in column 0. 

(This is why your q-series triangle has Catalan in the diagonal.) 

Amazingly, the matrix solution to the equation:

(3)  M^3 = SHIFTUP(M) 

where the main diagonal of M is {1,2,3,...} 
is the triangular matrix given by: 
http://www.research.att.com/projects/OEIS?Anum=A102098

which also has, as column 0, Valery's other sequence!
and that is: 
http://www.research.att.com/projects/OEIS?Anum=A082162

Now back to the discussion of matrix solutions of equation (2).

By examining the contribution of the diagonal elements of M 
to the terms in the columns, we arrive at a triangle of 
coefficients for each column in M. 

That is how I arrived at the triangle A102316 - it is
the triangle associated with column 0 of A102086: 
1,
1, 1,
1, 3, 3,
1, 7, 16, 16,
1, 15, 63, 127, 127,
1, 31, 220, 728, 1363, 1363,
...

The triangle for column 1 of A102086 is:
2,
4, 4,
8, 20, 20,
16, 76, 156, 156,
32, 260, 884, 1664, 1664,
64, 844, 4380, 12700, 22684, 22684,
...
the main diagonal of which equals column 1 of A102086.

The triangle for column 2 of A102086 is:
3,
9, 9,
27, 63, 63,
81, 333, 648, 648,
243, 1575, 4815, 8703, 8703,
729, 7029, 31104, 83322, 144243, 144243,
...
The main diagonal of which equals column 2 of A102086.

etc.

Thus, if a nice e.g.f. for A102316 be found, 
then an e.g.f for A102086 would immediately follow. 

And it is possible that knowing the e.g.f. for A10286 could 
lead to the e.g.f. for all solutions to the equation

   M^n = SHIFTUP(M).

Thanks,
    Paul

========================================================
-- "Meeussen Wouter (bkarnd)" <wouter.meeussen at vandemoortele.com> wrote:
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.