7
$\begingroup$

Today when I solve a counting problem using different methods I find the following (seemingly correct) combinatorial identity, but I can't find it on the Internet and I can't prove its correctness neither. But I have verified its correctness with positive integer $n$ within $[0, 1000]$ using a simple computer program. Anyone can give a proof to this identity (or any link to its proof)?

$$\frac{(n+1)n}{2} \cdot n! = \sum\limits_{k=0}^{n} (-1)^k \cdot \frac{n!}{k!\cdot(n-k)!} \cdot (n-k)^{n+1}$$

And equivalently if you want,

$$\frac{(n+1)n}{2} = \sum\limits_{k=0}^{n} (-1)^k \cdot \frac{1}{k!\cdot(n-k)!} \cdot (n-k)^{n+1}$$

$\endgroup$
  • 2
    $\begingroup$ You have posted a few questions on this site, yet still haven't learnt how to use LaTeX commands? $\endgroup$ – Batominovski Aug 17 '16 at 14:55
  • $\begingroup$ Please check the formula, I've tried to format it properly, might have misunderstood few terms. $\endgroup$ – Evgeny Aug 17 '16 at 15:00
  • 1
    $\begingroup$ you can cancle the n! on each side. $\endgroup$ – miracle173 Aug 17 '16 at 15:03
  • 1
    $\begingroup$ for n=1 the LHS is 1 and the RHS is -1, for n=2 the LHS is 3 and the RHS is -5 $\endgroup$ – miracle173 Aug 17 '16 at 15:13
  • 2
    $\begingroup$ @miracle173 ... I get $1=1$ and $3=3$. $\endgroup$ – GEdgar Aug 17 '16 at 15:22
7
$\begingroup$

The identity can be written

$$n!\binom{n+1}2=\sum_k(-1)^k\binom{n}k(n-k)^{n+1}\;.\tag{1}$$

The righthand side has the look of an inclusion-exclusion calculation, so we can look for a combinatorial interpretation on that basis. If $K$ is a subset of $[n]=\{1,\ldots,n\}$ with $k$ elements, $(n-k)^{n+1}$ can be interpreted as the number of functions from $[n+1]$ to $[n]\setminus K$. If for $k\in[n]$ we let $A_k$ be the set of functions from $[n+1]$ to $[n]\setminus\{k\}$, then for each $K\subseteq[n]$ with $|K|=k$ we have

$$\left|\,\bigcap_{k\in K}A_k\,\right|=(n-k)^{n+1}\;.$$

There are $\binom{n}k$ such subsets of $[n]$, so

$$\begin{align*} \left|\bigcup_{k=1}^nA_k\right|&=\sum_{\varnothing\ne K\subseteq[n]}(-1)^{|K|+1}\left|\,\bigcap_{k\in K}A_k\,\right|\\ &=\sum_{\varnothing\ne K\subseteq[n]}(-1)^{|K|+1}(n-k)^{n+1}\\ &=\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^{n+1}\;. \end{align*}$$

$\bigcup_{k=1}^nA_k$ is the set of functions from $[n+1]$ to $[n]$ that are not surjections, so the number of surjections from $[n+1]$ to $[n]$ must be

$$\begin{align*} n^{n+1}-\left|\bigcup_{k=1}^nA_k\right|&=n^{n+1}-\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^{n+1}\\ &=n^{n+1}+\sum_{k=1}^n(-1)^k\binom{n}k(n-k)^{n+1}\\ &=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^{n+1}\;. \end{align*}$$

To complete the proof of $(1)$ we need only show that there are $n!\binom{n+1}2$ surjections from $[n+1]$ to $[n]$.

If $f:[n+1]\to[n]$ is a surjection, there must be distinct $k,\ell\in[n+1]$ such that $f(k)=f(\ell)$, while $f$ is injective on $[n+1]\setminus\{k,\ell\}$. Let $D=[n+1]\setminus\{\ell\}$; each surjection $g$ from $D$ to $[n]$ extends to a unique surjection $f:[n+1]\to[n]$ with $f(k)=f(\ell)$, the function defined by

$$f(i)=\begin{cases} g(i),&\text{if }i\in D\\ g(k),&\text{if }i=\ell\;. \end{cases}$$

