2
$\begingroup$

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?

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

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .