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

Question

I have a set with $N$ members $\{1,2, \dots, N\}$. I would like to know number of set partitions in which each subset is either of size $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

This is equal to the number of involutions in the symmetric group $S_n$ (permutations whose square is the identity), via the correspondence that associates to such an involution its set of orbits. The exponential generating function for these numbers $f_n$ is $$ \sum_{n\in\Bbb N}f_n\frac{X^n}{n!}=\exp\left(X+\frac{X^2}2\right) $$ where one may interpret the term $X$ in the argument of $\exp$ as the fact that fixed points are allowed, and the term $\frac{X^2}2$ as the fact that $2$-cycles are allowed. This number is also the number of standard Young tableaux of size$~n$. (This is actually one of the first exercises in Stanley's Enumerative Combinatorics book, IIRC.)

Answer 2

Explanation of recurrence relation mentioned by @bof.

Denote the number of these partitions by $p_{N}$.

Then $p_{0}=p_{1}=1$. For $n\geq2$ we have the relation:

$$p_{n}=\left(n-1\right)p_{n-2}+p_{n-1}$$

There are $p_{n-1}$ partitions such that $\{1\}$ is one of its elements.

They are induced by the sortlike partitions of $\{2,\dots,n\}$.

For $k=2,\dots,n$ there are $p_{n-2}$ partitions such that $\{1,k\}$ is one of its elements.

They are induced by the sortlike partitions of $\{2,\dots,k-1,k+1,\dots n\}$.

Answer 3

This is OEIS sequence A000085. Here is a table of values. There is a recurrence $p_n=p_{n-1}+(n-1)p_{n-2}$. The exponential generating function is $\exp(x+\frac12x^2)$.

This sequence has come up before, here and here and here and here and here.

More generally, given sets $A\subseteq\{0,1,2,3,\dots\}$ and $B\subseteq\{1,2,3,\dots\},$ if $p_n$ counts the partitions of $\{1,2,\dots,n\}$ subject to the conditions that the number of cells belongs to $A$ and the size of each cell belongs to $B$, then the exponential generating function is $$\sum_{n=0}^\infty\frac{p_nx^n}{n!}=e_A(e_B(x))$$ where $$e_S(x)=\sum_{n\in S}\frac{x^n}{n!}.$$