Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

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


Given a barrier 0 ≤ b0 ≤ b1 ≤..., let f(n) be the number of nondecreasing integer sequences 0 ≤ a0 ≤ a1≤ ... ≤ an for which aj ≤ bj 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 bj = rj+s, a short explicit formula (Proctor, 1983). A relatively easy bivariate recursion, decomposing all sequences according to n and an, 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.