How do I prove :

$\sum_{j=2}^{n} (-1)^j {\frac {M(n+j,j;2)}{j!}} = (-1)^n n! + 1$?

where $M(n+j,j;2)$ is the multinomial sum $M(n+j,j;2) = \sum_{t_1 + t_2 + \dotsc + t_j = n+j, t_k \geq 2} {n+j \choose t_1 \dotsc t_k}$ which denotes the number of surjective functions from $n+j$ points to $j$ points with at least two elements in each pre-image.

I have tried using the recursion formulas of counting doubly surjective functions which didn't help much. My thought was the alternate signs appear for some Moebius maps on some partial order on the disjoint set of surjective maps from $n+j$ points to $j$ points up to permuting the image points (which explains division by $j!$). My definition of reshuffling images which give a partial order which give $0$ to distant points.

  • 1
    $\begingroup$ Note: $\dfrac{M\left(n+j,j;2\right)}{j!}$ is the number of set partitions of the set $\left\{1,2,\ldots,n+j\right\}$ into $j$ subsets, each of which has at least $2$ elements. Not saying that this helps, but it might be a first step. $\endgroup$ – darij grinberg May 1 '18 at 7:28
  • $\begingroup$ I would really like an inclusion-exlcusion-style argument for this. Perhaps multiplying both sides with n! makes it easier? Also, what is the j=1-term? Is it 0? $\endgroup$ – Per Alexandersson May 1 '18 at 7:29
  • $\begingroup$ By the way, where does the problem come from? $\endgroup$ – darij grinberg May 1 '18 at 7:32
  • 1
    $\begingroup$ The safest approach I see, by the way, is to rewrite $M\left(n+j,j;2\right)$ in terms of Stirling numbers using inclusion-exclusion. $\endgroup$ – darij grinberg May 1 '18 at 7:35
  • $\begingroup$ @Darij : I was trying to estimate some error term of some characteristic coefficients of a Taylor series which come from lower bound on largest eigenvalues of a symmetric matrix (due to Walker and Mieghem, 2008). This sum appeared as in each of the error terms of inverse of exponential map combined with power matrices. $\endgroup$ – Siddhartha May 1 '18 at 18:07

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

| cite | improve this answer | |
  • $\begingroup$ There should be an alternating sign in your sum, right? $\endgroup$ – Per Alexandersson May 1 '18 at 10:33
  • $\begingroup$ @PerAlexandersson yes, thank you, fixed $\endgroup$ – Fedor Petrov May 1 '18 at 11:24
  • $\begingroup$ There doesn't seem to be a corresponding sequence on OEIS ($2,0,3,-5,25,-119,721,-5039...$) if you are inclined to author a new entry. $\endgroup$ – Ben Burns May 1 '18 at 14:55
  • $\begingroup$ @Fedor : we thanked you for the proof, ref : arxiv.org/pdf/1609.06022.pdf $\endgroup$ – Siddhartha May 10 '18 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.