Skip to main content
added 33 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

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 (observation of Darij Grinberg). Your identity rewrites as $A(n):=\sum_{j\geqslant 1} (-1)^jf(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).

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} (-1)^jf(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).

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 (observation of Darij Grinberg). Your identity rewrites as $A(n):=\sum_{j\geqslant 1} (-1)^jf(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).

added 6 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

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!$$A(n):=\sum_{j\geqslant 1} (-1)^jf(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).

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).

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} (-1)^jf(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).

Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

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).