Every surjection $f:[n+1]\to[n]$ such that $f(k)=f(\ell)$ arises in this way from a surjection from $D$ to $[n]$, and $|D|=n$ so there are $n!$ surjections from $D$ to $[n]$ and hence $n!$ surjections $f:[n+1]\to[n]$ such that $f(k)=f(\ell)$. Finally, there are $\binom{n+1}2$ ways to choose the $k$ and $\ell$ that $f$ is to send to the same element of $[n]$, so there are altogether $n!\binom{n+1}2$ surjections from $[n+1]$ to $[n]$.

$\endgroup$
  • $\begingroup$ We can interpret as counting the number of ways of distributing $n+1$ distinct balls into $n$ distinct boxes so that no box is empty. $n-1$ boxes can be chosen in $n$ ways and two balls can be chosen in $\binom{n+1}{2}$ ways. Put the $n-1$ balls in $n-1$ boxes in $(n-1)!$ ways and the two balls in the remaining box. This gives $\binom{n+1}{2} n!$ ways. This gives the left hand side of the equality. $\endgroup$ – user348749 Aug 18 '16 at 2:02
  • $\begingroup$ @Muralidharan: Yes: that’s the same as counting surjections from $[n+1]$ to $[n]$, just in different language. $\endgroup$ – Brian M. Scott Aug 18 '16 at 2:09
  • $\begingroup$ @Muralidharan In fact I found this identity just by using the two methods you posted here. $\endgroup$ – Daniel Aug 18 '16 at 14:01
4
$\begingroup$

Another way is to consider that the backward finite difference (backward Delta) is defined as $$ \nabla _x \,f(x) = f(x) - f(x - 1) $$ and we have that its $n$-th iteration is: $$ \nabla _x ^n \,f(x) = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} n \\ k \\ \end{gathered} \right)\;f(x - k)} $$ therefore the RHS is: $$ \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} n \\ k \\ \end{gathered} \right)\;\left( {n - k} \right)^{n + 1} } = \left. {\nabla _x ^n \,x^{n + 1} } \right|_{\,x = n} $$ Now $x^{\,n + 1} $ is a polynomial of degree $n+1$ and we can express it in terms of the Stirling Numbers of $2$nd kind and Falling Factorials of $x$ as $$ x^{\,n + 1} = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left\{ \begin{gathered} n + 1 \\ k \\ \end{gathered} \right\}\;x^{\,\underline {\,k\;} } } $$ The backward Delta of the falling factorial is given by: $$ \begin{gathered} \nabla _x \;x^{\,\underline {\,m\;} } = \left( {x\left( {x - 1} \right) \cdots \left( {x - m + 1} \right)} \right) - \left( {\left( {x - 1} \right)\left( {x - 2} \right) \cdots \left( {x - m} \right)} \right) = m\left( {x - 1} \right)^{\,\underline {\,m - 1\;} } \hfill \\ \nabla _x ^{\,n} \;x^{\,\underline {\,m\;} } = m^{\,\underline {\,n\;} } \left( {x - n} \right)^{\,\underline {\,m - n\;} } \quad \Rightarrow \quad \nabla _x ^{\,n} \;x^{\,\underline {\,m\;} } = 0\quad \left| {\;m < n} \right. \hfill \\ \end{gathered} $$ therefore: $$ \begin{gathered} \nabla _x ^n \,x^{n + 1} = \nabla _x ^n \,\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left\{ \begin{gathered} n + 1 \\ k \\ \end{gathered} \right\}\;x^{\,\underline {\,k\;} } } = \nabla _x ^n \,\left( {\left\{ \begin{gathered} n + 1 \\ n + 1 \\ \end{gathered} \right\}\;x^{\,\underline {\,n + 1\;} } + \left\{ \begin{gathered} n + 1 \\ n \\ \end{gathered} \right\}\;x^{\,\underline {\,n\;} } } \right) = \hfill \\ = \left( {\left\{ \begin{gathered} n + 1 \\ n + 1 \\ \end{gathered} \right\}\;\left( {n + 1} \right)^{\,\underline {\,n\;} } \left( {x - n} \right)^{\,\underline {\,1\;} } + \left\{ \begin{gathered} n + 1 \\ n \\ \end{gathered} \right\}n^{\,\underline {\,n\;} } \;\left( {x - n} \right)^{\,\underline {\,0\;} } } \right) = \hfill \\ = \left( {1\;\left( {n + 1} \right)^{\,\underline {\,n\;} } \left( {x - n} \right)^{\,\underline {\,1\;} } + \left( \begin{gathered} n + 1 \\ n - 1 \\ \end{gathered} \right)n^{\,\underline {\,n\;} } \;\left( {x - n} \right)^{\,\underline {\,0\;} } } \right) = \hfill \\ = n!\left( {\;\left( \begin{gathered} n + 1 \\ n \\ \end{gathered} \right)\left( {x - n} \right) + \left( \begin{gathered} n + 1 \\ n - 1 \\ \end{gathered} \right)} \right) \hfill \\ \end{gathered} $$ which, calculated at $x=n$ gives: $$ \begin{gathered} \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} n \\ k \\ \end{gathered} \right)\;\left( {n - k} \right)^{n + 1} } = \left. {\nabla _x ^n \,x^{n + 1} } \right|_{\,x = n} = \hfill \\ = n!\left( \begin{gathered} n + 1 \\ n - 1 \\ \end{gathered} \right) = n!\frac{{\left( {n + 1} \right)n}} {2} \hfill \\ \end{gathered} $$ thus proving your assertion, while generalizing it to other values of $x$.

