# 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. Aug 14, 2013 at 2:50
• @AndréNicolas That is very true. Aug 14, 2013 at 3:12
• Now how to solve taking into account repeated letters? Aug 14, 2013 at 3:30
• There are messy expressions using Stirling numbers. Aug 14, 2013 at 3:34
• I see. In other words, I should just use an estimate? I'm fine with that. Thanks for your help. =) Aug 14, 2013 at 4:16