Shallow diagonals of triangular tables
Wouter Meeussen
w.meeussen.vdmcc at vandemoortele.be
Fri Feb 27 16:33:37 CET 1998
hi all,
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.
NV Vandemoortele Coordination Center
Oils & Fats Applied Research
Prins Albertlaan 79
Postbus 40
B-8870 Izegem (Belgium)
Tel: +/32/51/33 21 11
Fax: +/32/51/33 21 75
vdmcc at vandemoortele.be
More information about the SeqFan
mailing list