# Number of ways for a k-letter word to have no repeat letters.

Assuming a standard English 26-letter alphabet, and $k<26$, what's the number of $k$-letter words where the letters don't repeat? So for example 'house' has no repeat letters, while 'rolls' has a repeat.

The way I solved this was to first select the $k$ letters which will make up the word, and then count all the permutations, so $$N={26 \choose k}k!=26\cdot 25 \cdot \dots \cdot (26-k+1)$$

Which is like sampling with replacement, where order doesn't matter. However, I don't understand that - looking at the problem I would say that order matters (abc is a different word than cab) and that there can't be any replacement (after all we don't want repeats!), but this is obviously wrong.

How should I think about this problem? Why is it like sampling with replacement where order doesn't matter? Or indeed, why not without replacement and with order...

• ${26 \choose k}$ is the set of $k$ letter you can use, for example $\{a,b,c,d\}$ is one of them. With each one, you can do $k!$ words permutating them: abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda, bdac, bdca, cabd, cadb, cbad, cbda, cdab, cdba, dabc, dacb, dbac, dbca, dcab, dcba. Counting this, you have no repetion, and actually the order is important – Exodd Sep 27 '14 at 16:14
• You're right that the expression that comes out is similar to 'stars-and-bars' style expressions, but note that the fact that you're inserting bars means that if you were sampling with replacement from a set of 26 items your first value would be larger than 26 - it would be $26+k-1$. What you're discovering is that there are many isomorphisms in combinatorics - ways of counting what look like different things that turn out to be the same. – Steven Stadnicki Sep 27 '14 at 16:34
• Would there be a way to frame this question differently, so that the answer is $N= {26+k-1 \choose k}$, as in sampling without replacement where order matters? I also don't understand what am I overcounting if I just used this approach to the current problem. – Spine Feast Sep 27 '14 at 17:38

Sampling with replacement means that any letter you use is put back and can be re-used. In this case, the number of $k$-letter words is $26^k$. (Order here does matter. It's a bit trickier if order doesn't matters.)
What you are doing is sampling without replacement: no letter is used twice. If order doesn't matter, then there are ${26 \choose k}$ possibilities. But since order does matter, you were right to multiply by $k!$ to get all permutations of all possible $k$-sets.