对于具有 N 个成员的集合，每个子集的大小为 1 或 2 的集合分区的数量是多少？
For a set with N members, what is the number of set partition in which each subset is either size of 1 or 2?
我有一个包含 N 个成员 {1,2,.. N} 的集合。我想知道每个子集的大小为 1 或 2 的集合分区的数量，即分区中每个子集的基数最大为 2。例如，N=3 .. 我们有最大大小为 2 的集合分区是 {1,2,3}, {(1,2),3)}, {1,(2,3)}, {(1,3),2}。但是我对 {(1,2,3)} 不感兴趣，因为它的长度为 3。请告诉我具有 N 个成员的集合的此类集合分区的数量。
令一组基数 n 的此类分区数为 p(n)。
该集合的第一个元素可以在基数 1 的子集中，留下剩余元素的 p(n-1) 个分区，或者它可以与其他 n-1 个元素配对，留下 p(n-2)剩余元素的可能分区。所以我们有
p(n) = p(n-1) + (n-1)*p(n-2)
显然：p(1) = 1 和 p(2) = 2
因此p(3) = 2 + 2*1 = 4
https://oeis.org/A000085 "a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2"
我有一个包含 N 个成员 {1,2,.. N} 的集合。我想知道每个子集的大小为 1 或 2 的集合分区的数量，即分区中每个子集的基数最大为 2。例如，N=3 .. 我们有最大大小为 2 的集合分区是 {1,2,3}, {(1,2),3)}, {1,(2,3)}, {(1,3),2}。但是我对 {(1,2,3)} 不感兴趣，因为它的长度为 3。请告诉我具有 N 个成员的集合的此类集合分区的数量。
令一组基数 n 的此类分区数为 p(n)。
该集合的第一个元素可以在基数 1 的子集中，留下剩余元素的 p(n-1) 个分区，或者它可以与其他 n-1 个元素配对，留下 p(n-2)剩余元素的可能分区。所以我们有
p(n) = p(n-1) + (n-1)*p(n-2)
显然：p(1) = 1 和 p(2) = 2
因此p(3) = 2 + 2*1 = 4
https://oeis.org/A000085 "a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2"