$\endgroup$
4
$\begingroup$

Here is another variation of the theme. It is convenient to use the coefficient of operator $[t^k]$ to denote the coefficient of $t^k$ in a series. This way we can write e.g. \begin{align*} \binom{n}{k}=[t^k](1+t)^n\qquad\text{and}\qquad k^n=n![t^n]e^{kt} \end{align*}

OPs identity can be written as

\begin{align*} \frac{n}{2}(n+1)!=\sum_{k=0}^n&(-1)^k\binom{n}{k}(n-k)^{n+1}\quad\qquad n\geq 0 \end{align*}

We start with the right-hand side and obtain \begin{align*} \sum_{k=0}^n&(-1)^k\binom{n}{k}(n-k)^{n+1}\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^{n+1}\tag{1}\\ &=\sum_{k=0}^\infty(-1)^{n-k}[u^k](1+u)^n(n+1)![t^{n+1}]e^{kt}\tag{2}\\ &=(-1)^n(n+1)![t^{n+1}]\sum_{k=0}^\infty(-e^t)^k[u^k](1+u)^n\tag{3}\\ &=(-1)^n(n+1)![t^{n+1}]\left(1-e^t\right)^n\tag{4}\\ &=(n+1)![t^{n+1}]\left(t+\frac{t^2}{2}+\cdots\right)^n\tag{5}\\ &=\frac{n}{2}(n+1)!\tag{6} \end{align*} and the claim follows.

Comment:

  • In (1) we change the order of summation: $k\longrightarrow n-k$

  • In (2) we apply the coefficient of operator twice. We also extend the range of summation to infinity without changing anything, since we are adding zeros only.

  • In (3) we do some rearrangements and use the linearity of the coefficient of operator.

  • In (4) we use the substitution rule with $u=-e^t$ \begin{align*} A(t)=\sum_{k=0}^\infty a_kt^k=\sum_{k=0}^\infty t^k[u^k]A(u)\\ \end{align*}

  • In (5) we factor out $(-1)^n$ and expand the exponential series.

  • In (6) we note that in order to extract the coefficient of $t^{n+1}$ we have $n$ possibilities to select the term $t$ and one possibility to select the the term $\frac{t^2}{2}$ giving $\frac{n}{2}$.

$\endgroup$
  • $\begingroup$ @MarkoRiedel: Thanks, Marko! Very nice from you. :-) $\endgroup$ – Markus Scheuer Aug 18 '16 at 20:17
  • $\begingroup$ @MarkusScheuer, this is the 2nd time I see you applying the "coefficient of" technique, and again it is impressive how neat and efficient it is. Hope I can get some mastering of it. $\endgroup$ – G Cab Aug 19 '16 at 14:30
  • $\begingroup$ @GCab: A landmark is Egorychev's classic. Easier accessible is this paper. It's funny to detect the efficiency of this method. Yesterday I saw a nice answer by MarkoRiedel regarding this question. I've thought about his nice representation of Iverson brackets and was astonished how efficient we can handle this situation with the coefficient of technique ... :-) $\endgroup$ – Markus Scheuer Aug 19 '16 at 14:51
  • 1
    $\begingroup$ @MarkusScheuer thanks for your indications: the paper The Method of Coefficients- by D. Merlini, R. Sprugnoli, M. C. Verri provides a clear and interesting introduction. Also, MarkoRiedel's definition for Iverson bracket is something to pinpoint: my thanks to him as well. $\endgroup$ – G Cab Aug 19 '16 at 16:22
  • 1
    $\begingroup$ @MarkoRiedel, wish to thank you for pointing out the "alternative" definition for Iverson bracket ( in the answer to the other post cited by Markus). $\endgroup$ – G Cab Aug 19 '16 at 16:25
