Return to Revisions

Denote by $f(n,m)=M(n+m,m;2)/m!$ the number of partitions of $\{1,2,\dots,n+m\}$ onto $m$ subsets of size at least 2. Your identity rewrites as $A(n):=\sum_{j\geqslant 1} f(n,j)=(-1)^nn!$. We have $f(n,m)=mf(n-1,m)+(n+m-1)f(n-1,m-1)$: the first summand corresponds to the partitions in which $n+m$ belongs to a subset of size at least 3; the second to the partitions in which $n+m$ belongs to a subset of size 2. Substitute this to $A(n)$ we get $A(n)=-nA(n-1)$ and your identity follows by induction (with base $n=1$, say).