Summing factors of binomial coefficients - get general formula?

Question

Consider summing more and more factors of binomial coefficients:

Assuming[n ∈ Integers && n > 0, Sum[Binomial[n, i] // FunctionExpand, {i, 1, n}]] // FullSimplify

-1 + 2^n

Assuming[n ∈ Integers && n > 0, Sum[Binomial[n, i] Binomial[n - i, j] // FunctionExpand, {i, 1, n}, {j, 1, n - i}]] // FullSimplify

1 - 2^(1 + n) + 3^n

Assuming[n ∈ Integers && n > 0, Sum[Binomial[n, i] Binomial[n - i, j] Binomial[n - i - j, k] //FunctionExpand, {i, 1, n}, {j, 1, n - i}, {k, 1, n - i - j}]] // FullSimplify

-1 + 3 2^n - 3^(1 + n) + 4^n

Assuming[n ∈ Integers && n > 0, Sum[Binomial[n, i] Binomial[n - i, j] Binomial[n - i - j, k] Binomial[n - i - j - k, l] // FunctionExpand, {i, 1, n}, {j, 1, n - i}, {k, 1, n - i - j}, {l, 1, n - i - j - k}]] // FullSimplify

1 - 2^(2 + n) + 2 3^(1 + n) - 4^(1 + n) + 5^n

We can see that in each case the result is a sum over integers to the power n with some coefficients. Now I wonder if there is a way to use Mathematica to get the general expression for an arbitrary number of factors of binomial coefficients? (Continuing the above sequence all the way up to n factors of binomial coefficients under n sums.)

Answer 1

By inspection of the first few terms we can infer that the correct generalization should be:

fun[m_, n_] := Sum[(-1)^(q + m) Binomial[m - 1, q - 1] q^n, {q, 1, m}]

which properly reproduces the results:

Table[fun[m, n], {m, 2, 5}] // MatrixForm