Counting set partitions by the number of movable letters

摘要

A movable letter within a sequence belonging to a class is one that may be transposed with its predecessor while staying within the class.Weconsider in this paper the problem of counting finite set partitions by the number of movable letters in their canonical sequential representations. A further restricted count on the set P(n, k) of partitions of [n] = {1, 2, . . . , n} with k blocks is given wherein it is required that no two equal letters be transposed. Explicit formulas for the associated exponential generating functions and for the totals of the respective statistics over all members of P(n, k) are found. To establish several of our results, we solve explicitly various linear partial differential equations. Finally, some comparable results are found for the class of non-crossing partitions of [n] where in this case we focus instead on the ordinary generating functions of the associated distributions.