Enumerating finite set partitions according to the number of connectors

Abstract

Let $P(n,k)$ denote the set of partitions of $[n]=\{1,2,\dots ,n\}$ containing exactly $k$ blocks. Given a partition $\mathrm{\Pi }=B_1/B_2/\cdots /B_k\in P(n,k)$ in which the blocks are listed in increasing order of their least elements, let $\pi ={\pi }_1{\pi }_2\cdots {\pi }_n$ denote the canonical sequential form wherein $j\in B_{{\pi }_j}$ for all $j\in [n]$. In this paper, we supply an explicit formula for the generating function which counts the elements of $P(n,k)$ according to the number of strings $k1$ and $r(r+1)$, taken jointly, occurring in the corresponding canonical sequential forms. A comparable formula for the statistics on $P(n,k)$ recording the number of strings $1k$ and $r(r-1)$ is also given, which may be extended to strings $r(r-1)\cdots (r-m)$ of arbitrary length using linear algebra. In addition, we supply algebraic and combinatorial proofs of explicit formulas for the total number of occurrences of $k1$ and $r(r+1)$ within all the members of $P(n,k)$.