# Counting the number of permutations of all sizes without repetition

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?

-
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