Recursively defined combinatorial functions:
Extending Galton's board

Erich Neuwirth

University of Vienna, Austria

January 17,
4:15pm
refreshments at 3:45pm
2-338

ABSTRACT 

We will study recursively defined functions of the type

F(n,k)=a(n-1,k)*F(n-1,k)+b(n-1,k-1)*F(n-1,k-1),
which will be called Galton schemes with generators a(n,k) and b(n,k). Galton schemes can be seen as infinite triangular matrices, and therefore we can ask the question if the generators of a matrix product can be obtained through simple operations from the generators of the factors. Additionally, results about generators of the identity matrix can be used to derive inversion results about Galton schemes. Our general theorems unify many known results about Binomial coefficients, Stirling numbers, and similar well known combinatorial functions, and in particular many of the inversion results about theses functions turn out to be special cases of our general approach.

Our results are, however, more general. They also allow decomposition of certain Galton schemata into matrix products of simpler structures.

Somewhat surprisingly, the proof techniques are mainly applications of elementary linear algebra methods.


Speaker's Contact Info: erich.neuwirth(at-sign)univie.ac.at


Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on January 12, 2001 at 03:02 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.