Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Combinatorics Seminar

Stephen DeSalvo

UCLA

Non-attacking rooks, Stirling numbers, and filling a gap with Poisson approximation

Abstract:

Given a rectangular board B with any set of forbidden states, the rook number $r_B(k)$ is the number of ways of placing k non-attacking rooks on board $B$ which avoid the set of forbidden states. When non-attacking only means no two rooks lie in the same column, the number of such configurations is called the file number, $f_B(k)$. When the board $B$ is the staircase board, with row lengths $n-1, n-2, ..., 1$, then the rook number coincides with the Stirling numbers of the second kind, and the file number coincides with the unsigned Stirling numbers of the first kind. We will demonstrate, using Poisson approximation and an explicit coupling, how one can obtain quantitative bounds on rook and file numbers under certain conditions. In the case of Stirling numbers, our results fill a gap in a recent asymptotic expansion which uses explicitly defined parameters due to Louchard. This is joint work with Richard Arratia.

Host: Brendon Rhoades

November 10, 2016

2:00 PM

AP&M 6402

****************************