### DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the

Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

**Co-organizers:**
**Andrew Baxter**, Rutgers University, baxter{at} math [dot] rutgers [dot] edu
** Doron Zeilberger**, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Counting nondecreasing integer sequences that lie below a barrier

Speaker: **Herbert Wilf**, University of Pennsylvania

Date: Thursday, April 30, 2009 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Given a barrier * 0 ≤ b*_{0} ≤ b_{1} ≤..., let *f(n)* be the number of nondecreasing integer sequences *0 ≤ a*_{0} ≤ a_{1}≤ ... ≤ a_{n} for which *a*_{j} ≤ b_{j} for all *0 ≤ j ≤ n*.
Known formulae for *f(n)* include an n-by-n determinant whose entries are binomial coefficients (Kreweras, 1965) and, in the special case of *b*_{j} = rj+s, a short explicit formula (Proctor, 1983).
A relatively easy bivariate recursion, decomposing all sequences according to *n* and *a*_{n}, leads to a bivariate generating function, then a univariate generating function, then a linear recursion for * { f(n) } *. Moreover, the coefficients of the bivariate generating function have a probabilistic interpretation, leading to an analytic inequality which is an identity for certain values of its argument.