Enumerating finite set partitions according to the number of connectors

Abstract

Let \( P(n, k) \) denote the set of partitions of \( [n] = \{1, 2, \ldots, n\} \) containing exactly \( k \) blocks. Given a partition \( \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) \).