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₀ ≤ b₁ ≤..., let f(n) be the number of nondecreasing integer sequences 0 ≤ a₀ ≤ a₁≤ ... ≤ 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.