4
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\sum_{k = 0}^{n}\pars{-1}^{k}{n! \over k!\pars{n - k}!} \,\pars{n - k}^{n + 1}\ =\ {\pars{n + 1}n \over 2}\,n!:\ ?}$

\begin{align} &\color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \over k!\pars{n - k}!} \,\pars{n - k}^{n + 1}}\ =\ \sum_{k = 0}^{n}\pars{-1}^{k}\,{n \choose k}\ \overbrace{\pars{n + 1}! \oint_{\verts{z}\ =\ 1}{\expo{\pars{n - k}z} \over z^{n + 2}} \,{\dd z \over 2\pi\ic}}^{\ds{\pars{n - k}^{n + 1}}} \\[5mm] = & \pars{n + 1}!\oint_{\verts{z}\ =\ 1}\,\, {\expo{nz} \over z^{n + 2}}\,\, \sum_{k = 0}^{n}{n \choose k}\pars{-\expo{-z}}^{\, k}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{n + 1}!\oint_{\verts{z}\ =\ 1},\,\, {\expo{nz} \over z^{n + 2}}\,\pars{1 - \expo{-z}}^{n}\,{\dd z \over 2\pi\ic} = \pars{n + 1}!\oint_{\verts{z}\ =\ 1}\,\, {\pars{\expo{z} - 1}^{n} \over z^{n + 2}}\,{\dd z \over 2\pi\ic}\tag{1} \end{align}


