A certain type of combinatorial identity, involving de Montmort numbers

Question

It would lead me too far to explain how I stumbled upon the somewhat obscure identities $$\sum_{m=0}^n \binom{n}{m} (1-m)^m m^{n-m}=(-1)^n d_n, \quad \sum_{m=0}^n \binom{n}{m} (1-m)^{m-1} m^{n-m}=1,$$ where $d_n=n!\sum^{n}_{k=0} (-1)^k /k!$ is the $n$-th de Montmort number, when doing some algebro-geometric considerations. No doubt they are well-known to professional combinatorialists. As stated, they look rather unmotivated; surely they are special cases of a much broader class of identities. Ideally I would like to get a reference for the latter.

Answer 1

In John Riordan's book Combinatorial Identities, page 21, is the formula $$\sum_{k=0}^n \binom{n}{k}(x+k)^k (y+n-k)^{n-k}= \sum_{k=0}^n \binom{n}{k} k!\, (x+y+n)^{n-k}.$$ (There is a typo in the formula given in the book—this is the correct version.) Riordan writes, "This is usually called Cauchy's formula," but I don't know of a reference to Cauchy's work. The case $x=-1, y=-n$ is the OP's first formula.

Sections 1.5 and 1.6 of Riordan's book are devoted to Abel-type formulas.

Answer 2

The first formula is due to Herbert Ryser, who derived it from an inclusion-exclusion formula for the permanent of a matrix. It can be found in his book Combinatorial Mathematics, Mathematical Association of America, Washington, D. C., 1963. I don't have my copy available so I can't tell you exactly where in the book it is. A proof of Ryser's formula and a generalization to Latin rectangles can be found in Peter G. Doyle, The number of Latin rectangles, arXiv:math/0703896 [math.CO], https://arxiv.org/abs/math/0703896, section 3.

Answer 3

Here is a way to generalize these identities. Abel's binomial theorem generalizes the second one as follows

$$\sum_{k=0}^n \binom{n}{k}a(a-kt)^{k-1}(b+kt)^{n-k}=(a+b)^n$$

Your identity follows by specializing $a=1, b=0, t=1$. Using Abel's binomial theorem and some umbral calculus you can generalize the fist identity as well. This is done in the paper "$\lambda$-factorials of $n$" by Sun and Zhuang.

Define the polynomials $$D_n(x)=\sum_{k=0}^{n}\binom{n}{k}d_{n-k}x^k.$$ Then the following Abel type identity holds $$\sum_{k=0}^n\binom{n}{k}(x+k)^k(y-k-1)^{n-k}=D_n(x+y)$$ Your identity follows by specializing $x=y=0$.

Answer 4

The second identity is the special case $x=1$, $z=1$, $y=0$ of Abel's generalization of the binomial theorem, as stated in Enumerative Combinatorics, vol. 2, Exercise 5.31(c). This identity states that $$ (x+y)^n = \sum_{k=0}^n{n\choose k}x(x-kz)^{k-1}(y+kz)^{n-k}. $$