For a set with N members, what is the number of set partition in which each subset is either size of 1 or 2?

Question

I have a set with N members {1,2,.. N}. I like to know number of set partition in which each subset is either size of 1 or 2, i.e., cardinality of each subset in the partition is maximum 2. For example with N=3.. we have the set partitions of maximum size 2 are {1,2,3}, {(1,2),3)}, {1,(2,3)}, {(1,3),2}. However I am not interested in {(1,2,3)} since it is of length 3. Kindly tell me number of such set partitions for a set with N members.

Answer 1

Let the number of such partitions of a set of cardinality n be p(n). The first element of the set can either be in subset of cardinality 1, leaving p(n-1) partitions of the remaining elements, or it can be paired with one of the other n-1 elements, leaving p(n-2) possible partitions for the remaining elements. So we have

p(n) = p(n-1) + (n-1)*p(n-2)

Obviously: p(1) = 1 and p(2) = 2

And therefore 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"