1
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ ${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 $\endgroup$ – Exodd Sep 27 '14 at 16:14
  • $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Sep 27 '14 at 16:34
  • $\begingroup$ 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. $\endgroup$ – Spine Feast Sep 27 '14 at 17:38
0
$\begingroup$

Your answer is right. But why don't you write that simply as 26Pk (i.e. Permutation), 1 < k < 25.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.