|
I've been trying to solve this problem and haven't had any luck. I also haven't been able to find anything online. Clearly there are $m^n$ ways if we do not need to use each one once, but what restriction gets placed if we do? Some must be duplicated, but not all. EDIT: I'm very tired and massively miswrote this question at first. I explained this in the comments to a response, but it seems to have been deleted now. Sorry to anyone who answered the first question. |
|||||||||
|
|
This is an application of the principle of inclusion-exclusion. You can start with the answer $m^n$ that you give for the case where there is no requirement that each letter be used at least once. Since this count includes words that don't use all of the letters, you can subtract these away. There are $(m-1)^n$ words that omit a particular one of the letters, and there are $m$ possibilities for the omitted letter. Subtracting these gives $m^n-m(m-1)^n$ words. But you've subtracted away too much since words that omit exactly two of the letters got subtracted twice. You can add these back: there are $\binom{m}{2}$ choices for the two omitted letters, and $(m-2)^n$ words you can make with the remaining letters. This gives $m^n-m(m-1)^n+\binom{m}{2}(m-2)^n$. But words that omit exactly three of the letters still are not counted correctly... Continuing in this way, the principle of inclusion-exclusion implies that there are $$\sum_{j=0}^m(-1)^j\binom{m}{j}(m-j)^n$$ words that use each letter at least once. This equals $m!\lbrace{n\atop m}\rbrace$, where $\lbrace{n\atop m}\rbrace$ is the Stirling number of the second kind. Addendum: The Stirling number of the second kind $\lbrace{n\atop m}\rbrace$ is usually defined as the number of partitions of a set of $n$ objects into $m$ non-empty unlabeled subsets. Think of the $n$ objects as the letter slots. The partition determines which slots get the same letter. But since the subsets are unlabeled, there are $m!$ ways of assigning the $m$ letters to the $m$ subsets. |
||||
|
|
|
Permutations are exactly what you describe. For example: Thus, the number of rearrangements possible (requiring every letter to be used once) is $n!$ |
|||||||||
|
|
It depends on the number of repititions each letter have, you have to divide $n!$ (which is the number of permutations when all the letters are considered distinct, even if it the same letter) by ִ$$r_{1}!\cdot...r_{k}!$$ Where $k$ is the number of distinct letters and $r_{1},...,r_{k}$ is the number of repetitions each letter have. Can you see why ? |
|||
|
