6
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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
    Commented May 1, 2018 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
    Commented May 1, 2018 at 7:29
  • $\begingroup$ By the way, where does the problem come from? $\endgroup$
    – darij grinberg
    Commented May 1, 2018 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
    Commented May 1, 2018 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
    Commented May 1, 2018 at 18:07

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ There should be an alternating sign in your sum, right? $\endgroup$
    – Per Alexandersson
    Commented May 1, 2018 at 10:33
  • $\begingroup$ @PerAlexandersson yes, thank you, fixed $\endgroup$
    – Fedor Petrov
    Commented May 1, 2018 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
    Commented May 1, 2018 at 14:55
  • $\begingroup$ @Fedor : we thanked you for the proof, ref : arxiv.org/pdf/1609.06022.pdf $\endgroup$
    – Siddhartha
    Commented May 10, 2018 at 5:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .