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.

I want to know the formula for the following:

1.) Permutation of N different items taken 1,2,3...N at a time.
2.) Permutation of N items taken 1,2,3...N at a time but with repeating items.

I couldn't search this in the internet. I tried to derive this formula using the basic formulas of permutation and combinations, but after hours of trying they just gave me headache.

To make my question clear:

Since the formula for Permutations of n things taken r at a time is:

P(n,r) = n! / (n-r)!


*On my 1st problem, I want to get:

Psum(n) = P(n,1) + P(n,2) + P(n,3) + ... + P(n,n)

*On my 2nd problem, it's the same as the 1st problem but there are repeating items.
ex: What is Psum(n) in the word COMMITTEE? (M=2, T=2, E=2)

I already came-up with a formula for my 1st problem but it is recursive. This is the formula so far:

Psum(n) = n*[1 + Psum(n-1)]

Sorry for my english.

share|improve this question
3  
When you are trying to find a combinatorial formula for something like this, and you can't figure out where to start, the best strategy is always to calculate the answers for small n and put them into oeis.org –  Oliver Jan 15 '12 at 5:30
1  
In this case, you will discover that your first problem has been discussed since 1659. I don't see that there is a another formula you are likely to prefer to the recursive one you already found. –  Oliver Jan 15 '12 at 5:38
    
If you include the empty word in your count by adding $P(n,0)$, the recurrence becomes $P_{\text{sum}}(n)=nP_{\text{sum}}(n-1)+1$, which looks marginally nicer and has direct –  joriki Jan 15 '12 at 9:04
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.