$\ds{\pars{\expo{z} - 1}^{n}}$ is related, as a generating function, to the Stirling Numbers of the Second Kind. Namely, \begin{equation} \pars{\expo{z} - 1}^{n} = n!\sum_{j = 0}^{\infty}\braces{j \atop n}\,{z^{\, j} \over j!} \tag{1.1} \end{equation} $\ds{\braces{j \atop n}}$ is a Stirling Number of the Second Kind. With this expression, $\ds{\pars{1}}$ is reduced to: \begin{align} &\color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \over k!\pars{n - k}!} \,\pars{n - k}^{n + 1}}\ =\ \pars{n + 1}!\, n!\sum_{j = 0}^{\infty}{\braces{j \atop n} \over j!}\ \overbrace{\oint_{\verts{z}\ =\ 1}\,\, {1 \over z^{n + 2 - j}}\,\,{\dd z \over 2\pi\ic}} ^{\ds{\delta_{n + 2 - j,1}}} \\[5mm] = &\ \pars{n + 1}!\, n!\sum_{j = 0}^{\infty}{\braces{j \atop n} \over j!}\, \delta_{j,n + 1} = \pars{n + 1}!\, n!\,{\braces{n + 1 \atop n} \over \pars{n + 1}!} = n!\braces{n + 1 \atop n}\tag{2} \end{align}
However, $\ds{\braces{n + 1 \atop n}}$ satisfies the 'simple identity' $\ds{\braces{n + 1 \atop n} = {n + 1 \choose 2} = {\pars{n + 1}n \over 2}}$ such that the expression $\ds{\pars{2}}$ becomes: $$ \color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \over k!\pars{n - k}!} \,\pars{n - k}^{n + 1}} = \color{#f00}{{\pars{n + 1}n \over 2}\,n!} $$

ADDENDA:
Following @MarkoRiedel comment ( see below ), we can 'jump directly' from expression $\ds{\pars{1}}$: \begin{align} &\color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \over k!\pars{n - k}!} \,\pars{n - k}^{n + 1}} = \pars{n + 1}!\bracks{z^{n + 1}}\bracks{\pars{\expo{z} - 1}^{n}} \\[5mm] = & \pars{n + 1}!\bracks{n!\,{\braces{n + 1 \atop n} \over \pars{n + 1}!}} = n!\braces{n + 1 \atop n} = \color{#f00}{{\pars{n + 1}n \over 2}\,n!} \end{align} where we used the generating function $\ds{\pars{1.1}}$.

$\endgroup$
  • $\begingroup$ (+1). Nice work, You don't need the Kronecker delta, you can read off the Stirling number instantly from the first closed form integral you found. $\endgroup$ – Marko Riedel Aug 17 '16 at 20:26
  • 1
    $\begingroup$ @MarkoRiedel Thanks a lot. Yes: I can avoid the $\delta$'s but it's the 'step by step' solution. It avoids some user asks for the "parachute result". $\endgroup$ – Felix Marin Aug 17 '16 at 22:07
  • $\begingroup$ @MarkoRiedel I just add an ADDENDA which is related to your suggestion. Thanks. $\endgroup$ – Felix Marin Aug 19 '16 at 19:28
  • $\begingroup$ Okay! I think we have a very useful page now. $\endgroup$ – Marko Riedel Aug 19 '16 at 20:10
  • $\begingroup$ It would be an honor to see a proof using your methods of the second identity at this MSE link that is if you are interested and have the time. Second answers frequently achieve simplification and streamlining compared to first answers. $\endgroup$ – Marko Riedel Aug 23 '16 at 20:51
3
$\begingroup$

Write $$(n-k)^{n+1}=\sum_{j=0}^{n+1}\,a_j\,\binom{k}{j}$$ for some $a_0,a_1,a_2,\ldots,a_{n+1}\in\mathbb{Z}$. Clearly, $$a_{n+1}=(-1)^{n+1}\,(n+1)!$$ and $$a_n=(-1)^n\,\frac{n(n+1)}{2}\,n!\,.$$ That is, $$\sum_{k=0}^{n}\,(-1)^k\,\binom{n}{k}\,(n-k)^{n+1}=\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,\sum_{j=0}^{n+1}\,a_j\,\binom{k}{j}=\sum_{j=0}^{n+1}\,a_j\,\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,\binom{k}{j}\,.$$ Using the identity $\binom{n}{k}\,\binom{k}{j}=\binom{n}{j}\,\binom{n-j}{k-j}$ for integers $n,k,j$ with $0\leq j\leq k\leq n$, we obtain $$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,(n-k)^{n+1}=\sum_{j=0}^{n}\,(-1)^j\,a_j\,\binom{n}{j}\,\sum_{k=j}^n\,(-1)^{k-j}\,\binom{n-j}{k-j}\,,$$ or $$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,(n-k)^{n+1}=(-1)^n\,a_n=\frac{n(n+1)}{2}\,n!\,.$$

P.S. While the term involving $a_{n+1}$ vanishes, the coefficient $a_{n+1}$ need be evaluated in order to determine $a_n$. In general, $$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,f(k)=(-1)^n\,b_n\,,$$ where $$f(x)=\sum_{j=0}^d\,b_j\,\binom{x}{j}$$ with $d\in\mathbb{Z}$ greater than or equal to $n$ and $b_0,b_1,b_2,\ldots,b_d\in K$, where $K$ is an extension field of $\mathbb{Q}$.

$\endgroup$
  • $\begingroup$ After reading this, the OP may like to look up "Stirling numbers". $\endgroup$ – GEdgar Aug 17 '16 at 15:33
  • $\begingroup$ @thuzhf I intentionally removed the $a_{n+1}$-term after "we obtain" because the summand with $a_{n+1}$ vanishes. $\endgroup$ – Batominovski Aug 18 '16 at 14:01
  • $\begingroup$ @Batominovski I see, and I modified two places, and what about the other one? $\endgroup$ – Daniel Aug 18 '16 at 14:06
  • $\begingroup$ @thuzhf What other place? I only saw that you changed the sum from $\sum_{j=0}^n$ to $\sum_{j=0}^{n+1}$ after "we obtain." Did I miss something? $\endgroup$ – Batominovski Aug 18 '16 at 14:08
  • 1
    $\begingroup$ @Batominovski This time I can't modify it, because it says "Edits must be at least 6 characters". But it is where after you said "Using the identity ...", and the "identity" you used is not fully reflected in the next line. I mean, you have two $\binom{n-j}{k-j}$ there. $\endgroup$ – Daniel Aug 18 '16 at 14:19

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.