For each $m$ we have found the values of

$$\sum_{j=0}^m {m \choose j}(-1)^j p(j)$$

for polynomials of degree at most m.

Use a combinatorial story to find the Stirling number

$$m+1 \brace m$$

and deduce a formula for

$$\sum_{j=0}^m {m \choose j}(-1)^j j^{m+1}.$$

In my Combinatorics lectures, we studied a theorem relating to orthogonality for binomial coefficients. This is what the first sentence of the problem relates to.

So, I know that

$$\sum_{j=0}^m {m \choose j}(-1)^j p(j) = \begin{cases}

0 & \text{when $\deg(p)\leq m-1$} \\

(-1)^m m! & \text{when $\deg(p) = m.$}

\end{cases}$$

By calculating the result of $m+1 \brace m$ for various values of $m$ ($2, 3$ and $4$, to be precise), I managed to show that

$${m+1 \brace m} = {m+1 \choose 2}.$$

However, I am unsure how to solve the very last part of the problem (which requires a deduction).

My main thought about it so far is that: this re-arranged version of the formula for $m+1 \brace m$

$$\sum_{j=0}^m {m \choose j}(-1)^j (m-j)^{m+1} = m! {m+1\choose 2}$$

looks very similar to the formula for the orthogonality for binomial coefficients when $\deg(p) = m$

$$\sum_{j=0}^m {m \choose j}(-1)^j j^{m} = (-1)^m m!.$$

I have not yet been able to relate the two, though.

I would greatly appreciate a HINT(S) as to how to solve this last part of the problem.