1
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ What exactly would you expect to get? $\endgroup$ – Igor Rivin Oct 9 '15 at 10:49
  • $\begingroup$ Can you include in your question the array consisting from first values of your function $f(m,n)$? $\endgroup$ – Alexey Ustinov Oct 9 '15 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 '15 at 11:14
  • $\begingroup$ sometimes an alternating sum is easier to work with $\endgroup$ – JMP Oct 9 '15 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 '15 at 11:39
1
$\begingroup$

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,1)=-1+4^n$

$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]

Improve this answer
$\endgroup$
  • 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 '15 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 '15 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 '15 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.