# Simplifying a sum involving Stirling numbers of the second kind

What is known of the following sum? If it's not well studied, what can we say about it? $$f(x,m)=\sum_{n=1}^x \sum_{j=1}^n \bigg\lbrace {m \atop j}\bigg\rbrace$$ Can we simplify it?

$$g(x,m)=\sum_{n=1}^\infty \sum_{j=1}^n \bigg\lbrace {m \atop j}\bigg\rbrace x^n$$

Does this have a closed/simplified (or at the very least, explicit) form? (Forgive me if this is trivial; I have not studied generating functions for long.)

• For $f(x)$, $\sum_{j=1}^n \bigg\lbrace {n \atop j}\bigg\rbrace$ is called Bell number. $g(x)$ is exactly the generating function of Bell numbers and it is $\sum_{n=1}^\infty \frac{1}{e(1-nx)n!}$. – didgogns May 2 '18 at 16:50
• @didgogns Yes, but what if the inner summation doesn't sum to $n$? – Tiwa Aina May 2 '18 at 17:56
• So if m in your equations are not typo, you should write them as $f(x, m)$ and $g(x, m)$ – didgogns May 3 '18 at 3:53

Let me premise that the partial sum over the lower index of Stirling Numbers, same as for the Binomial coefficient, do not have a known "simple" formula.
So in the case that you propose, we may just try and recast it into different formulations, involving related Numbers and functions, which could indicate some interesting properties.

First, let's take the sums starting from $0$; it will be easy later (if needed) to deduct the values of the sum starting from $1$.
And let's replace in $f$ the $x$ with $q$ to avoid confusion with the generating function.
Then we can rewrite $f(q,m)$ as \eqalign{ & f(q,m) = \sum\limits_{0\, \le \,n\, \le \,q} {\sum\limits_{0\, \le \,j\, \le \,n} {\left\{ \matrix{ m \cr j \cr} \right\}} } = \sum\limits_{0\, \le \,j\, \le \,x} {\sum\limits_{\,j\, \le \,n\, \le \,q} {\left\{ \matrix{ m \cr j \cr} \right\}} } = \cr & = \sum\limits_{0\, \le \,j\, \le \,q} {\left( {q - j + 1} \right)\left\{ \matrix{ m \cr j \cr} \right\}} = \sum\limits_{\left( {0\, \le } \right)\,j\, \le \,q} {\left( {q - j + 1} \right)\left\{ \matrix{ m \cr j \cr} \right\}} = \cr & = \sum\limits_{0\, \le \,k\left( {\, \le \,q} \right)} {\left( {k + 1} \right)\left\{ \matrix{ m \cr q - k \cr} \right\}} = \cr & = \left( {q + 1} \right)\sum\limits_{0\, \le \,k\left( {\, \le \,q} \right)} {\left\{ \matrix{ m \cr q - k \cr} \right\}} - \sum\limits_{0\, \le \,k\left( {\, \le \,q} \right)} {\left( {q - k} \right)\left\{ \matrix{ m \cr q - k \cr} \right\}} = \cr & = \left( {q + 1} \right)\sum\limits_{0\, \le \,k\left( {\, \le \,q} \right)} {\left\{ \matrix{ m \cr q - k \cr} \right\}} - \sum\limits_{0\, \le \,k\left( {\, \le \,q} \right)} {\left\{ \matrix{ m + 1 \cr q - k \cr} \right\}} + \sum\limits_{0\, \le \,k\left( {\, \le \,q - 1} \right)} {\left\{ \matrix{ m \cr q - 1 - k \cr} \right\}} \cr}

After that, many different paths can be explored, also depending on the goal of your study

a) Relation with Touchard Polynomials

The Touchard Polynomials are defined as $$T_{\,m} (x) = \sum\limits_{0\, \le \,k\,\left( { \le \,m} \right)} {\left\{ \matrix{ m \cr k \cr} \right\}x^{\,k} }$$ so we have \eqalign{ & \sum\limits_{0\, \le \,q} {f(q,m)\,x^{\,q} } = \sum\limits_{0\, \le \,q} {\left( {\sum\limits_{0\, \le \,k\left( {\, \le \,q} \right)} {\left( {k + 1} \right)\left\{ \matrix{ m \cr q - k \cr} \right\}} } \right)\,x^{\,q} } = \cr & = \sum\limits_{0\, \le \,q} {\sum\limits_{0\, \le \,k\left( {\, \le \,q} \right)} {\left\{ \matrix{ m \cr q - k \cr} \right\}x^{\,q - k} \left( {k + 1} \right)x^{\,k} } \,} = \left( {\sum\limits_{0\, \le \,j\left( {\, \le \,m} \right)} {\left\{ \matrix{ m \cr j \cr} \right\}x^{\,j} } } \right)\left( {\sum\limits_{0\, \le \,k} {\left( {k + 1} \right)x^{\,k} } } \right) = \cr & = T_{\,m} (x){d \over {dx}}\sum\limits_{0\, \le \,k} {x^{\,k + 1} } = T_{\,m} (x){d \over {dx}}{x \over {1 - x}} = {1 \over {\left( {1 - x} \right)^{\,2} }}T_{\,m} (x) \cr}

b) Relation with Binomial C.

Replacing the Stirling with its representation through the binomials, we get \eqalign{ & \sum\limits_{0\, \le \,k\left( {\, \le \,q} \right)} {\left\{ \matrix{ m \cr q - k \cr} \right\}} \quad = \sum\limits_{0\, \le \,k\left( {\, \le \,q} \right)} {{1 \over {\left( {q - k} \right)!}}\sum\limits_{0\, \le \,j\left( {\, \le \,q - k} \right)} {\left( \matrix{ q - k \cr j \cr} \right)j^{\,m} \left( { - 1} \right)^{\,q - k - j} } } = \cr & = \sum\limits_{0\, \le \,k \le \,q} {\sum\limits_{0\, \le \,j\left( {\, \le \,q - k} \right)} {{{\left( { - 1} \right)^{\,q - k - j} } \over {\left( {q - k - j} \right)!}}{{j^{\,m} } \over {j!}}} } = \sum\limits_{0\, \le \,i \le \,q} {{{\left( { - 1} \right)^{\,q - i} } \over {\left( {q - i} \right)!}}\sum\limits_{0\, \le \,j\, \le \,i} {{{j^{\,m} } \over {j!}}} } \cr} which can be a starting point for constructing other ogf's.