Shallow diagonals of triangular tables

[Olivier Gerard]

Dear List members,

First of all, thanks to Wouter for sending
the first real message to this list. As the
list creator, I should have done so for weeks...
Here we are.


Wouter Meeussen wrote:
>
> 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?
>

The very simple form of basic diagonal in the case of the Pascal and of the
Catalan triangle are mainly the result of numerous symmetries (my name for
coincidence, acknowledged by the numerous combinatorial identities known)
in the formula of the base triangle and in/with respect to the
.transformation. process (in this case, sum of diagonals).

In general, one can systematically derive combinatorial interpretations
by combining previous ones. In the case you describe, it is not important
(though helpful for further work) to have a closed form. But a recurrence
relation can be a good help for another point: inclusion of objects.

What we need is a starting combinatorial interpretation of the diagonal.
But as the sequel shows, we take advantage of the combinatorial
interpretation of the relations between the two parameters of the triangle.

To start, let's have a naive look (I mean that there could be a more
technical and systematic view on this, worth for more complicated examples,
along the lines of the poset view of combinatorics such as synthetized by
Rota. See for reference Richard Stanley's excellent book, Enumerative
Combinatorics, Cambridge, vol.1) at summing a diagonal in the Pascal
triangle, using a classic combinatorial interpretation of its entries.

If we view C(n,k) as the number of n bits word with k ones (dually k zeros).
The shallow diagonal quoted by Wouter correspond to
Sum C(n-i,i)   (i,0->n)

Apparently we add up collections of words of different length. Here we take
advantage of a natural inclusion of each horizontal line of the triangle
into the next (n-1 bits words are subwords of n bits words). Indeed one way
to relate all these words, is to suppose that we have always n bits (the
maximum) but each time we set a bit to one, we impose to have at least a
zero to accompagny it, thus restricting the possibilities. So the
combinatorial interpretation of this diagonal sum becomes (for instance,
many variations are possible)
"the number of n-bit words starting with a number of 0s equal or superior
to the
number of 1s" (or vice-versa).

One can relate this interpretation to the variable-length coding used in
classical compression schemes, where Fibonacci numbers appear immediately.

Note that we have used implicitely several times the inclusion of
smaller words in bigger ones and that we have been forced to break
the symmetry of the formula when chosing an interpretation (0 or 1, starting
or ending or another general scheme of inclusion, ...).

I pretend that it is always possible to find combinatorial interpretations
of such regular extractions, summations, products of triangles. But each
time you will need to have a good model of your objects, the best being a
model where you can map uniformly any element of the triangle as a subset
of the objects counted by a bigger element.

The existence of a (linear) recurrence relation is a proof of an embedding
of smaller objects into bigger ones. To be able to have a combinatorial
interpretation of a specific extraction/combination you will need a
combinatorial interpretation of a recurrence relation that use axes and
operations compatible with your procedure. Non linear relations can require
further
work to be interpreted.

In the case of the Catalan numbers, there are plenty of choices. Richard P.
Stanley, whom I quoted above, has compiled a list of 50+ interpretations of
these numbers for his forthcoming 2nd vol of Enum. Combinatorics.
I think it is still available at his web's page. I will post the address
as soon as I have the opportunity to do it. But the point is, many of
these interpretations are of a recursive nature (graphs, parenthesings,
expressions ... ) to which you can apply ideas similar to what I used
for the Pascal triangle.


Let's make a beauty contest for this one:

>From Wouter Meeussen:

Wanted
a combinatorial interpretation
of 1,1,3,7,20,59,184,593,1964,6642  or any linear diagonal sum taken from the
Catalan triangle.

Good luck to all,


Olivier