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.
Received October 2 2007;
revised version received February 5 2008.
Published in Journal of Integer Sequences, February 5 2008.