Sets, Lists and Noncrossing Partitions
Partitions of [n]={1,2,...,n} into sets of lists
are counted by sequence A000262
in the On-Line Encyclopedia of Integer Sequences. They
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.
