On trees and noncrossing partitions

We give a simple and natural proof of (an extension of) the identity P(k, l, n) = P-2(k - 1, l - 1, n - 1). The number P(k, l, n) counts noncrossing partitions of {1,2,..., l} into n parts such that no part contains two numbers x and y, 0 < y - x < k. The lower index 2 indicates partitions with no part of size three or more. We use the identity to give quick proofs of the closed formulae for P(k, l, n) when k is 1, 2, or 3. (C) 1998 Elsevier Science B.V. All rights reserved.