# How many ways can you fill a list with $n$ slots with $m$ letters, $m<n$, making sure to use each one once?

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.

-
I think it's the factorial of the number of distinct letters. – saadtaame Mar 1 '13 at 2:22
Now you can't fill all $n$ slots, there are $n-m$ slots that will be empty – Belgi Mar 1 '13 at 2:41
Yes but you can reuse letters, you just must use each one once. – laplacian13 Mar 1 '13 at 2:42
Yes, they would be. Assuming there is something in that first blank. – laplacian13 Mar 1 '13 at 2:47

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:

"GFEDCBA" is a permutation of "ABCDEFG"
"ABC"     is NOT a permutation of "ABCDEFG"


Thus, the number of rearrangements possible (requiring every letter to be used once) is $n!$

-
What would you say about the word $aaa$ ? it have only $1$ permutation – Belgi Mar 1 '13 at 2:33
You didn't use each letter once in constructing the word... – apnorton Mar 1 '13 at 2:34
I got the question as using each appearance of a letter once, probably I got it wrong.. – Belgi Mar 1 '13 at 2:36
Actually, I think you have a better approach to the question. Your approach works for more cases than mine does... :\ Words tend to have repeat letters. (+1 to your answer) – apnorton Mar 1 '13 at 2:42

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 ?

-
This makes sense (and answers my last [incorrect] question perfectly). Thanks for the quick help. Unfortunately I meant to ask something much more confusing >< – laplacian13 Mar 1 '13 at 2:48