Séminaire Lotharingien de Combinatoire, B62a (2009), 8 pp.

Anisse Kasraoui

d-Regular Set Partitions and Rook Placements

Abstract. We use a classical correspondence between set partitions and rook placements on the triangular board to give a quick picture understanding of the "reduction identity"

|P(d)(n,k)| = |P(d-j)(n-j,k-j)|,

where P(d)(n,k) is the collection of all set partitions of [n]:={1,2,...,n} into k blocks such that for any two distinct elements x,y in the same block, we have |y-x| >= d. We also generalize an identity of Klazar on d-regular noncrossing partitions. Namely, we show that the number of d-regular l-noncrossing partitions of [n] is equal to the number of (d-1)-regular enhanced l-noncrossing partitions of [n-1].

Received: March 7, 2009. Accepted: May 3, 2009. Final Version: July 2, 2009.

The following versions are available: