Statistics of Partial Permutations via Catalan matrices

Abstract

A generalized Catalan matrix $(a_{n,k}{)}_{n,k\ge 0}$ is generated by two seed sequences $\mathbf{s}=(s_0,s_1,\dots )$ and $\mathbf{t}=(t_1,t_2,\dots )$ together with a recurrence relation. By taking $s_{\ell }=2\ell +1$ and $t_{\ell }={\ell }^2$ we can interpret $a_{n,k}$ as the number of partial permutations, which are $n\times n$ $0,1$-matrices of $k$ zero rows with at most one $1$ in each row or column. In this paper we prove that most of fundamental statistics and some set-valued statistics on permutations can also be defined on partial permutations and be encoded in the seed sequences. Results on two interesting permutation families, namely the connected permutations and cycle-up-down permutations, are also given.

22 pages