# Summing factors of binomial coefficients - get general formula?

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

• Oh, I'm silly... Seems like the coefficients are just binomial coefficients, power is always the same and sign is alternating... – Kagaratsch Mar 2 '17 at 22:16
• Perhaps you should self-answer, or if you do not feel motivated to do so, delete this question? – Mr.Wizard Mar 3 '17 at 0:26

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

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