[seqfan] Re: Shallow diagonals of triangular tables
Christian G.Bower
bowerc at usa.net
Fri Apr 10 17:20:59 CEST 1998
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
More information about the SeqFan
mailing list