[seqfan] Re: Shallow diagonals of triangular tables

[Christian G.Bower]

I finally figured out how to get old submissions from the server.

I looked at Wouter Meeussen's problem of the other shallow diagonal
of the Catalan triangle and I think I have an interpretation (although
it's a bit contrived.)

Meeussen's sequence 1,1,3,7,20,59,184,593... is the INVERT
transform of (starting at index 1) 1,2,2,5,14,42,132...

i.e., take the Catalan numbers A000108, shift one place right and
make the index 2 term a 2 instead of a 1.

(If a sequence a(n) has g.f. A(x) then the INVERT transform has
g.f. A(x)/(1-A(x)))

Since the Catalan numbers have many interpretations, this leads to
many interpretations of Meeussen's sequence.

Here's one using the right shifted Catalan numbers as planar planted
trees of n nodes not counting the root.

The number of linear forests (i.e. union of trees) of planted planar
trees of n nodes not counting the roots where trees of exactly 2
non-root nodes come in 2 colors.

That's the best I can do for now. I don't have anything to say about
the more general question.

Christian


> the EIS contains a number of tiangular tables like Pascal's triangle.
> Sometimes, the shallow diagonal sums have obvious special properties,
> sometimes not.
> 
> example:
>
>                                 1
>                               1   1
>                             1   2   1
>                           1   3  +3  (1)
>                         1  +4  (6)  4   1
>                      +1  (5)  10  10  5   1  
>                    (1)
> 
> gives shallow diagonal 1,1,2,3,5,+8,(13),21,... the Fibonacci numbers.
> 
> An other triangular table, a favorite of mine, the Catalan triangle, has as
> shallow diagonal sum the central binomial coefficients Binomial[n,Floor[n/2]]:
> 
>                                  1
>                                1,  1
>                              1,  2,  2
>                            1,  3,  5, (5)
>                          1,  4, (9)  14, 14
>                        1, (5)  14,  28,  42, 42
>                     (1)  6,  20,  48,  90, 132, 132
> 
> 
> shallow diagonal sum : 1,1,2,3,6,10,(20),35,70,126,252 ...
> Since for both these triangles, the non-recursive form of each entry is known
> (* Pascal's : Binomial[n,m] ; Catalan's: Binomial[n+m,n](n-m+1)/(n+1) ; *)
> thus also the shallow diagonal has a simple form;
> 
> in Mathematica, it is Sum[ triangle[n-k,k-1],{k,1,Floor[(n+1)/2]}]
> with triangle[n,k] the n-th row and the k-th column in the triangle.
> 
> The "opposite" sloping shallow diagonal (top left to bottom right) has the
> form:
> Sum[triangle[n-k,(n-k)-(k-1)],{k,1,Floor[(n+1)/2]}]
> and for a non-symmetrical triangle like Catalan's it is of course different:
>  1,1,3,7,20,59,184,593,1964,6642,22845,79667,281037,1001092,3595865 ...
> but this does not appear to "count" any known combinatorial objects.
> 
> QUESTION:
> 
> If a triangular table has both a recurrence relation and a closed form,
> and is related to the counting of some combinatorial type of object,
> does this imply that the "Shallow Diagonals" have a combinatorial
> significance?
> 
> In other words, are the simple forms obtained for Pascal's and Catalan's
> triangle just coincidence ? What about the other triangular tables in EIS?
> 
> wouter.


____________________________________________________________________
Get free e-mail and a permanent address at http://www.netaddress.com