Journal of Integer Sequences, Vol. 11 (2008), Article 08.1.3

Sets, Lists and Noncrossing Partitions

David Callan
Department of Statistics
University of Wisconsin-Madison
1300 University Ave.
Madison, WI 53706-1532


Partitions of [n] = {1,2,...,n} into sets of lists (A000262) are somewhat less numerous than partitions of [n] into lists of sets (A000670). Here we observe that the former are actually equinumerous with partitions of [n] into lists of noncrossing sets and give a bijective proof. We show that partitions of [n] into sets of noncrossing lists are counted by A088368 and generalize this result to introduce a transform on integer sequences that we dub the "noncrossing partition" transform. We also derive recurrence relations to count partitions of [n] into lists of noncrossing lists.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000108 A000110 A000262 A000670 A001263 A002866 A006906 A088368 and A105278 .)

Received October 2 2007; revised version received February 5 2008. Published in Journal of Integer Sequences, February 5 2008.

Return to Journal of Integer Sequences home page