Can $\sum_{i=0}^n (k^i)/i!$ be simplified?

Question

Can this expression be simplified?

$ \sum_{i=0}^n (k^i)/i! $

EDIT: This expression I have got as the number of possible ways to select n objects or less from k different infinite objects (you can select as many as you can from any type)...

I believe it must be equal to the number of possible ways to select n objects from k+1 different infinite objects, where the extra +1 is a dummy object, selecting one of this type means letting an empty space in the final selection (i.e. selecting n-1 not n)...

so this must be equal to:

$ (k+1)^n/n! $

Why that is not right??

Note that 1 plus this expression would be a truncation of the power series for exp(k). Perhaps you meant to start the summation at i=0? In any case this is a polynomial in k. There are more efficient ways to evaluate it than term-by-term, e.g. Horner's method. Is that the kind of "simplification" you have in mind? — hardmath, Nov 30 '10 at 12:05
That truncation of the exponential function can be expressed as an incomplete gamma, but my opinion is that's the simplest you can get for that sum, computationally speaking. — J. M. ain't a mathematician, Nov 30 '10 at 12:06
Not so relevant, but for $k=n$ this expression is asymptotically $e^n / 2$ as $n \to \infty$ (by the central limit theorem). — Shai Covo, Nov 30 '10 at 12:32
As J. M. said, this is a possible duplicate of Closed form of a partial sum of the power series of exp(x) — Ross Millikan, Nov 30 '10 at 14:11
"k infinite objects"? Make up your mind, do you have k of them or an infinite number of them? — J. M. ain't a mathematician, Nov 30 '10 at 14:45
Are you sure $k^i/i!$ is the right expression? Maybe you want $\binom{k+i-1}{i-1}$? — Yuval Filmus, Nov 30 '10 at 17:38

Qiaochu Yuan · Answer 1 · 2011-02-17T09:02:48.603

Your reasoning is incorrect. $\frac{k^i}{i!}$ is not even an integer in general, so it can't count what you're claiming it counts. While $k^i$ is the number of ways to choose $i$ objects from $k$ types of objects in order, you can't just divide by $i!$ to get rid of the ordering because some of the orderings are the same when you rearrange them.

For example, if $k = 2, i = 3$, then the possible ways to choose $3$ objects from $2$ types of objects in order are $AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB$, and the possible ways to choose $3$ objects from $2$ types are $AAA, AAB, ABB, BBB$, which is $4$ and not $\frac{2^3}{3!} = \frac{4}{3}$. When you are dividing by $3!$ you are pretending that the different orderings group evenly into groups of $6$ but, as you can see, they don't.

The actual number you want, for fixed $i$, is the number of multisets of $i$ objects on a $k$-element set, which is actually

$${k+i-1 \choose i}.$$

This can be proven using what's called the "stars and bars" argument, as well as Burnside's lemma. Note that if $i$ is fixed and $k$ tends to infinity this is asymptotically, but not exactly, $\frac{k^i}{i!}$.

As you say, if you want the number of multisets of $n$ or less objects, then you just add in a dummy element of the set, so the final answer is

$$\sum_{i=0}^n {k+i-1 \choose i} = {k+n \choose n}.$$

This identity is sometimes known as the hockey-stick identity because it has an interpretation in terms of summing along a hockey-stick-like shape on Pascal's triangle.

Unless I've remembered combinatorials wrongly you're saying f(1,n)=(1+n n+1)=1, but I believe it should be n (or n+1, to include none). — Mark Hurd, Feb 17 '11 at 07:29
Yes, you're right, I messed up the indexing slightly. Thanks. — Qiaochu Yuan, Feb 17 '11 at 09:03
Here's an aside question: I've seen $\left(!!\binom{n}{k}!!\right)$ used for the multiset coefficients in a couple places. Is this standard notation? — , Feb 17 '11 at 12:50
@Graham: more or less. It is used, for example, in Stanley's book. — Qiaochu Yuan, Feb 17 '11 at 13:28

Ross Millikan · Answer 2 · 2010-11-30T15:13:14.800

1

In response to the edited question, it is not right. If we just let n=2, $1+k+\frac{k^2}{2}\neq \frac{(k+1)^2}{2}$. The difference is $\frac{1}{2}$

edited Nov 30 '10 at 15:13

answered Nov 30 '10 at 14:30

Ross Millikan

374,822

But what is wrong with the assumption then? – Betamoo Nov 30 '10 at 16:29

score 1 · Answer 3 · answered Feb 16 '11 at 15:12

Your existing formula does not produce integers all the time:

Consider number of types, k=1

I believe that means f(k,n)=n

Your f(1,n)= $ \sum_{i=0}^n 1/i! $ which is definitely not generally an integer.

What you want is

$ \sum_{i=0}^n g(k,i) $

where g(k,i) is the number of ways you can select exactly i objects from upto k types.

Which can be similarly expanded to

$ \sum_{i=0}^n \sum_{j=0}^k h(j,i) $

where h(j,i) is the number of ways you can select exactly i objects from exactly j types.

Note, because h(j,i)=0,i<j, we can swap the summations:

$ \sum_{j=0}^k \sum_{i=j}^n h(j,i) $

[ and l(j,n)=$ \sum_{i=j}^n h(j,i) $ is the number of ways you can select between j and n objects from exactly j types

which is the same as selecting between 0 and n-j objects from up to j types

thus l(j,n)=$ \sum_{i=0}^{n-j} g(j,i) $

so f(k,n)=$ \sum_{i=0}^n g(k,i) = \sum_{j=0}^k \sum_{i=0}^{n-j} g(j,i) $ ]

One of g or h (or l) should be definable using combinations as suggested by Yuval Filmus's comment.

Can $\sum_{i=0}^n (k^i)/i!$ be simplified?

3 Answers3