Skip to content

Catalan and Bell

Catalan VS Bell

一、在阅读 wikipedia Partition of a set 时,其中的 "Counting partitions" 中列举了计算它们的方法。

二、给定一个sequence、set,对它进行划分,是否能够交叉

1、能够交叉→bell number

2、不能够交叉→Catalan number

stackexchange Catalan Numbers vs Bell Numbers

A

Among the many things counted by the nnth Catalan number is the number of non-crossing partitions of an ordered set of nn elements.

Since every non-crossing partition is, in particular, a partition, the number of non-crossing partitions cannot exceed the number of partitions, which is the nnth Bell number.