4
$\begingroup$

How can we calculate the series $$ I_N(n)=\sum_{m=1}^{N}m^n\binom{N}{m}? $$ with $n,N$ are integers. The first three ones are $$ I_N(1)=N2^{N-1}; I_N(2)=N(N+1)2^{N-2}; I_N(3)=N^2(N+3)2^{N-3} $$

$\endgroup$
4
$\begingroup$

Suppose we are trying to evaluate $$I_N(n) = \sum_{m=1}^N {N\choose m} m^n.$$

Observe that $$m^n = \sum_{q=0}^m {n\brace q} \frac{m!}{(m-q)!}.$$ Note also that ${n\brace 0} = 0$ so that we get for the sum $$\sum_{m=0}^N {N\choose m} \sum_{q=0}^m {n\brace q} \frac{m!}{(m-q)!}.$$

Re-write this as $$\sum_{q=0}^N {n\brace q} \sum_{m=q}^N {N\choose m} \frac{m!}{(m-q)!}$$ or $$\sum_{q=0}^N {n\brace q} \times q! \times \sum_{m=q}^N {N\choose m} {m\choose q}.$$

We now see by inspection (i.e. considering subsets of size $q$ of $N$ elements) that the inner sum can be simplified to give $$\sum_{q=0}^N {n\brace q} \times q! \times {N\choose q} 2^{N-q}.$$

Now it remains to show how to compute the Stirling numbers for fixed $q.$ Recall the marked species of set partitions $$\mathfrak{P}(\mathcal{U}(\mathfrak{P}_{\ge 1}(\mathcal{Z})))$$ which gives the generating function $$G(z, u) = \exp(u(\exp(z)-1))$$ and hence $${n\brace q} = n! [z^n] \frac{(\exp(z)-1)^q}{q!}.$$

Suppose we wanted to compute $I_N(3).$ We get $${n\brace 1} = n! [z^n] \frac{\exp(z)-1}{1!} = n! \frac{1}{n!} = 1$$ and $${n\brace 2} = n! [z^n] \frac{(\exp(z)-1)^2}{2!} = \frac{n!}{2!} \times \left(\frac{2^n}{n!}-2\frac{1}{n!}\right) = 2^{n-1} - 1.$$ and finally $${n\brace 3} = n! [z^n] \frac{(\exp(z)-1)^3}{3!} = \frac{n!}{3!} \times \left(\frac{3^n}{n!} - 3\frac{2^n}{n!} + 3\frac{1}{n!}\right) \\ = \frac{1}{6} 3^n - \frac{1}{2} 2^n + \frac{1}{2}.$$

This gives for $I_N(3)$ the expression $${N\choose 1} 2^{N-1} + (2^2-1) \times 2 \times {N\choose 2} 2^{N-2} + \left(\frac{1}{6} 3^3 - \frac{1}{2} \times 2^3 + \frac{1}{2}\right) \times 6 \times {N\choose 3} 2^{N-3}.$$

This is $$2^{N-3} \times \left(4N + 6N(N-1)+ N(N-1)(N-2)\right).$$ which simplifies to $$I_N(3) = N^2\times (N+3)\times 2^{N-3}.$$

$\endgroup$
  • $\begingroup$ Thanks. But usual we would set $\binom{n}{0}=1$ instead. The $m=0$ term can be included since $0^n=0$. $\endgroup$ – Roger209 Dec 29 '14 at 1:08
3
$\begingroup$

(This isn’t really an answer, but it’s too long for a comment.)

The first half of Marko’s answer can also be obtained by a simple combinatorial argument.

It’s not hard to see that $I_N(n)$ counts the ordered pairs $\langle f,A\rangle$ such that $f:[n]\to[N]$ and $\operatorname{ran}f\subseteq A$: for each $m\in[N]$, $m^n\binom{N}m$ is the number of pairs $\langle f,A\rangle$ such that $A\subseteq[N]$, $|A|=m$, and $\operatorname{ran}f\subseteq A$.

We can also count these pairs in the following way. For $m\in[N]$ there are $n\brace m$ partitions of $[n]$ into $m$ parts; these parts will be the fibres of a function $f:[n]\to[N]$. The function $f$ can be chosen in $N^{\underline m}=m!\binom{N}m$ ways. Then we can choose a subset $A$ of $[N]$ that contains $\operatorname{ran}f$ in $2^{N-m}$ ways. Thus,

$$I_N(n)=\sum_{m=1}^N{n\brace m}N^{\underline m}2^{N-m}=\sum_{m=1}^N{n\brace m}m!\binom{N}m2^{N-m}\;.$$

$\endgroup$

Not the answer you're looking for?Browse other questions tagged or ask your own question.