Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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??

share|improve this question
    
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
2  
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. Nov 30 '10 at 12:06
5  
Speaking of which... –  J. M. Nov 30 '10 at 12:08
    
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
4  
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
show 5 more comments

3 Answers

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.

share|improve this answer
    
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 7:29
    
Yes, you're right, I messed up the indexing slightly. Thanks. –  Qiaochu Yuan Feb 17 '11 at 9: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? –  user4689 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
add comment

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

share|improve this answer
    
But what is wrong with the assumption then? –  Betamoo Nov 30 '10 at 16:29
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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