I have a trouble with the following sum $\sum_{i=0}^n\binom{n}{i}S(i,m)3^i$, where $S(i,m)$ is the Stirling number of the second kind (the number of all partitions of $i$ elements into $m$ nonempty sets).

Below it was obtained the sum $f(n,m)=\frac{1}{m!}\sum_{k=0}^m(-1)^{m-k}\binom{m}{k}(1+3k)^n$. Is there a further simplification of this expression?

  • $\begingroup$ What exactly would you expect to get? $\endgroup$
    – Igor Rivin
    Oct 9, 2015 at 10:49
  • $\begingroup$ Can you include in your question the array consisting from first values of your function $f(m,n)$? $\endgroup$ Oct 9, 2015 at 10:55
  • $\begingroup$ I would like to obtain a closed form of my sum (if it exists, of couse). It will be the best solution. But I will be pleased for any advice. $\endgroup$
    – Artem
    Oct 9, 2015 at 11:14
  • $\begingroup$ sometimes an alternating sum is easier to work with $\endgroup$
    – JMP
    Oct 9, 2015 at 11:25
  • $\begingroup$ Unfortunately, my sum can not be alternating, since it occurs in the counting of solutions of equations over some semilattices. $\endgroup$
    – Artem
    Oct 9, 2015 at 11:39

1 Answer 1


here is a table of $f(m,n)$ for small values of $m$ and $n\geq m$ (note that $f(m,n)=0$ for $n<m$):


$f(n,2)=\tfrac{1}{2}\left(1-2\cdot 4^n+7^n\right)$

$f(n,3)=\tfrac{1}{6}\left(-1+3\cdot 4^n-3\cdot 7^n+10^n\right)$

$f(n,4)=\tfrac{1}{24}\left(1-4\cdot 4^n+6\cdot 7^n-4\cdot 10^n+13^n\right)$

$f(n,5)=\tfrac{1}{120}\left(-1+5\cdot 4^n-10\cdot 7^n+10\cdot 10^n-5\cdot 13^n+16^n\right)$

$f(n,6)=\tfrac{1}{720}\left(1-6\cdot 4^n +15\cdot 7^n-20\cdot 10^n+15\cdot 13^n-6\cdot 16^n+19^n\right)$

there is a pattern, which as Todd Trimble points out is

$$f(n,m)=\frac1{m!} \sum_{k=0}^m (-1)^{m-k} \binom{m}{k} (1 + 3k)^n$$

note: Mathematica gets $f(n,2)$ wrong... [SE post]

  • 1
    $\begingroup$ The general pattern is $\frac1{m!} \sum_{k=0}^m (-1)^{m-k} \binom{m}{k} (1 + 3k)^n$? $\endgroup$
    – Todd Trimble
    Oct 9, 2015 at 11:59
  • $\begingroup$ You are right, and I can prove this formula! Now the question is: how to simplify the obtained pattern? $\endgroup$
    – Artem
    Oct 9, 2015 at 12:03
  • $\begingroup$ Except for the factor in front of the sum, this is the $m^{th}$ iterate of the successive difference operator applied to the function $k \mapsto (1 + 3k)^n$ (for what that's worth). $\endgroup$
    – Todd Trimble
    Oct 9, 2015 at 12:18

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.