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 have this piece of software where the user enters a sequence of letters (doesn't matter which ones and there can be repeats). I then get all permutations of all lengths without repetition (e.g. "tee" -> "e", "t", "ee", "et", "te", "eet", "ete", "tee"), which I've done.

Now I need to count how many of them there are before I actually permute them all (e.g. "tee" -> 8). Without repeated letters, I would have (1! x 2! x 3! x …); but repeated letters complicates things. How would I go about solving this?

share|improve this question
1  
Without repeated letters you would have $n+n(n-1)+n(n-1)(n-2)+\cdots +n!$. To get pleasant form, divide by $n!$. You get $n!(1+1+\frac{1}{2!}+\cdots+\frac{1}{(n-1)!})$, which unless $n$ is small is close to $n!e$, where $e$ is the base for natural logarithms. –  André Nicolas Aug 14 '13 at 2:50
    
@AndréNicolas That is very true. –  fumoboy007 Aug 14 '13 at 3:12
    
Now how to solve taking into account repeated letters? –  fumoboy007 Aug 14 '13 at 3:30
    
There are messy expressions using Stirling numbers. –  André Nicolas Aug 14 '13 at 3:34
    
I see. In other words, I should just use an estimate? I'm fine with that. Thanks for your help. =) –  fumoboy007 Aug 14 '13 at 4:16

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.